augmented lagrangian method

Augmented Lagrangian and Alternating Direction Methods for Convex Optimization: A Tutorial and Some Illustrative Computational Results

  • Jonathan Eckstein
    • Categories Convex Optimization Tags , ,

    The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from “big data” and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. This paper aims … Read more

    COMPUTATIONAL COMPLEXITY OF INEXACT GRADIENT AUGMENTED LAGRANGIAN METHODS: APPLICATION TO CONSTRAINED MPC

  • Ion Necoara
  • Quoc Tran-Dinh
  • Valentin Nedelcu
    • Categories Control Applications, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    We study the computational complexity certification of inexact gradient augmented Lagrangian methods for solving convex optimization problems with complicated constraints. We solve the augmented Lagrangian dual problem that arises from the relaxation of complicating constraints with gradient and fast gradient methods based on inexact first order information. Moreover, since the exact solution of the augmented … Read more

    An Efficient Augmented Lagrangian Method with Applications to Total Variation Minimization

  • Hong Jiang
  • Wotao Yin
  • Yin Zhang
  • Chengbo Li
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    Based on the classic augmented Lagrangian multiplier method, we propose, analyze and test an algorithm for solving a class of equality-constrained non-smooth optimization problems (chiefly but not necessarily convex programs) with a particular structure. The algorithm effectively combines an alternating direction technique with a nonmonotone line search to minimize the augmented Lagrangian function at each … Read more

    A GLOBALLY CONVERGENT STABILIZED SQP METHOD

  • Philip E. Gill
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    Sequential quadratic programming (SQP) methods are a popular class of methods for nonlinearly constrained optimization. They are particularly effective for solving a sequence of related problems, such as those arising in mixed-integer nonlinear programming and the optimization of functions subject to differential equation constraints. Recently, there has been considerable interest in the formulation of \emph{stabilized} … Read more

    Regularized Sequential Quadratic Programming

  • Philip E. Gill
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    We present the formulation and analysis of a new sequential quadratic programming (\SQP) method for general nonlinearly constrained optimization. The method pairs a primal-dual generalized augmented Lagrangian merit function with a \emph{flexible} line search to obtain a sequence of improving estimates of the solution. This function is a primal-dual variant of the augmented Lagrangian proposed … Read more

    An Alternating Direction Method for Total Variation Denoising

  • Donald Goldfarb
  • Zhiwei (Tony) Qin
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    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 … Read more

    Distributed Basis Pursuit

  • Pedro Aguiar
  • João Mota
  • Markus Püschel
  • João Xavier
    • Categories Convex Optimization, Network Optimization, Parallel Algorithms Tags , , ,

    We propose a distributed algorithm for solving the optimization problem Basis Pursuit (BP). BP finds the least L1-norm solution of the underdetermined linear system Ax = b and is used, for example, in compressed sensing for reconstruction. Our algorithm solves BP on a distributed platform such as a sensor network, and is designed to minimize … Read more

    Fast First-Order Methods for Stable Principal Component Pursuit

  • Necdet Serhat Aybat
  • Donald Goldfarb
  • Garud Iyengar
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , , ,

    The stable principal component pursuit (SPCP) problem is a non-smooth convex optimization problem, the solution of which has been shown both in theory and in practice to enable one to recover the low rank and sparse components of a matrix whose elements have been corrupted by Gaussian noise. In this paper, we first show how … Read more

    Structured Sparsity via Alternating Direction Methods

  • Donald Goldfarb
  • Zhiwei (Tony) Qin
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus … Read more

    Group Sparse Optimization by Alternating Direction Method

  • Wei Deng
  • Wotao Yin
  • Yin Zhang
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper proposes efficient algorithms for group sparse optimization with mixed L21-regularization, which arises from the reconstruction of group sparse signals in compressive sensing, and the group Lasso problem in statistics and machine learning. It is known that encoding the group information in addition to sparsity will lead to better signal recovery/feature selection. The L21-regularization … Read more