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.     

Stabilized Sequential Quadratic Programming

Recently, Wright proposed a stabilized sequential quadratic programming algorithm for inequality constrained optimization. Assuming the Mangasarian-Fromovitz constraint qualification and the existence of a strictly positive multiplier (but possibly dependent constraint gradients), he proved a local quadratic convergence result. In this paper, we establish quadratic convergence in cases where both strict complementarity and the Mangasarian-Fromovitz constraint qualification do not hold. The constraints on the stabilization parameter are relaxed, and linear convergence is demonstrated when the parameter is kept fixed. We show that the analysis of this method can be carried out using recent results for the stability of variational problems.     

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

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

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

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

Inexact Josephy–Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization

We propose and analyze a perturbed version of the classical Josephy–Newton method for solving generalized equations. This perturbed framework is convenient to treat in a unified way standard sequential quadratic programming, its stabilized version, sequential quadratically constrained quadratic programming, and linearly constrained Lagrangian methods. For the linearly constrained Lagrangian methods, in particular, we obtain superlinear convergence under the second-order sufficient optimality condition and the strict Mangasarian–Fromovitz constraint qualification, while previous results in the literature assume (in addition to second-order sufficiency) the stronger linear independence constraint qualification as well as the strict complementarity condition. For the sequential quadratically constrained quadratic programming methods, we prove primal-dual superlinear/quadratic convergence under the same assumptions as above, which also gives a new result.     

A Robust SQP Method for Mathematical Programs with Linear Complementarity Constraints

The relationship between the mathematical program with linear complementarity constraints (MPLCC) and its inequality relaxation is studied. Based on this relationship, a new sequential quadratic programming (SQP) method is presented for solving the MPLCC. A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global convergence results are derived without assuming the linear independence constraint qualification for MPEC, the nondegeneracy condition, and any feasibility condition of the quadratic programming subproblems. Preliminary numerical results are reported. Research is partially supported by Singapore-MIT Alliance and School of Business, National University of Singapore.     

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.     

A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS

In this paper, we propose a feasible QP-free method for solving nonlinear inequality constrained optimization problems. A new working set is proposed to estimate the active set. Specially, to determine the working set, the new method makes use of the multiplier information from the previous iteration, eliminating the need to compute a multiplier function. At each iteration, two or three reduced symmetric systems of linear equations with a common coefficient matrix involving only constraints in the working set are solved, and when the iterate is sufficiently close to a KKT point, only two of them are involved. Moreover, the new algorithm is proved to be globally convergent to a KKT point under mild conditions. Without assuming the strict complementarity, the convergence rate is superlinear under a condition weaker than the strong second-order sufficiency condition. Numerical experiments illustrate the efficiency of the algorithm.     

Local Convergence of a Primal-Dual Method for Degenerate Nonlinear Programming

In recent work, the local convergence behavior of path-following interior-point methods and sequential quadratic programming methods for nonlinear programming has been investigated for the case in which the assumption of linear independence of the active constraint gradients at the solution is replaced by the weaker Mangasarian–Fromovitz constraint qualification. In this paper, we describe a stabilization of the primal-dual interior-point approach that ensures rapid local convergence under these conditions without enforcing the usual centrality condition associated with path-following methods. The stabilization takes the form of perturbations to the coefficient matrix in the step equations that vanish as the iterates converge to the solution.     

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.     

Stabilized SQP revisited

The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve superlinear convergence in situations when the Lagrange multipliers associated to a solution are not unique. Within the framework of Fischer (Math Program 94:91–124, 2002), the key to local superlinear convergence of sSQP are the following two properties: upper Lipschitzian behavior of solutions of the Karush-Kuhn-Tucker (KKT) system under canonical perturbations and local solvability of sSQP subproblems with the associated primal-dual step being of the order of the distance from the current iterate to the solution set of the unperturbed KKT system. According to Fernández and Solodov (Math Program 125:47–73, 2010), both of these properties are ensured by the second-order sufficient optimality condition (SOSC) without any constraint qualification assumptions. In this paper, we state precise relationships between the upper Lipschitzian property of solutions of KKT systems, error bounds for KKT systems, the notion of critical Lagrange multipliers (a subclass of multipliers that violate SOSC in a very special way), the second-order necessary condition for optimality, and solvability of sSQP subproblems. Moreover, for the problem with equality constraints only, we prove superlinear convergence of sSQP under the assumption that the dual starting point is close to a noncritical multiplier. Since noncritical multipliers include all those satisfying SOSC but are not limited to them, we believe this gives the first superlinear convergence result for any Newtonian method for constrained optimization under assumptions that do not include any constraint qualifications and are weaker than SOSC. In the general case when inequality constraints are present, we show that such a relaxation of assumptions is not possible. We also consider applying sSQP to the problem where inequality constraints are reformulated into equalities using slack variables, and discuss the assumptions needed for convergence in this approach. We conclude with consequences for local regularization methods proposed in (Izmailov and Solodov SIAM J Optim 16:210–228, 2004; Wright SIAM J. Optim. 15:673–676, 2005). In particular, we show that these methods are still locally superlinearly convergent under the noncritical multiplier assumption, weaker than SOSC employed originally.     

General primal-dual penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods are considered, that define a local continuously differentiable primal-dual path. The class of penalty/barrier terms includes most of the usual techniques like logarithmic barriers, SUMT, quadratic loss functions as well as exponential penalties, and the optimization problem which may contain inequality as well as equality constraints. The convergence of the corresponding general primal-dual path-following method is shown for local minima that satisfy strong second-order sufficiency conditions with linear independence constraint qualification (LICQ) and strict complementarity. A basic tool in the analysis of these methods is to estimate the radius of convergence of Newton's method depending on the penalty/barrier-parameter. Without using self-concordance properties convergence bounds are derived by direct estimations of the solutions of the Newton equations. Parameter selection rules are proposed which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints

Generalized stationary points of the mathematical program with equilibrium constraints (MPEC) are studied to better describe the limit points produced by interior point methods for MPEC. A primal-dual interior-point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced under fairly general conditions other than strict complementarity or the linear independence constraint qualification for MPEC (MPEC-LICQ). It is shown that every limit point of the generated sequence is a strong stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a point with certain stationarity can be obtained. Preliminary numerical results are reported, which include a case analyzed by Leyffer for which the penalty interior-point algorithm failed to find a stationary point.Mathematics Subject Classification (1991):90C30, 90C33, 90C55, 49M37, 65K10     

On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

A Class of Quadratic Programs with Linear Complementarity Constraints

We consider a class of quadratic programs with linear complementarity constraints (QPLCC) which belong to mathematical programs with equilibrium constraints (MPEC). We investigate various stationary conditions and present new and strong necessary and sufficient conditions for global and local optimality. Furthermore, we propose a Newton-like method to find an M-stationary point in finite steps without MEPC linear independence constraint qualification. The research of this author is partially supported by NSERC, and Research Grand Council of Hong Kong.     

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 method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

Quadratic convergence of a smoothing Newton method for symmetric cone programming without strict complementarity

This paper deals with symmetric cone programming (SCP), which includes the linear programming (LP), the second-order cone programming (SOCP), the semidefinite programming (SDP) as special cases. Based on the Chen?CMangasarian smoothing function of the projection operator onto symmetric cones, we establish a smoothing Newton method for SCP. Global and quadratic convergence of the proposed algorithm is established under the primal and dual constraint nondegeneracies, but without the strict complementarity. Moreover, we show the equivalence at a Karush?CKuhn?CTucker (KKT) point among the primal and dual constraint nondegeneracies, the nonsingularity of the B-subdifferential of the smoothing counterpart of the KKT system, and the nonsingularity of the corresponding Clarke??s generalized Jacobian.     

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

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