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.     

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.     

Proximal Point Methods for Lipschitz Functions on Hadamard Manifolds: Scalar and Vectorial Cases

In the second part of our study, we introduce the concept of global extended exactness of penalty and augmented Lagrangian functions, and derive the localization principle in the extended form. The main idea behind the extended exactness consists in an extension of the original constrained optimization problem by adding some extra variables, and then construction of a penalty/augmented Lagrangian function for the extended problem. This approach allows one to design extended penalty/augmented Lagrangian functions having some useful properties (such as smoothness), which their counterparts for the original problem might not possess. In turn, the global exactness of such extended merit functions can be easily proved with the use of the localization principle presented in this paper, which reduces the study of global exactness to a local analysis of a merit function based on sufficient optimality conditions and constraint qualifications. We utilize the localization principle in order to obtain simple necessary and sufficient conditions for the global exactness of the extended penalty function introduced by Huyer and Neumaier, and in order to construct a globally exact continuously differentiable augmented Lagrangian function for nonlinear semidefinite programming problems.     

An improved penalty function method for solving constrained parameter optimization problems

An effective algorithm is described for solving the general constrained parameter optimization problem. The method is quasi-second-order and requires only function and gradient information. An exterior point penalty function method is used to transform the constrained problem into a sequence of unconstrained problems. The penalty weightr is chosen as a function of the pointx such that the sequence of optimization problems is computationally easy. A rank-one optimization algorithm is developed that takes advantage of the special properties of the augmented performance index. The optimization algorithm accounts for the usual difficulties associated with discontinuous second derivatives of the augmented index. Finite convergence is exhibited for a quadratic performance index with linear constraints; accelerated convergence is demonstrated for nonquadratic indices and nonlinear constraints. A computer program has been written to implement the algorithm and its performance is illustrated in fourteen test problems.     

Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs

In this paper, an approximate augmented Lagrangian function for nonlinear semidefinite programs is introduced. Some basic properties of the approximate augmented Lagrange function such as monotonicity and convexity are discussed. Necessary and sufficient conditions for approximate strong duality results are derived. Conditions for an approximate exact penalty representation in the framework of augmented Lagrangian are given. Under certain conditions, it is shown that any limit point of a sequence of stationary points of approximate augmented Lagrangian problems is a KKT point of the original semidefinite program and that a sequence of optimal solutions to augmented Lagrangian problems converges to a solution of the original semidefinite program.     

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.     

A new constraint test-case generator and the importance of hybrid optimizers

In the past decade, significant progress has been made in understanding problem complexity of discrete constraint problems. In contrast, little similar work has been done for constraint problems in the continuous domain. In this paper, we study the complexity of typical methods for non-linear constraint problems and present hybrid solvers with improved performance. To facilitate the empirical study, we propose a new test-case generator for generating non-linear constraint satisfaction problems (CSPs) and constrained optimization problems (COPs). The optimization methods tested include a sequential quadratic programming (SQP) method, a penalty method with a fixed penalty function, a penalty method with a sequence of penalty functions, and an augmented Lagrangian method. For hybrid solvers, we focus on the form that combines two or more optimization methods in sequence. In the experiments, we apply these methods to solve a series of continuous constraint problems with increasing constraint-to-variable ratios. The test problems include artificial benchmark problems from the test-case generator and problems derived from controlling a hyper-redundant modular manipulator. We obtain novel results on complexity phase transition phenomena of the various methods. Specifically, for constraint satisfaction problems, the SQP method is the best on weakly constrained problems, whereas the augmented Lagrangian method is the best on highly constrained ones. Although the static penalty method performs poorly by itself, by combining it with the SQP method, we show a hybrid solver that is significantly better than any of the individual methods on problems with moderate to large constraint-to-variable ratios. For constrained optimization problems, the hybrid solver obtains much better solutions than SQP, while spending comparable amount of time. In addition, the hybrid solver is flexible and can achieve good results on time-bounded applications by setting parameters according to the time limits.     

A geometric framework for nonconvex optimization duality using augmented lagrangian functions

We provide a unifying geometric framework for the analysis of general classes of duality schemes and penalty methods for nonconvex constrained optimization problems. We present a separation result for nonconvex sets via general concave surfaces. We use this separation result to provide necessary and sufficient conditions for establishing strong duality between geometric primal and dual problems. Using the primal function of a constrained optimization problem, we apply our results both in the analysis of duality schemes constructed using augmented Lagrangian functions, and in establishing necessary and sufficient conditions for the convergence of penalty methods.     

An augmented penalty function method with penalty parameter updates for nonconvex optimization

Given an augmented Lagrangian scheme for a general optimization problem, we use an epsilon subgradient step for improving the dual function. This can be seen as an update for an augmented penalty method, which is more stable because it does not force the penalty parameter to tend to infinity. We establish for this update primal-dual convergence for our augmented penalty method. As illustration, we apply our method to the test-bed kissing number problem.     

Augmented penalty functions for delayed control systems

A descent method is given for the numerical solution of delayed optimal control problems with fixed delays by first reducing them to nondelayed problems and then using the technique of augmented penalty functions. The system resulting from the reduction to a nondelayed problem is of higher order than the original system; however, the time is proportionally shorter, and the variational matrices are sparse.     

带等式约束的光滑优化问题的一类新的精确罚函数

罚函数方法是将约束优化问题转化为无约束优化问题的主要方法之一. 不包含目标函数和约束函数梯度信息的罚函数, 称为简单罚函数. 对传统精确罚函数而言, 如果它是简单的就一定是非光滑的; 如果它是光滑的, 就一定不是简单的. 针对等式约束优化问题, 提出一类新的简单罚函数, 该罚函数通过增加一个新的变量来控制罚项. 证明了此罚函数的光滑性和精确性, 并给出了一种解决等式约束优化问题的罚函数算法. 数值结果表明, 该算法对于求解等式约束优化问题是可行的.     

基于增广Lagrange函数的RQP方法

Recursive quadratic programming is a family of techniques developd by Bartholomew-Biggs and other authors for solving nonlinear programming problems.This paperdescribes a new method for constrained optimization which obtains its search di-rections from a quadratic programming subproblem based on the well-known aug-mented Lagrangian function.It avoids the penalty parameter to tend to infinity.We employ the Fletcher‘s exact penalty function as a merit function and the use of an approximate directional derivative of the function that avoids the need toevaluate the second order derivatives of the problem functions.We prove that thealgorithm possesses global and superlinear convergence properties.At the sametime, numerical results are reported.     

Exact augmented Lagrangian functions for nonlinear semidefinite programming

In this paper, we study augmented Lagrangian functions for nonlinear semidefinite programming (NSDP) problems with exactness properties. The term exact is used in the sense that the penalty parameter can be taken appropriately, so a single minimization of the augmented Lagrangian recovers a solution of the original problem. This leads to reformulations of NSDP problems into unconstrained nonlinear programming ones. Here, we first establish a unified framework for constructing these exact functions, generalizing Di Pillo and Lucidi’s work from 1996, that was aimed at solving nonlinear programming problems. Then, through our framework, we propose a practical augmented Lagrangian function for NSDP, proving that it is continuously differentiable and exact under the so-called nondegeneracy condition. We also present some preliminary numerical experiments.     

Optimal multigrid preconditioned semi‐monotonic augmented Lagrangians applied to the Stokes problem

We propose an optimal computational complexity algorithm for the solution of quadratic programming problems with equality constraints arising from partial differential equations. The algorithm combines a variant of the semi‐monotonic augmented Lagrangian (SMALE) method with adaptive precision control and a multigrid preconditioning for the Hessian of the cost function and for the inner product on the space of Lagrange variables. The update rule for penalty parameter acts as preconditioning of constraints. The optimality of the algorithm is theoretically proven and confirmed by numerical experiments for the two‐dimensional Stokes problem. Copyright © 2007 John Wiley & Sons, Ltd.     

A Continuation Algorithm for Max-Cut Problem

A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.     

Augmented Lagrangians with Adaptive Precision Control for Quadratic Programming with Equality Constraints

In this paper we introduce an augmented Lagrangian type algorithm for strictly convex quadratic programming problems with equality constraints. The new feature of the proposed algorithm is the adaptive precision control of the solution of auxiliary problems in the inner loop of the basic algorithm. Global convergence and boundedness of the penalty parameter are proved and an error estimate is given that does not have any term that accounts for the inexact solution of the auxiliary problems. Numerical experiments illustrate efficiency of the algorithm presented     

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

Stability and augmented Lagrangian duality in nonconvex semi-infinite programming

In this paper the pseudo-Lipschitz property of the constraint set mapping and the Lipschitz property of the optimal value function of parametric nonconvex semi-infinite optimization problems are obtained under suitable conditions on the limiting subdifferential and the limiting normal cone. Then we derive sufficient conditions for the strong duality of nonconvex semi-infinite optimality problems and a criterion for exact penalty representations via an augmented Lagrangian approach. Examples are given to illustrate the obtained results.     

A globally convergent constrained quasi-Newton method with an augmented lagrangian type penalty function

The recently proposed quasi-Newton method for constrained optimization has very attractive local convergence properties. To force global convergnce of the method, a descent method which uses Zangwill's penalty function and an exact line search has been proposed by Han. In this paper a new method which adopts a differentiable penalty function and an approximate line is presented. The proposed penalty function has the form of the augmented Lagrangian function. An algorithm for updating parameters which appear in the penalty function is described. Global convergence of the given method is proved.     

Double penalty method for bilevel optimization problems

A penalty function method approach for solving a constrained bilevel optimization problem is proposed. In the algorithm, both the upper level and the lower level problems are approximated by minimization problems of augmented objective functions. A convergence theorem is presented. The method is applicable to the non-singleton lower-level reaction set case. Constraint qualifications which imply the assumptions of the general convergence theorem are given.A part of this paper was presented in a talk at the 11th Symposium on Mathematical Programming with Data Perturbations, Washington, DC, May 1989.