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.     

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.     

On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming

In this paper, we present new convergence properties of the augmented Lagrangian method for nonlinear semidefinite programs (NSDP). Convergence to the approximately global solutions and optimal values of NSDP is first established for a basic augmented Lagrangian scheme under mild conditions, without requiring the boundedness condition of the multipliers. We then propose four modified augmented Lagrangian methods for NSDP based on different algorithmic strategies. We show that the same convergence of the proposed methods can be ensured under weaker conditions.     

Unified theory of augmented Lagrangian methods for constrained global optimization

We classify in this paper different augmented Lagrangian functions into three unified classes. Based on two unified formulations, we construct, respectively, two convergent augmented Lagrangian methods that do not require the global solvability of the Lagrangian relaxation and whose global convergence properties do not require the boundedness of the multiplier sequence and any constraint qualification. In particular, when the sequence of iteration points does not converge, we give a sufficient and necessary condition for the convergence of the objective value of the iteration points. We further derive two multiplier algorithms which require the same convergence condition and possess the same properties as the proposed convergent augmented Lagrangian methods. The existence of a global saddle point is crucial to guarantee the success of a dual search. We generalize in the second half of this paper the existence theorems for a global saddle point in the literature under the framework of the unified classes of augmented Lagrangian functions.     

Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming

We investigate in this paper global convergence properties of the augmented Lagrangian method for nonlinear semidefinite programming (NLSDP). Four modified augmented Lagrangian methods for solving NLSDP based on different algorithmic strategies are proposed. Possibly infeasible limit points of the proposed methods are characterized. It is proved that feasible limit points that satisfy the Mangasarian-Fromovitz constraint qualification are KKT points of NLSDP without requiring the boundedness condition of the multipliers. Preliminary numerical results are reported to compare the performance of the modified augmented Lagrangian methods.     

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.     

本刊英文版Vol.30(2014),No.1论文摘要

<正>Analysis on a Superlinearly Convergent Augmented Lagrangian Method Ya Xiang YUAN Abstract The augmented Lagrangian method is a classical method for solving constrained optimization.Recently,the augmented Lagrangian method attracts much attention due to its applications to sparse optimization in compressive sensing and low rank matrix optimization problems.However,most Lagrangian methods use first order information to update the Lagrange multipliers,which lead to only linear convergence.In this paper,we study an update technique     

Analysis on a superlinearly convergent augmented Lagrangian method

The augmented Lagrangian method is a classical method for solving constrained optimization.Recently,the augmented Lagrangian method attracts much attention due to its applications to sparse optimization in compressive sensing and low rank matrix optimization problems.However,most Lagrangian methods use first order information to update the Lagrange multipliers,which lead to only linear convergence.In this paper,we study an update technique based on second order information and prove that superlinear convergence can be obtained.Theoretical properties of the update formula are given and some implementation issues regarding the new update are also discussed.     

Convergence Rate of the Augmented Lagrangian SQP Method

In this paper, the augmented Lagrangian SQP method is considered for the numerical solution of optimization problems with equality constraints. The problem is formulated in a Hilbert space setting. Since the augmented Lagrangian SQP method is a type of Newton method for the nonlinear system of necessary optimality conditions, it is conceivable that q-quadratic convergence can be shown to hold locally in the pair (x, ). Our interest lies in the convergence of the variable x alone. We improve convergence estimates for the Newton multiplier update which does not satisfy the same convergence properties in x as for example the least-square multiplier update. We discuss these updates in the context of parameter identification problems. Furthermore, we extend the convergence results to inexact augmented Lagrangian methods. Numerical results for a control problem are also presented.     

Convergence of a Penalty Method for Mathematical Programming with Complementarity Constraints

We adapt the convergence analysis of the smoothing (Ref. 1) and regularization (Ref. 2) methods to a penalty framework for mathematical programs with complementarity constraints (MPCC); we show that the penalty framework shares convergence properties similar to those of these methods. Moreover, we give sufficient conditions for a sequence generated by the penalty framework to be attracted to a B-stationary point of the MPCC.     

A generalized proximal-point method for convex optimization problems in Hilbert spaces

We deal with a generalization of the proximal-point method and the closely related Tikhonov regularization method for convex optimization problems. The prime motivation behind this is the well-known connection between the classical proximal-point and augmented Lagrangian methods, and the emergence of modified augmented Lagrangian methods in recent years. Our discussion includes a formal proof of a corresponding connection between the generalized proximal-point method and the modified augmented Lagrange approach in infinite dimensions. Several examples and counterexamples illustrate the convergence properties of the generalized proximal-point method and indicate that the corresponding assumptions are sharp.     

关于结构型单调变分不等式的平行分裂增广Lagrangian方法的O(1/t)阶收敛性(英文)

最近,何[3]证明了投影收缩算法的O(1/t)阶收敛性.受此启发,本文证明了结构型单调变分不等式的平行分裂增广Lagrangian方法的O(1/t)阶收敛性.     

Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

Erratum to: An abstract model for branching and its application to mixed integer programming

Stabilized sequential quadratic programming (sSQP) methods for nonlinear optimization generate a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the local convergence analysis of an sSQP method that uses a line search with a primal-dual augmented Lagrangian merit function to enforce global convergence. The method is provably well-defined and is based on solving a strictly convex quadratic programming subproblem at each iteration. It is shown that the method has superlinear local convergence under assumptions that are no stronger than those required by conventional stabilized SQP methods. The fast local convergence is obtained by allowing a small relaxation of the optimality conditions for the quadratic programming subproblem in the neighborhood of a solution. In the limit, the line search selects the unit step length, which implies that the method does not suffer from the Maratos effect. The analysis indicates that the method has the same strong first- and second-order global convergence properties that have been established for augmented Lagrangian methods, yet is able to transition seamlessly to sSQP with fast local convergence in the neighborhood of a solution. Numerical results on some degenerate problems are reported.     

A Globally Convergent Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds

We consider the global and local convergence properties of a class of Lagrangian barrier methods for solving nonlinear programming problems. In such methods, simple bound constraints may be treated separately from more general constraints. The objective and general constraint functions are combined in a Lagrangian barrier function. A sequence of such functions are approximately minimized within the domain defined by the simple bounds. Global convergence of the sequence of generated iterates to a first-order stationary point for the original problem is established. Furthermore, possible numerical difficulties associated with barrier function methods are avoided as it is shown that a potentially troublesome penalty parameter is bounded away from zero. This paper is a companion to previous work of ours on augmented Lagrangian methods.

     

A Modified Barrier-Augmented Lagrangian Method for Constrained Minimization

We present and analyze an interior-exterior augmented Lagrangian method for solving constrained optimization problems with both inequality and equality constraints. This method, the modified barrier—augmented Lagrangian (MBAL) method, is a combination of the modified barrier and the augmented Lagrangian methods. It is based on the MBAL function, which treats inequality constraints with a modified barrier term and equalities with an augmented Lagrangian term. The MBAL method alternatively minimizes the MBAL function in the primal space and updates the Lagrange multipliers. For a large enough fixed barrier-penalty parameter the MBAL method is shown to converge Q-linearly under the standard second-order optimality conditions. Q-superlinear convergence can be achieved by increasing the barrier-penalty parameter after each Lagrange multiplier update. We consider a dual problem that is based on the MBAL function. We prove a basic duality theorem for it and show that it has several important properties that fail to hold for the dual based on the classical Lagrangian.     

Log-Sigmoid Multipliers Method in Constrained Optimization

In this paper we introduced and analyzed the Log-Sigmoid (LS) multipliers method for constrained optimization. The LS method is to the recently developed smoothing technique as augmented Lagrangian to the penalty method or modified barrier to classical barrier methods. At the same time the LS method has some specific properties, which make it substantially different from other nonquadratic augmented Lagrangian techniques.We established convergence of the LS type penalty method under very mild assumptions on the input data and estimated the rate of convergence of the LS multipliers method under the standard second order optimality condition for both exact and nonexact minimization.Some important properties of the dual function and the dual problem, which are based on the LS Lagrangian, were discovered and the primal–dual LS method was introduced.     

广义乘子交替方向法求解线性约束不可分非凸优化问题的收敛性

In this paper, we consider the convergence of the generalized alternating direction method of multipliers(GADMM) for solving linearly constrained nonconvex minimization model whose objective contains coupled functions. Under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality, we prove that the sequence generated by the GADMM converges to a critical point of the augmented Lagrangian function when the penalty parameter in the augmented Lagrangian function is sufficiently large. Moreover, we also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.     

Using a factored dual in augmented Lagrangian methods for semidefinite programming

In the context of augmented Lagrangian approaches for solving semidefinite programming problems, we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. Hints on how to deal with the resulting unconstrained maximization of the augmented Lagrangian are given. We further use the approximate maximum of the augmented Lagrangian with the aim of improving the convergence rate of alternating direction augmented Lagrangian frameworks. Numerical results are reported, showing the benefits of the approach.     

无限多类别网络均衡问题中的收费计算

对于一个多类别的网络均衡问题,可以通过计算某个辅助问题的容量限制约束相应的乘子向量得到有效收费.本文通过计算拉格朗日函数的鞍点来计算乘子向量.借助于广义拉格朗日函数的稳定性和Uzawa算法非精确解的收敛性,得到鞍点序列的收敛性.其中离散化方法用于最小化广义拉格朗日函数的计算.