互补约束优化问题的乘子序列部分罚函数算法

利用互补问题的Lagrange函数,
将互补约束优化问题(MPCC)转化为含参数的约束优化问题.
给出Lagrange乘子的简单修正公式,
并给出求解互补约束优化问题的部分罚函数法. 无须假设二阶必要条件成立,
只要算法产生的迭代点列的极限点满足互补约束优化问题的线性独立约束规范(MPCC-LICQ),
且极限点是MPCC的可行点, 则算法收敛到原问题的M-稳定点. 另外,
在上水平严格互补(ULSC)成立的条件下, 算法收敛到原问题的B-稳定点.     

关于求解带线性互补约束的数学规划问题正则方法的一个注记

本文主要研究在某些较弱条件下求解带线性互补约束的数学规划问题(MPLCC)正则方法的收敛性.若衡约束规划线性独立约束规范条件(MPEC-LICQ)在由正则方法产生的点列的聚点处成立,且迭代点列满足二阶必要条件,同时,若比在文[7]中渐近弱非退化条件Ⅰ更弱的渐近弱非退化条件Ⅱ在聚点处也成立,那么所有这些聚点都是B-稳定点.此外,在弱MPEC-LICQ,二阶必要条件及渐近弱退化条件Ⅱ下,我们仍能证明通过正则方法所得的聚点都是B-稳定点.     

非线性互补约束均衡问题的一个SQP算法

提出了一个求解非线性互补约束均衡问题(MPCC)的逐步逼近光滑SQP算法.通过一系列光滑优化来逼近MPCC.引入l<,1>精确罚函数,线搜索保证算法具有全局收敛性.进而,在严格互补及二阶充分条件下,算法是超线性收敛的.此外,当算法有限步终止,当前迭代点即为MPEC的一个精确稳定点.     

一般互补约束问题的一种松弛逐步二次规划算法北大核心CSCD

1 引言 互补约束问题（简称MPCC）是一类具有特殊约束条件的约束最优化问题．不同于一般约束优化问题,其基本约束条件不仅包含等式约束和不等式约束,而且还包含比较复杂的互补约束．MPCC的一般形式如下：     

群零模正则化问题的等价Lipschitz优化模型

针对群零模正则化问题, 从零模函数的变分刻画入手, 将其等价地表示为带有 互补约束的数学规划问题(简称MPCC问题), 然后证明将互补约束直接罚到MPCC的目标函数而得到的罚问题是MPCC问题的全局精确罚. 此精确罚问题的目标函数不仅在可行集上全局Lipschitz连续而且还具有满意的双线性结构, 为设计群零模正则化问题的序列凸松弛算法提供了满意的等价Lipschitz优化模型.     

隐互补约束优化问题的磨光SQP算法

本文提出了一类隐互补约束优化问题的磨光SQP算法.首先,我们给出了这类优化问题的最优性和约束规范性条件.然后,在适当假设条件下,我们证明了算法具有全局收敛性.     

非凸优化带松弛步的对称ADMM局部线性收敛率分析

基于对称交替方向乘子法(ADMM),结合松弛步技巧,该文提出一种带松弛步的对称ADMM用于求解两分块线性约束非凸优化问题.同时,新算法乘子更新步采用不同的松弛因子.常规假设下,给出新算法子序列的收敛性证明.误差界条件下,分析并获得由新算法产生的迭代点列以线性收敛的速率局部趋于问题稳定点,相应增广拉格朗日函数序列亦线性收敛.最后,初步试验结果表明新算法是有效的.     

一类带概率互补约束的随机优化问题的最优性条件

主要讨论了一类带概率互补约束的随机优化问题的最优性条件.首先利用一类非线性互补(NCP)函数将概率互补约束转化成为一个通常的概率约束.然后,利用概率约束的相关理论结果,将其等价地转化成一个带不等式约束的优化问题.最后给出了这类问题的弱驻点和最优解的最优性条件.     

线性互补约束规划问题的一种Filter算法

本文研究了求解线性互补约束规划问题的算法问题.首先基于广义互补函数和摄动技术将问题转化为带参数的非线性优化问题,利用SlQP-Filter算法方法,求解线性互补约束规划问题的一种Filter算法.在适当条件下,证明了该算法的全局收敛性.     

互补约束问题的一种新松弛规划及其收敛性

在G.H.Lin与M.Fukushima思想的启发下,针对一般形式的互补约束问题,本文构造了一种新的松弛规划.通过修正和简化G.H.Lin与M.Fukushima的证明方法,在比其更弱的假设条件下获得了该松弛规划的收敛性质.     

A log-exponential smoothing method for mathematical programs with complementarity constraints

In this paper a log-exponential smoothing method for mathematical programs with complementarity constraints (MPCC) is analyzed, with some new interesting properties and convergence results provided. It is shown that the stationary points of the resulting smoothed problem converge to the strongly stationary point of MPCC, under the linear independence constraint qualification (LICQ), the weak second-order necessary condition (WSONC), and some reasonable assumption. Moreover, the limit point satisfies the weak second-order necessary condition for MPCC. A notable fact is that the proposed convergence results do not restrict the complementarity constraint functions approach to zero at the same order of magnitude.     

Superlinear Convergence of a Smooth Approximation Method for Mathematical Programs with Nonlinear Complementarity Constraints

<正>Mathematical programs with complementarity constraints(MPCC) is an important subclass of MPEC.It is a natural way to solve MPCC by constructing a suitable approximation of the primal problem.In this paper,we propose a new smoothing method for MPCC by using the aggregation technique.A new SQP algorithm for solving the MPCC problem is presented.At each iteration,the master direction is computed by solving a quadratic program,and the revised direction for avoiding the Maratos effect is generated by an explicit formula.As the non-degeneracy condition holds and the smoothing parameter tends to zero,the proposed SQP algorithm converges globally to an S-stationary point of the MPEC problem,its convergence rate is superlinear.Some preliminary numerical results are reported.     

Global Convergence of a Smooth Approximation Method for Mathematical Programs with Complementarity Constraints

A new smoothing approach was given for solving the mathematical programs with complementarity constraints (MPCC) by using the aggregation technique. As the smoothing parameter tends to zero, if the KKT point sequence generated from the smoothed problems satisfies the second-order necessary condition, then any accumulation point of the sequence is a B-stationary point of MPCC if the linear independence constraint qualification (LICQ) and the upper level strict complementarity (ULSC) condition hold at the limit point. The ULSC condition is weaker than the lower level strict complementarity (LLSC) condition generally used in the literatures. Moreover, the method can be easily extended to the mathematical programs with general vertical complementarity constraints.     

Active set algorithm for mathematical programs with linear complementarity constraints

In the paper, an incomplete active set algorithm is given for mathematical programs with linear complementarity constraints (MPLCC). At each iteration, a finite number of inner-iterations are contained for approximately solving the relaxed nonlinear optimization problem. If the feasible region of the MPLCC is bounded, under the uniform linear independence constraint qualification (LICQ), any cluster point of the sequence generated from the algorithm is a B-stationary point of the MPLCC. Preliminary numerical tests show that the algorithm is promising.     

Convergence Properties of Modified and Partially-Augmented Lagrangian Methods for Mathematical Programs with Complementarity Constraints

We present new convergence properties of partially augmented Lagrangian methods for mathematical programs with complementarity constraints (MPCC). Four modified partially augmented Lagrangian methods for MPCC based on different algorithmic strategies are proposed and analyzed. We show that the convergence of the proposed methods to a B-stationary point of MPCC can be ensured without requiring the boundedness of the multipliers.     

A Sequential Smooth Penalization Approach to Mathematical Programs with Complementarity Constraints

In this paper, a mathematical program with complementarity constraints (MPCC) is reformulated as a nonsmooth constrained mathematical program via the Fischer–Burmeister function. Smooth penalty functions are used to treat this nonsmooth constrained program. Under linear independence constraint qualification, and upper level strict complementarity condition, together with some other mild conditions, we prove that the limit point of stationary points satisfying second-order necessary conditions of unconstrained penalized problems is a strongly stationary point, hence a B-stationary point of the original MPCC. Furthermore, this limit point also satisfies a second-order necessary condition of the original MPCC. Numerical results are presented to test the performance of this method.     

A Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints

In this paper, we consider a mathematical program with complementarity constraints. We present a modified relaxed program for this problem, which involves less constraints than the relaxation scheme studied by Scholtes (2000). We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. We also consider a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is C-stationary to the original problem under the MPEC linear independence constraint qualification and, if the Hessian matrices of the Lagrangian functions of the relaxed problems are uniformly bounded below on the corresponding tangent space, it is M-stationary. We also obtain some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices mentioned above are new and can be verified easily. This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to an anonymous referee for critical comments.     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

Partial Augmented Lagrangian Method and Mathematical Programs with Complementarity Constraints

In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC). Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem. We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational performances of several methods for MPCC proposed in the literature. This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday.