求解互补约束优化问题的乘子松弛法

利用互补问题的Lagrange函数, 给出了互补约束优化问题\,(MPCC)\,的一种新松弛问题. 在较弱的条件下, 新松弛问题满足线性独立约束规范. 在此基础上, 提出了求解互补约束优化问题的乘子松弛法. 在MPCC-LICQ条件下, 松弛问题稳定点的任何聚点都是MPCC的M-稳定点. 无需二阶必要条件, 只在ULSC条件下, 就可保证聚点是MPCC的B-稳定点. 另外, 给出了算法收敛于B-稳定点的新条件.     

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

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

随机二阶锥二次规划逆问题的SAA方法

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。     

随机二阶锥二次规划逆问题的SAA方法

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。     

非线性规划问题的精确增广Lagrange函数

对于一般的非线性规划给出一种精确增广Lagrange函数,并讨论其性质.无需假设严格互补条件成立,给出了原问题的局部极小点与增广Lagrange函数在原问题的变量空间上的局部极小的关系.进一步,在适当的假设条件下,建立了两者的全局最优解之间的关系.     

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

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

一类非凸优化问题广义交替方向法的收敛性

考虑利用广义交替方向法(GADMM)求解线性约束两个函数和的最小值问题,其中一个函数为凸函数,另一个函数可以表示为两个凸函数的差.对GADMM的每一个子问题,采用两个凸函数之差算法中的线性化技术来处理.通过假定相应函数满足Kurdyka-Lojasiewicz不等式,当增广Lagrange(拉格朗日)函数的罚参数充分大时,证明了GADMM所产生的迭代序列收敛到增广Lagrange函数的稳定点.最后,给出了该算法的收敛速度分析.     

基于全牛顿求解P*(κ)阵水平线性互补问题的内点算法

提出一种求解P_*(k)阵水平线性互补问题的全牛顿内点算法,全牛顿算法的优势在于每次迭代中不需要线性搜寻.当给定适当的中心路径邻域的阈值和更新势垒参数,证明算法中心邻域的全牛顿是局部二次收敛的,最后给出算法迭代复杂性O(√n)log(n+1+k)/εμ₀.     

非线性优化修正Frisch函数方法的乘子映射

对于同时含有等式与不等式约束的非线性优化问题的修正Frisch函数方法,给出其乘子映射和解映射的导数的估计.将得到的估计用于建立修正Frisch函数方法的线性收敛速率.在线性无关的约束规范,严格互补条件和二阶充分性条件成立的前提下,证得该收敛率与1/c成正比.本文的收敛性分析依赖于矩阵的奇异值分解,其方法可以用来分析其他的修正Lagrange方法.     

一个解不等式约束优化问题的初始点任意而不需罚函数的SQP算法(英文)

本文构造了一解不等式约束优化问题的非单调SQP方法 ,与类似的算法比较 ,它有以下特点 :( 1 )初始点任意 ,并不用罚函数 ;( 2 )有限步后必产生可行点 ;( 3)在每次迭代 ,只需解一个二次规划子问题 ;( 4)不需要严格互补条件 ,在较弱的条件下 ,算法超线性收敛 .     

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.     

Dynamic Slope Scaling Procedure and Lagrangian Relaxation with Subproblem Approximation

The dynamic slope scaling procedure (DSSP) is an efficient heuristic algorithm that provides good solutions to the fixed-charge transportation or network flow problem. However, the procedure is graphically motivated and appears unrelated to other optimization techniques. In this paper, we formulate the fixed-charge problem as a mathematical program with complementarity constraints (MPCC) and show that DSSP is equivalent to solving MPCC using Lagrangian relaxation with subproblem approximation.     

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.     

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.     

A new smoothing scheme for mathematical programs with complementarity constraints

In this paper, we consider a mathematical program with complementarity constraints (MPCC). We present a new smoothing scheme for this problem, which makes the primal structure of the complementarity part unchanged mostly. For the new smoothing problem, we show that the linear independence constraint qualification (LICQ) holds under some conditions. We also analyze the convergence behavior of the smoothing problem, and get some sufficient conditions such that an accumulation point of stationary points of the smoothing problems is C (M, B)-stationarity respectively. Based on the smoothing problem, we establish an algorithm to solve the primal MPCC problem. Some numerical experiments are given in the paper.     

A Smoothing Method for Zero–One Constrained Extremum Problems

In this paper, the zero–one constrained extremum problem is reformulated as an equivalent smooth mathematical program with complementarity constraints (MPCC), and then as a smooth ordinary nonlinear programming problem with the help of the Fischer–Burmeister function. The augmented Lagrangian method is adopted to solve the resulting problem, during which the non-smoothness may be introduced as a consequence of the possible inequality constraints. This paper incorporates the aggregate constraint method to construct a uniform smooth approximation to the original constraint set, with approximation controlled by only one parameter. Convergence results are established, showing that under reasonable conditions the limit point of the sequence of stationary points generated by the algorithm is a strongly stationary point of the original problem and satisfies the second order necessary conditions of the original problem. Unlike other penalty type methods for MPCC, the proposed algorithm can guarantee that the limit point of the sequence is feasible to the original problem.     

Hybrid Approach with Active Set Identification for Mathematical Programs with Complementarity Constraints

We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs. We apply an active set identification technique to a smoothing continuation method (Ref. 1) and propose a hybrid algorithm for solving MPCC. We develop also two modifications: one makes use of an index addition strategy; the other adopts an index subtraction strategy. We show that, under reasonable assumptions, all the proposed algorithms possess a finite termination property. Further discussions and numerical experience are given as well 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 Professor Paul Tseng for helpful suggestions on an earlier version of the paper.     

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.     

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

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