Augmented Lagrangian functions for constrained optimization problems

In this paper, in order to obtain some existence results about solutions of the augmented Lagrangian problem for a constrained problem in which the objective function and constraint functions are noncoercive, we construct a new augmented Lagrangian function by using an auxiliary function. We establish a zero duality gap result and a sufficient condition of an exact penalization representation for the constrained problem without the coercive or level-bounded assumption on the objective function and constraint functions. By assuming that the sequence of multipliers is bounded, we obtain the existence of a global minimum and an asymptotically minimizing sequence for the constrained optimization 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     

对等式约束非线性规划问题的Hestenes-Powell增广拉格朗日函数的进一步研究

本文对用无约束极小化方法求解等式约束非线性规划问题的Hestenes-Powell 增广拉格朗日函数作了进一步研究．在适当的条件下,我们建立了Hestenes-Powell增广拉格朗日函数在原问题变量空间上的无约束极小与原约束问题的解之间的关系,并且也给出了Hestenes-Powell增广拉格朗日函数在原问题变量和乘子变量的积空间上的无约束极小与原约束问题的解之间的一个关系．因此,从理论的观点来看,原约束问题的解和对应的拉格朗日乘子值不仅可以用众所周知的乘子法求得,而且可以通过对Hestenes-Powell 增广拉格朗日函数在原问题变量和乘子变量的积空间上执行一个单一的无约束极小化来获得．     

带有不等式约束的非线性规划问题的一个精确增广Lagrange函数

对求解带有不等式约束的非线性非凸规划问题的一个精确增广Lagrange函数进行了研究．在适当的假设下,给出了原约束问题的局部极小点与增广Lagrange函数,在原问题变量空间上的无约束局部极小点之间的对应关系．进一步地,在对全局解的一定假设下,还提供了原约束问题的全局最优解与增广Lagrange函数,在原问题变量空间的一个紧子集上的全局最优解之间的一些对应关系．因此,从理论上讲,采用该文给出的增广Lagrange函数作为辅助函数的乘子法,可以求得不等式约束非线性规划问题的最优解和对应的Lagrange乘子．     

Perturbation Lemma for the Newton Method with Application to the SQP Newton Method

We study the convergence of a general perturbation of the Newton method for solving a nonlinear system of equations. As an application, we show that the augmented Lagrangian successive quadratic programming is locally and q-quadratically convergent in the variable x to the solution of an equality constrained optimization problem, under a mild condition on the penalty parameter and the choice of the Lagrange multipliers.     

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.     

A Unified Approach to the Global Exactness of Penalty and Augmented Lagrangian Functions I: Parametric Exactness

In this two-part study, we develop a unified approach to the analysis of the global exactness of various penalty and augmented Lagrangian functions for constrained optimization problems in finite-dimensional spaces. This approach allows one to verify in a simple and straightforward manner whether a given penalty/augmented Lagrangian function is exact, i.e., whether the problem of unconstrained minimization of this function is equivalent (in some sense) to the original constrained problem, provided the penalty parameter is sufficiently large. Our approach is based on the so-called localization principle that reduces the study of global exactness to a local analysis of a chosen merit function near globally optimal solutions. In turn, such local analysis can be performed with the use of optimality conditions and constraint qualifications. In the first paper, we introduce the concept of global parametric exactness and derive the localization principle in the parametric form. With the use of this version of the localization principle, we recover existing simple, necessary, and sufficient conditions for the global exactness of linear penalty functions and for the existence of augmented Lagrange multipliers of Rockafellar–Wets’ augmented Lagrangian. We also present completely new necessary and sufficient conditions for the global exactness of general nonlinear penalty functions and for the global exactness of a continuously differentiable penalty function for nonlinear second-order cone programming problems. We briefly discuss how one can construct a continuously differentiable exact penalty function for nonlinear semidefinite programming problems as well.     

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.     

Further Study on Augmented Lagrangian Duality Theory

In this paper, we present a necessary and sufficient condition for a zero duality gap between a primal optimization problem and its generalized augmented Lagrangian dual problems. The condition is mainly expressed in the form of the lower semicontinuity of a perturbation function at the origin. For a constrained optimization problem, a general equivalence is established for zero duality gap properties defined by a general nonlinear Lagrangian dual problem and a generalized augmented Lagrangian dual problem, respectively. For a constrained optimization problem with both equality and inequality constraints, we prove that first-order and second-order necessary optimality conditions of the augmented Lagrangian problems with a convex quadratic augmenting function converge to that of the original constrained program. For a mathematical program with only equality constraints, we show that the second-order necessary conditions of general augmented Lagrangian problems with a convex augmenting function converge to that of the original constrained program.This research is supported by the Research Grants Council of Hong Kong (PolyU B-Q359.)     

Existence of Augmented Lagrange Multipliers for Semi-infinite Programming Problems

Using an augmented Lagrangian approach, we study the existence of augmented Lagrange multipliers of a semi-infinite programming problem and discuss their characterizations in terms of saddle points. In the case of a sharp Lagrangian, we obtain a first-order necessary condition for the existence of an augmented Lagrange multiplier for the semi-infinite programming problem and some first-order sufficient conditions by assuming inf-compactness of the data functions and the extended Mangasarian–Fromovitz constraint qualification. Using a valley at 0 augmenting function and assuming suitable second-order sufficient conditions, we obtain the existence of an augmented Lagrange multiplier for the semi-infinite programming problem.     

On the convergence properties of modified augmented Lagrangian methods for mathematical programming with complementarity constraints

In this paper, we present new convergence results of augmented Lagrangian methods for mathematical programs with complementarity constraints (MPCC). Modified augmented Lagrangian methods based on four different algorithmic strategies are considered for the constrained nonconvex optimization reformulation of MPCC. We show that the convergence to a global optimal solution of the problem can be ensured without requiring the boundedness condition of the multipliers.     

Parallel Uzawa Method for Large-Scale Minimization of Partially Separable Functions

A parallel Uzawa-type algorithm, for solving unconstrained minimization of large-scale partially separable functions, is presented. Using auxiliary unknowns, the unconstrained minimization problem is transformed into a (linearly) constrained minimization of a separable function.The augmented Lagrangian of this problem decomposes into a sum of partially separable augmented Lagrangian functions. To take advantage of this property, a Uzawa block relaxation is applied. In every iteration, unconstrained minimization subproblems are solved in parallel before updating Lagrange multipliers. Numerical experiments show that the speed-up factor gained using our algorithm is significant.     

A nonlinear Lagrangian for constrained optimization problems

A novel nonlinear Lagrangian is presented for constrained optimization problems with both inequality and equality constraints, which is nonlinear with respect to both functions in problem and Lagrange multipliers. The nonlinear Lagrangian inherits the smoothness of the objective and constraint functions and has positive properties. The algorithm on the nonlinear Lagrangian is demonstrated to possess local and linear convergence when the penalty parameter is less than a threshold (the penalty parameter in the penalty method has to approximate zero) under a set of suitable conditions, and be super-linearly convergent when the penalty parameter is decreased following Lagrange multiplier update. Furthermore, the dual problem based on the nonlinear Lagrangian is discussed and some important properties are proposed, which fail to hold for the dual problem based on the classical Lagrangian. At last, the preliminary and comparing numerical results for several typical test problems by using the new nonlinear Lagrangian algorithm and the other two related nonlinear Lagrangian algorithms, are reported, which show that the given nonlinear Lagrangian is promising.     

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.     

Augmented Lagrangian method for distributed optimal control problems with state constraints

We consider state-constrained optimal control problems governed by elliptic equations. Doing Slater-like assumptions, we know that Lagrange multipliers exist for such problems, and we propose a decoupled augmented Lagrangian method. We present the algorithm with a simple example of a distributed control problem.     

On a characterization of convergence for the Hestenes method of multipliers

The connection between the convergence of the Hestenes method of multipliers and the existence of augmented Lagrange multipliers for the constrained minimum problem (P): minimizef(x), subject tog(x)=0, is investigated under very general assumptions onX,f, andg.In the first part, we use the existence of augmented Lagrange multipliers as a sufficient condition for the convergence of the algorithm. In the second part, we prove that this is also a necessary condition for the convergence of the method and the boundedness of the sequence of the multiplier estimates.Further, we give very simple examples to show that the existence of augmented Lagrange multipliers is independent of smoothness condition onf andg. Finally, an application to the linear-convex problem is given.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

Existence of augmented Lagrange multipliers: reduction to exact penalty functions and localization principle

Mathematical Programming - In this article, we present new general results on existence of augmented Lagrange multipliers. We define a penalty function associated with an augmented Lagrangian, and...     

Convergence of an augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraints

An augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraints is proposed based on a Löwner operator associated with a potential function for the optimization problems with inequality constraints. The favorable properties of both the Löwner operator and the corresponding augmented Lagrangian are discussed. And under some mild assumptions, the rate of convergence of the augmented Lagrange algorithm is studied in detail.     

A complete characterization of strong duality in nonconvex optimization with a single constraint

We first establish sufficient conditions ensuring strong duality for cone constrained nonconvex optimization problems under a generalized Slater-type condition. Such conditions allow us to cover situations where recent results cannot be applied. Afterwards, we provide a new complete characterization of strong duality for a problem with a single constraint: showing, in particular, that strong duality still holds without the standard Slater condition. This yields Lagrange multipliers characterizations of global optimality in case of (not necessarily convex) quadratic homogeneous functions after applying a generalized joint-range convexity result. Furthermore, a result which reduces a constrained minimization problem into one with a single constraint under generalized convexity assumptions, is also presented.