MPVCC问题的AC稳定性及算法研究_许娜.pdf

第 卷第期 年月辽宁师范大学学报（自然科学版）（）收稿日期：基金项目：辽宁省教育厅科学技术研究青年项目（）作者简介：许娜（），女，辽宁大连人，辽宁师范大学讲师，博士 ：文章编号：（）：问题的 稳定性及算法研究许娜，张林林，吴霜（辽宁师范大学 数学学院，辽宁 大连 ）摘要：带有垂直互补约束的数学规划（）问题是一类较难处理的优化问题 因此，通常应用专门的算法来求解 近年来，序列最优性条件被广泛应用于算法的收敛性分析，但是非线性优化问题的序列最优性条件并不适用于 因此，基于 的稳定性，给出了近似稳定性（稳定性），并证明了它是 的序列最优性条件 此外，还证明了在 正则性下，稳定性可以保证 稳定性成立 最后，证明了 的增广拉格朗日方法生成的序列满足 稳定性条件关键词：带有垂直互补约束的数学规划；序列最优性条件；增广拉格朗日方法中图分类号：文献标识码：本文主要研究带有垂直互补约束的数学规划（）问题，它是带有互补约束的数学规划（）问题的推广，其具体形式如下：（）（），（），（），（），（），其中，：R R，：R R，：R R，：R R（，）是连续可微的 在经济与工程等许多领域都有着广泛的应用，但是由于其约束集合的特殊结构，约束规范（）在任何可行点处均不成立，进而条件不一定在极小点处成立 因此，在过去的几十年里，人们提出了比 条件更弱的稳定性条件，例如：稳定性、稳定性以及 稳定性，同时也提出了一些约束规范，例如：、等近年来，序列最优性条件被广泛应用于非线性优化问题的理论证明和算法实现，但是这些序列最优性条件并不适用于 基于 等人的研究结果，许娜等人将 稳定性条件推广到 ，得到了 的序列最优性条件 在本文中，基于 的 稳定性，提出了 稳定性，这个新的序列最优性条件可用于研究 算法的收敛性结果和数值实现此外，还提出了与 稳定性相关的约束规范，即 正则性，并证明了在这个较弱的约束规范下，稳定点就是 稳定点最后，考虑求解 的增广拉格朗日方法，证明了在适当的条件下，增广拉格朗日方法产生的点列满足 稳定性条件，若还满足 正则性，则收敛到 的稳定点基础知识本节给出文中将要用到的一些基本概念首先给出指标集的定义，假设是 的可行域，第期许娜等：问题的 稳定性及算法研究对一个给定的可行点，令（）（），（）（，）（）.定义（外极限）设：RR是一集值映射，在处的外极限为 （），（），.定义（外半连续）称集值映射：RR在处是外半连续的，如果 （）（）.定义（稳定性）称是 的稳定点，如果存在 R，R，R，使得满足（）（）（）（），（），（），当（）（）时，.定义.设，称 常秩约束规范（）在处成立，如果存在的邻域（），使得梯度组（）（），（），（）（）对任意的（）有相同的秩.定义.设，（），是空间 （），的一组基，称 松弛正线性约束规范（）在处成立，如果存在的邻域（）使得（）对任意的（），（），有相同的秩；（）对任意的（）和（），若（），（），（），（，）是正线性相关的，那么对于任意的（），有（），（），（），（，）是线性相关的.基于稳定性的序列最优性条件本节给出 的 稳定性的定义，并证明了 稳定性是一个合理的序列最优性条件序列最优性条件与算法的终止准则密切相关，因此，稳定性有助于研究 算法的收敛性分析定义称是 的近似弱稳定点（稳定点），如果存在序列 和 （，）R R R 使得 ，（）（）（）（）（），（）（），（），（），.（）辽宁师范大学学报（自然科学版）第 卷定义.设是 的 稳定点，如果序列 和序列 （，）RR R 还满足 ，（）那么称是近似稳定点（稳定点）.定义.设是 的 稳定点，如果序列 和序列 （，）R R R 还满足 ，那么称是近似 稳定点（稳定点）.由定义.定义.可知，稳定性 稳定性 稳定性.下面由文献 的结果可以直接得到 稳定性是合理的序列最优性条件.定理.假设是 的局部最优解，那么是 稳定点.证设为 的局部最优解.由文献 中定理.可知是稳定点，从而是 稳定点.为了将 稳定性与稳定性联系起来，首先给出 正则性的定义并证明 正则性是 的约束规范，然后在 正则性下，证明 稳定点就是稳定点定义设，称 在处满足 正则性，如果集值映射：RR在处是外半连续的，其中，（）（）（）（）R，R，R，（），（，）（），（）（），：（）（），即 （）（）.定理假设，正则性在处成立当且仅当对于任意连续可微的目标函数，如果是 稳定点，那么是稳定点证（必要性）假设是连续可微的函数，由于是 稳定点，则存在序列 和 （，）R R R 满足 （），（），.不失一般性，令，（），（，）（），由 稳定点定义可得 ，（）（），（）（），（），（）（），则有 （），其中，（），（）（）（）.（）由于 正则性在处成立可得（）（）（）.因此，是稳定点第期许娜等：问题的 稳定性及算法研究（充分性）假设 （），则存在子列 和满足，（），由（），对任意的都存在，（）RRR 使得式（）和式（）成立下面证 明（），定 义 目 标 函 数（）（），可 得 （）（）（）.因此，是 的 稳定点，则由假设可知也是稳定点 故 （）（）.下面结合定理和定理可以得到 正则性是保证 问题 稳定性的新的约束规范使用文献 中定理相似的证明方法，可以得到 与 正则性之间的关系推论假设是 的局部最优解，如果 正则性在处成立，那么是 稳定点定理假设，如果 在处成立，那么 正则性在处也成立显然，下面 的新旧约束规范与稳定性之间的关系成立 正则性稳定性.增广拉格朗日方法首先回顾非线性规划（）问题：（）（），（），其中，与 中的函数相同，的 增广拉格朗日函数定义如下：（，）（）（）（）（），（）其中，R，（，）R R，.可以将 改写为如下形式：（）（），（），（），（），其中，（）（），（）.定义 的 增广拉格朗日函数为（，）（），（），其中，（）（）（）（）（）（）（）（）.下面给出 的增广拉格朗日方法及其收敛性结果算法 的增广拉格朗日方法选取 ，以及.令，.置.步 计算，（）的一个近似解使其满足（，）.辽宁师范大学学报（自然科学版）第 卷步 定义 （），（），.若且 （），（），令.否则，令.步计算，置，转步定理假设 是由算法生成的序列，是 的一个极限点，.对任意的 满足（）（）和充分大的，（）（）.如果，（）在处满足 不等式，即存在，：（）R，满足 （），以及对任意的（），（），（）（），（）.（）那么是 稳定点证不失一般性，假设，.由 增广拉格朗日函数的定义可以给出乘子的如下估计：，（），（），（），（），（）.当充分大时，使得式（）成立如果，那么当（），对充分大的，有，.如果 是有界的，当（）时，由算法可知 ，则有 ，.由此可得式（）成立 对于固定的指标，首先考虑，（）有界时的情况，当（）时，如果，则 ，（）.否则，可推出 ，（），.当（）时，（）.另外，由，有 ，（）.因此，当（）时 ，可得式（）成立 同时，直接可得式（）也成立若，（）是无界的 不失一般性，可以假设，（），对所有成立，为指标的无限子集 当（）时，有 ，（），（），（）（），（）（）.由算法可知 （），（），从而，（）是有界的 令，（）（），则，（），（）（），（）（）（）（）（），（），（）（）（）（）（，（）（）.当充分大时，由于方括号里的项都是有界的，因此，（）是有界的 由，（）第期许娜等：问题的 稳定性及算法研究 和式（）可知 ，（），故 （）（）.当（）时，有（）以及 ，（）（）（），可得 .因此式（）成立为了证明式（），对任意的 满足（）（），有（），（）以及 ，（），（），（）（，（）（）（）（，（），（），（），（），（）.（）因为，（），则 有（）.对 充 分 大 的，由 假 设 条 件 可 知（）（），可得式（）中前项都是非负的，并且有 （）（）.若（），（），由，（），（），（），（），可得 .若（），（），则式（）中第三行中的项非负，因此，.综上所述，从而式（）成立推论在和定理相同的假设下，如果 正则性在成立，那么是 的稳定点数值实验及结果考虑如下带有极大极小约束的优化问题：（）（）.（）为验证算法的有效性，应用 软件编写程序，求解下面个例子例考虑带有极大极小约束的优化问题：（）（），（），（），（）.最优解是，（），最优值是，等价的 为 （），.（）应用算法可得问题（）的最终的迭代点为（，.），相应的目标函数值为.例考虑带有极大极小约束的优化问题：（）（），（.），（）.，（）.，（）.（），（）.（），（），（），（）.辽宁师范大学学报（自然科学版）第 卷最优解是（.，），最优值是.，等价的 为 ，（），（.），（），（），（），（），（），（），（）.（）应用算法可得问题（）的最终的迭代点为（.，），相应的目标函数值为.小结本文主要研究了 的序列最优性条件，提出了 的 稳定性，并证明了 稳定性条件是一个合理的序列最优性条件然后给出了 正则性，并证明了 正则性实际上是能保证稳定点的一个新的约束规范，证明了 正则性是比 更弱的约束规范 在 正则性下，稳定点就是稳定点应用 的增广拉格朗日方法产生的点列可以收敛到 稳定点，并给出数值结果验证算法的有效性参考文献：，：，（）：，（）：张杰，王全，张亚琦 中的几个新的约束规范 辽宁师范大学学报（自然科学版），（）：，（）：许娜，沈洁，姜姗 问题的稳定性的序列最优性条件研究辽宁师范大学学报（自然科学版），（）：，：，：，（，）：（），（），：；