Search

We introduce exponential augmented Lagrangian methods for solving equilibrium problems in finite-dimensional spaces, extending the so-called quadratic augmented Lagrangian methods. Unlike the quadratic augmented Lagrangian methods that are at most first-order differentiable, our exponential augmented Lagrangian methods can be differentiable at any order. Therefore, second-order methods, such as Newton's methods, can be used to solve the subproblems generated by the augmented Lagrangian methods. We also present numerical results obtained based on implementing our proposed algorithms in Matlab. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing a smooth nonconvex function over a structured convex feasible set, that is, defined by two sets of constraints that are easy to treat when considered separately. In order to exploit the structure of the problem, we define an equivalent formulation by duplicating the variables and we consider the augmented Lagrangian of this latter formulation. Following the idea of the Alternating Direction Method of Multipliers (ADMM), we propose an algorithm where a two-blocks decomposition method is embedded within an augmented Lagrangian framework. The peculiarities of the proposed algorithm are the following: (1) the computation of the exact solution of a possibly nonconvex subproblem is not required; (2) the penalty parameter is iteratively updated once an approximated stationary point of the augmented Lagrangian is determined. Global convergence results are stated under mild assumptions and without requiring convexity of the objective function. Although the primary aim of the paper is theoretical, we perform numerical experiments on a nonconvex problem arising in machine learning, and the obtained results show the practical advantages of the proposed approach with respect to classical ADMM. [ABSTRACT FROM AUTHOR]

Sdpnal+ is a MATLAB software package that implements an augmented Lagrangian based method to solve large scale semidefinite programming problems with bound constraints. The implementation was initially based on a majorized semismooth Newton-CG augmented Lagrangian method, here we designed it within an inexact symmetric Gauss-Seidel based semi-proximal ADMM/ALM (alternating direction method of multipliers/augmented Lagrangian method) framework for the purpose of deriving simpler stopping conditions and closing the gap between the practical implementation of the algorithm and the theoretical algorithm. The basic code is written in MATLAB, but some subroutines in C language are incorporated via Mex files. We also design a convenient interface for users to input their SDP models into the solver. Numerous problems arising from combinatorial optimization and binary integer quadratic programming problems have been tested to evaluate the performance of the solver. Extensive numerical experiments conducted in [L.Q. Yang, D.F. Sun, and K.C. Toh, SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput. 7 (2015), pp. 331–366] show that the proposed method is quite efficient and robust, in that it is able to solve 98.9% of the 745 test instances of SDP problems arising from various applications to the accuracy of 10 − 6 in the relative KKT residual. [ABSTRACT FROM AUTHOR]

In this paper, we propose an augmented Lagrangian affine scaling (ALAS) algorithm for general nonlinear programming, for which a quadratic approximation to the augmented Lagrangian is minimized at each iteration. Different from the classical sequential quadratic programming (SQP), the linearization of nonlinear constraints is put into the penalty term of this quadratic approximation, which results in smooth objective of the subproblem and avoids possible inconsistency among the linearized constraints and trust region constraint. By applying affine scaling techniques to handle the strict bound constraints, an active set type affine scaling trust region subproblem is proposed. Through special strategies of updating Lagrange multipliers and adjusting penalty parameters, this subproblem is able to reduce the objective function value and feasibility errors in an adaptive well-balanced way. Global convergence of the ALAS algorithm is established under mild assumptions. Furthermore, boundedness of the penalty parameter is analyzed under certain conditions. Preliminary numerical experiments of ALAS are performed for solving a set of general constrained nonlinear optimization problems in CUTEr problem library. [ABSTRACT FROM AUTHOR]

We consider the image denoising problem using total variation (TV) regularization. This problem can be computationally challenging to solve due to the non-differentiability and non-linearity of the regularization term. We propose an alternating direction augmented Lagrangian (ADAL) method, based on a new variable splitting approach that results in subproblems that can be solved efficiently and exactly. The global convergence of the new algorithm is established for the anisotropic TV model. For the isotropic TV model, by doing further variable splitting, we are able to derive an ADAL method that is globally convergent. We compare our methods with the split Bregman method [T. Goldstein and S. Osher,The split Bregman method for l1-regularized problems, SIAM J. Imaging Sci. 2 (2009), pp. 323],which is closely related to it, and demonstrate their competitiveness in computational performance on a set of standard test images. [ABSTRACT FROM PUBLISHER]

In this paper, we study decomposition methods based on separable approximations for minimizing the augmented Lagrangian. In particular, we study and compare the diagonal quadratic approximation method (DQAM) of Mulvey and Ruszczyński [A diagonal quadratic approximation method for large scale linear programs, Oper. Res. Lett. 12 (1992), pp. 205–215] and the parallel coordinate descent method (PCDM) of Richtárik and Takáč [Parallel coordinate descent methods for big data optimization. Technical report, November 2012. arXiv:1212.0873]. We show that the two methods are equivalent for feasibility problems up to the selection of a step-size parameter. Furthermore, we prove an improved complexity bound for PCDM under strong convexity, and show that this bound is at least 8(L′/L̄)(ω−1)2times better than the best known bound for DQAM, where ω is the degree of partial separability andL’ andL̄are the maximum and average of the block Lipschitz constants of the gradient of the quadratic penalty appearing in the augmented Lagrangian. [ABSTRACT FROM PUBLISHER]

We consider a primal-dual augmented Lagrangian (PDAL) method for optimization problems with equality constraints. Each step of the PDAL requires solving the primal-dual (PD) linear system of equations. We show that under the standard second-order optimality condition the PDAL method generates a sequence, which locally converges to the PD solution with quadratic rate. [ABSTRACT FROM AUTHOR]

We consider nonlinear optimization programs with matrix inequality constraints, also known as nonlinear semidefinite programs. We prove local convergence for an augmented Lagrangian method which uses smooth spectral penalty functions. The sufficient second-order no-gap optimality condition and a suitable implicit function theorem are used to prove local linear convergence without the need to drive the penalty parameter to 0. [ABSTRACT FROM AUTHOR]

The augmented Lagrangian and Newton methods are used to simultaneously solve the primal and dual linear programming problems. The proposed approach is applied to the primal linear programming problem with a very large number (≈106) of nonnegative variables and a moderate (≈103) number of equality-type constraints. Computation results such as the solution of a linear programme with 10 million primal variables are presented. [ABSTRACT FROM AUTHOR]

An augmented Lagrange-SQP method with Lipschitz continuous Lagrange multiplier updates is analyzed. The approximation of this method is investigated, and convergence results are presented. A mesh-independence principle for the augmented Lagrange-SQP method is proved, which asserts that asymptotically the infinite-dimensional algorithm and finite-dimensional discretizations have the same convergence property. More precisely, for sufficiently small mesh-size there is at most a difference of one iteration step between the number of steps required by the infinite-dimensional method and its discretization to converge within a given tolerance ℇ > 0. The theoretical results are demonstrated numerically by a parameter identification problem. [ABSTRACT FROM AUTHOR]