augmented lagrangian method

Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Constrained Nonlinear Optimization Tags , , ,

    At each outer iteration of standard Augmented Lagrangian methods one tries to solve a box-constrained optimization problem with some prescribed tolerance. In the continuous world, using exact arithmetic, this subproblem is always solvable. Therefore, the possibility of finishing the subproblem resolution without satisfying the theoretical stopping conditions is not contemplated in usual convergence theories. However, … Read more

    A Unified Approach for Minimizing Composite Norms

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , , , , , ,

    We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem min |sigma(F(X)-G)|_alpha + |C(X)- d|_beta subject to A(X)-b in Q; where sigma(X) denotes the vector of singular values of X, the matrix norm |sigma(X)|_alpha denotes either the Frobenius, the nuclear, or the L2-operator norm of X, the vector norm |.|_beta … Read more

    A First-Order Augmented Lagrangian Method for Compressed Sensing

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    We propose a First-order Augmented Lagrangian algorithm (FAL) for solving the basis pursuit problem. FAL computes a solution to this problem by inexactly solving a sequence of L1-regularized least squares sub-problems. These sub-problems are solved using an infinite memory proximal gradient algorithm wherein each update reduces to “shrinkage” or constrained “shrinkage”. We show that FAL … Read more

    Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization

  • Junfeng Yang
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , ,

    The nuclear norm is widely used to induce low-rank solutions for many optimization problems with matrix variables. Recently, it has been shown that the augmented Lagrangian method (ALM) and the alternating direction method (ADM) are very efficient for many convex programming problems arising from various applications, provided that the resulting subproblems are sufficiently simple to … Read more

    Recovering low-rank and sparse components of matrices from incomplete and noisy observations

  • Tao Min
  • Xiao-Ming Yuan
    • Categories Convex Optimization, Statistics Tags , , , , ,

    Many applications arising in a variety of fields can be well illustrated by the task of recovering the low-rank and sparse components of a given matrix. Recently, it is discovered that this NP-hard task can be well accomplished, both theoretically and numerically, via heuristically solving a convex relaxation problem where the widely-acknowledged nuclear norm and … Read more

    Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions

  • Donald Goldfarb
  • Shiqian Ma
  • Katya Scheinberg
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    We present in this paper first-order alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution, while our accelerated (i.e., fast) versions of them require at most $O(1/\sqrt{\epsilon})$ iterations, with little change in … Read more

    Alternating Direction Augmented Lagrangian Methods for semidefinite programming

  • Donald Goldfarb
  • Zaiwen Wen
  • Wotao Yin
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    We present an alternating direction method based on an augmented Lagrangian framework for solving semidefinite programming (SDP) problems in standard form. At each iteration, the algorithm, also known as a two-splitting scheme, minimizes the dual augmented Lagrangian function sequentially with respect to the Lagrange multipliers corresponding to the linear constraints, then the dual slack variables … Read more

    An Augmented Lagrangian Approach for Sparse Principal Component Analysis

  • Zhaosong Lu
  • Yong Zhang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , ,

    Principal component analysis (PCA) is a widely used technique for data analysis and dimension reduction with numerous applications in science and engineering. However, the standard PCA suffers from the fact that the principal components (PCs) are usually linear combinations of all the original variables, and it is thus often difficult to interpret the PCs. To … Read more

    Iteration-complexity of first-order augmented Lagrangian methods for convex programming

  • Guanghui Lan
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    This paper considers a special class of convex programming (CP) problems whose feasible regions consist of a simple compact convex set intersected with an affine manifold. We present first-order methods for this class of problems based on an inexact version of the classical augmented Lagrangian (AL) approach, where the subproblems are approximately solved by means … Read more

    Proximal Methods for Nonlinear Programming: Double Regularization and Inexact Subproblems

  • Jonathan Eckstein
  • Paulo J. S. Silva
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , ,

    This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that … Read more