Updating the Multipliers Associated with Inequality Constraints in an Augmented Lagrangian Multiplier Method

This paper contributes to the development of the field of augmented Lagrangian multiplier methods for general nonlinear programming by introducing a new update for the multipliers corresponding to inequality constraints. The update maintains naturally the nonnegativity of the multipliers without the need for a positive-orthant projection, as a result of the verification of the first-order necessary conditions for the minimization of a modified augmented Lagrangian penalty function.In the new multiplier method, the roles of the multipliers are interchanged: the multipliers corresponding to the inequality constraints are updated explicitly, whereas the multipliers corresponding to the equality constraints are approximated implicitly. It is shown that the basic properties of local convergence of the traditional multiplier method are valid also for the proposed method.     

Augmented Lagrangians which are quadratic in the multiplier

We present a class of new augmented Lagrangian functions with the essential property that each member is concave quadratic when viewed as a function of the multiplier. This leads to an improved duality theory and to a related class of exact penalty functions. In addition, a relationship between Newton steps for the classical Lagrangian and the new Lagrangians is established.This work was supported in part by ARO Grant No. DAAG29-77-G-0125.     

The role of the multipliers in the multiplier method

The paper studies the role of the multipliers when the multiplier method is applied as a computational technique for minimizing penalized cost functionals for optimal control problems characterized by linear systems and integral quadratic costs.Theauthor would like to gratefully thank two anonymous referees for many helpful suggestions which led to a major improvement in both the quality and clarity of the paper, and to Professor Angelo Miele for his encouragement.     

A note on the method of multipliers

Implementation of the penalty function method for constrained optimization poses numerical difficulties as the penalty parameter increases. To offset this problem, one often resorts to Newton's method. In this note, working in the context of the penalty function method, we establish an intimate connection between the second-order updating formulas which result from Newton's method on the primal problem and Newton's method on the dual problem.The author wishes to thank Professor R. A. Tapia for his careful review of this note. He has contributed significantly to its content through several crucial observations.     

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.     

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.     

On the twice differentiable cubic augmented Lagrangian

Rockafellar's quadratic augmented Lagrangian for inequality constrained minimization is not twice differentiable. To eliminate this drawback, several quite complicated Lagrangians have been proposed. We exhibit a simple cubic Lagrangian that is twice differentiable. It stems from the recent work of Eckstein and Teboulle on Bregmanrelated Lagrangians.This research was supported by the State Committee for Scientific Research under Grant 8S50502206.     

Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function

An algorithm for nonlinear programming problems with equality constraints is presented which is globally and superlinearly convergent. The algorithm employs a recursive quadratic programming scheme to obtain a search direction and uses a differentiable exact augmented Lagrangian as line search function to determine the steplength along this direction. It incorporates an automatic adjustment rule for the selection of the penalty parameter and avoids the need to evaluate second-order derivatives of the problem functions. Some numerical results are reported.     

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).     

Properties of the Augmented Lagrangian in Nonlinear Semidefinite Optimization

We study the properties of the augmented Lagrangian function for nonlinear semidefinite programming. It is shown that, under a set of sufficient conditions, the augmented Lagrangian algorithm is locally convergent when the penalty parameter is larger than a certain threshold. An error estimate of the solution, depending on the penalty parameter, is also established.The first author was partially supported by Singapore-MIT Alliance and by the National University of Singapore under Grants RP314000-028/042/057-112. The second author was partially supported by the Funds of the Ministry of Education of China for PhD Units under Grant 20020141013 and the National Natural Science Foundation of China under Grant 10471015.     

On the convergence rate for a penalty function method of exponential type

Recently, Kort and Bertsekas (Ref. 1) and Hartman (Ref. 2) presented independently a new penalty function algorithm of exponential type for solving inequality-constrained minimization problems. The main purpose of this work is to give a proof on the rate of convergence of a modification of the exponential penalty method proposed by these authors. We show that the sequence of points generated by the modified algorithm converges to the solution of the original nonconvex problem linearly and that the sequence of estimates of the optimal Lagrange multiplier converges to this multiplier superlinearly. The question of convergence of the modified method is discussed. The present paper hinges on ideas of Mangasarian (Ref. 3), but the case considered here is not covered by Mangasarian's theory.     

On the existence and nonexistence of Lagrange multipliers in Banach spaces

The paper deals with the existence of Lagrange multipliers for a general nonlinear programming problem. Some regularity conditions are formulated which are, in a sense, the weakest to assure the existence of multipliers. A number of related conditions are discussed. The connection between the choice of suitable function spaces and the existence of multipliers is analyzed.This work was partly supported by the National Science Foundation, Grant No. GF-37298, to the Institute of Automatic Control, Technical University of Warsaw, Warsaw, Poland, and the Department of Computer and Control Sciences, University of Minnesota, Minneapolis, Minnesota.The author wishes to thank Professor A. P. Wierzbicki for many important remarks concerning the subject of this paper.     

Use of Augmented Lagrangian Methods for the Optimal Control of Obstacle Problems

We investigate optimal control problems governed by variational inequalities involving constraints on the control, and more precisely the example of the obstacle problem. In this paper, we discuss some augmented Lagrangian algorithms to compute the solution.     

Computable numerical bounds for lagrange multipliers of stationary points of non-convex differentiable non-linear programs

It is shown that the satisfaction of a standard constraint qualification of mathematical programming [5] at a stationary point of a non-convex differentiable non-linear program provides explicit numerical bounds for the set of all Lagrange multipliers associated with the stationary point. Solution of a single linear program gives a sharper bound together with an achievable bound on the 1-norm of the multipliers associated with the inequality constraints. The simplicity of obtaining these bounds contrasts sharply with the intractable NP-complete problem of computing an achievable upper bound on the p-norm of the multipliers associated with the equality constraints for integer $\text{p ≧ 1}$.     

Characterizations of solution sets of mathematical programs in terms of Lagrange multipliers

The main aim of this article is to obtain characterizations of the solution set of two non-linear programs in terms of Lagrange multipliers. Both the programs have pseudolinear constraints but the objective function is convex for the first program and pseudolinear for the second program, where all the functions are defined in terms of bifunctions.     

A heuristic algorithm for nonlinear programming

In this paper, a heuristic algorithm for nonlinear programming is presented. The algorithm uses two search directions, and the Hessian of the Lagrangian function is approximated with the BFGS secant update. We show that the sequence of iterates convergeq-superlinearly if the sequence of approximating matrices satisfies a particular condition. Numerical results are presented.     

On the convergence of quasi-newton methods for nonsmooth problems

We develop a theory of quasi-New ton and least-change update methods for solving systems of nonlinear equations F(x) = 0. In this theory, no differentiability conditions are necessary. Instead, we assume that Fcan be approximated, in a weak sense, by an affine function in a neighborhood of a solution. Using this assumption, we prove local and ideal convergence. Our theory can be applied to B-differentiable functions and to partially differentiable functions.     

The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming

We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and the strong second order sufficient condition, the rate of convergence is linear and the ratio constant is proportional to 1/c, where c is the penalty parameter that exceeds a threshold . The research of Defeng Sun is partly supported by the Academic Research Fund from the National University of Singapore. The research of Jie Sun and Liwei Zhang is partly supported by Singapore–MIT Alliance and by Grants RP314000-042/057-112 of the National University of Singapore. The research of Liwei Zhang is also supported by the National Natural Science Foundation of China under project grant no. 10471015 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, China.     

k-均值问题的差分隐私算法综述

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息,同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。     

A Class of penalty functions for optimization problema with bound constraints

In this paper we propose a new class of continuously differentiable globally exact penalty functions for the solution of minimization problems with simple bounds on some (all) of the variables. The penalty functions in this class fully exploit the structure of the problem and are easily computable. Furthermore we introduce a simple updating rule for the penalty parameter that can be used in conjunction with unconstrained minimization techniques to solve the original problem.