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.     

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

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

带新NCP函数的Lagrangian乘子方法

在经营管理、工程设计、科学研究、军事指挥等方面普遍存在着最优化问题,而实际问题中出现的绝大多数问题都被归纳为非线性规划问题之中。作为带等式、不等式约束的复杂事例,最优化问题的求解向来较为繁琐、困难。适当条件下,非线性互补函数(NCP)可以与约束优化问题相结合,其中NCP函数的无约束极小解对应原约束问题的解及其乘子。本文提出了一类新的NCP函数用于解决等式和不等式约束非线性规划问题,结合新的NCP函数构造了增广Lagrangian函数。在适当假设条件下,证明了增广Lagrangian函数与原问题的解之间的一一对应关系。同时构造了相应算法,并证明了该算法的收敛性和有效性。     

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.     

Alternating direction augmented Lagrangian methods for semidefinite programming

We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixed-point argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our algorithms are robust and very efficient due to their ability or exploit special structures, such as sparsity and constraint orthogonality in these problems.     

A nonlinear augmented Lagrangian for constrained minimax problems

A novel smooth nonlinear augmented Lagrangian for solving minimax problems with inequality constraints, is proposed in this paper, which has the positive properties that the classical Lagrangian and the penalty function fail to possess. The corresponding algorithm mainly consists of minimizing the nonlinear augmented Lagrangian function and updating the Lagrange multipliers and controlling parameter. It is demonstrated that the algorithm converges Q-superlinearly when the controlling parameter is less than a threshold under the mild conditions. Furthermore, the condition number of the Hessian of the nonlinear augmented Lagrangian function is studied, which is very important for the efficiency of the algorithm. The theoretical results are validated further by the preliminary numerical experiments for several testing problems reported at last, which show that the nonlinear augmented Lagrangian is promising.     

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.     

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

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

乘子方法中的参数选择

Di Pillo和Grippo提出的含参数C〉0的增广Lagrangian函数中，使用了最大函数，该函数可能在无穷多个点处不可微．为了克服这个问题，濮定国在2004年提出了一类带新的NCP函数的乘子法．该方法在增广Lagrangian函数和原问题之间存在很好的等价性；同时该方法具有全局收敛性，且在适当假设下，具有超线性收敛率．但是在该方法中，要求参数C充分大．为了实现算法及提高算法效率，本文给出了一个有效选择参数C的方法．     

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

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

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.     

Lagrange Multiplier Conditions Characterizing the Optimal Solution Sets of Cone-Constrained Convex Programs

Various characterizations of optimal solution sets of cone-constrained convex optimization problems are given. The results are expressed in terms of subgradients and Lagrange multipliers. We establish first that the Lagrangian function of a convex program is constant on the optimal solution set. This elementary property is then used to derive various simple Lagrange multiplier-based characterizations of the solution set. For a finite-dimensional convex program with inequality constraints, the characterizations illustrate that the active constraints with positive Lagrange multipliers at an optimal solution remain active at all optimal solutions of the program. The results are applied to derive corresponding Lagrange multiplier characterizations of the solution sets of semidefinite programs and fractional programs. Specific examples are given to illustrate the nature of the results.     

Two-level primal-dual decomposition technique for large-scale nonconvex optimization problems with constraints

A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented.     

本刊英文版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     

New results on a class of exact augmented Lagrangians

In this paper, a new continuously differentiable exact augmented Lagrangian is introduced for the solution of nonlinear programming problems with compact feasible set. The distinguishing features of this augmented Lagrangian are that it is radially unbounded with respect to the multiplier and that it goes to infinity on the boundary of a compact set containing the feasible region. This allows one to establish a complete equivalence between the unconstrained minimization of the augmented Lagrangian on the product space of problem variables and multipliers and the solution of the constrained problem.The author wishes to thank Dr. L. Grippo for having suggested the topic of this paper and for helpful discussions.     

An Exact Augmented Lagrangian Function for Nonlinear Programming with Two-Sided Constraints

This paper is aimed toward the definition of a new exact augmented Lagrangian function for two-sided inequality constrained problems. The distinguishing feature of this augmented Lagrangian function is that it employs only one multiplier for each two-sided constraint. We prove that stationary points, local minimizers and global minimizers of the exact augmented Lagrangian function correspond exactly to KKT pairs, local solutions and global solutions of the constrained problem.     

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.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).     

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.