augmented lagrangian method

Iterative Reweighted Linear Least Squares for Exact Penalty Subproblems on Product Sets

  • James V. Burke
  • Frank E. Curtis
  • Hao Wang
  • Jiashan Wang
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization Tags , , , , ,

    We present two matrix-free methods for solving exact penalty subproblems on product sets that arise when solving large-scale optimization problems. The first approach is a novel iterative reweighting algorithm (IRWA), which iteratively minimizes quadratic models of relaxed subproblems while automatically updating a relaxation vector. The second approach is based on alternating direction augmented Lagrangian (ADAL) … Read more

    On the Proximal Jacobian Decomposition of ALM for Multiple-block Separable Convex Minimization Problems and its Relationship to ADMM

  • Bingsheng He
  • Xiao-Ming Yuan
  • Hong-Kun Xu
    • Categories Convex Optimization Tags , , , , , ,

    The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. When the objective function of the model under consideration is representable as the sum of some functions without coupled variables, a Jacobian or Gauss-Seidel decomposition is often implemented to decompose the ALM subproblems so that the functions’ properties could … Read more

    A Regularized SQP Method with Convergence to Second-Order Optimal Points

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

    Regularized and stabilized sequential quadratic programming methods are two classes of sequential quadratic programming (SQP) methods designed to resolve the numerical and theoretical difficulties associated with ill-posed or degenerate nonlinear optimization problems. Recently, a regularized SQP method has been proposed that provides a strong connection between augmented Lagrangian methods and stabilized SQP methods. The method … Read more

    Optimal scenario set partitioning for multistage stochastic programming with the progressive hedging algorithm

  • Fabian Bastin
  • Pierre-Luc Carpentier
  • Michel Gendreau
    • Categories Stochastic Programming Tags , , ,

    In this paper, we propose a new approach to reduce the total running time (RT) of the progressive hedging algorithm (PHA) for solving multistage stochastic programs (MSPs) defined on a scenario tree. Instead of using the conventional scenario decomposition scheme, we apply a multi-scenario decomposition scheme and partition the scenario set in order to minimize … Read more

    Separable Approximations and Decomposition Methods for the Augmented Lagrangian

  • Burak Buke
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , , , , ,

    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\'{n}ski and the Parallel Coordinate Descent Method (PCDM) of Richt\'{a}rik and Tak\'{a}\v{c}. We show that the two methods are equivalent for feasibility problems up … Read more

    Local Convergence of the Method of Multipliers for Variational and Optimization Problems under the Sole Noncriticality Assumption

  • Alexey F. Izmailov
  • A. S. Kurennoy
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , ,

    We present local convergence analysis of the method of multipliers for equality-constrained variational problems (in the special case of optimization, also called the augmented Lagrangian method) under the sole assumption that the dual starting point is close to a noncritical Lagrange multiplier (which is weaker than second-order sufficiency). Local superlinear convergence is established under the … Read more

    On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming

  • Bingsheng He
  • Xiao-Ming Yuan
  • Liusheng Hou
    • Categories Convex Optimization Tags , , , , , ,

    The augmented Lagrangian method (ALM) is a benchmark for solving the convex minimization problem with linear constraints. We consider the special case where the objective is in form of the sum of m functions without coupled variables. For solving this separable convex programming model, it is usually required to decompose the ALM subproblem at each … Read more

    An Augmented Lagrangian Method for Conic Convex Programming

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a “simple” … Read more

    Abstract Newtonian Frameworks and Their Applications

  • Alexey F. Izmailov
  • A. S. Kurennoy
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , , ,

    We unify and extend some Newtonian iterative frameworks developed earlier in the literature, which results in a collection of convenient tools for local convergence analysis of various algorithms under various sets of assumptions including strong metric regularity, semistability, or upper-Lipschizt stability, the latter allowing for nonisolated solutions. These abstract schemes are further applied for deriving … Read more

    On the Augmented Lagrangian Dual for Integer Programming

  • Natashia Boland
  • Andrew C. Eberhard
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We consider the augmented Lagrangian dual for integer programming, and provide a primal characterization of the resulting bound. As a corollary, we obtain proof that the augmented Lagrangian is a strong dual for integer programming. We are able to show that the penalty parameter applied to the augmented Lagrangian term may be placed at a … Read more