augmented lagrangian method

A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization

  • Chuan He
  • Zhaosong Lu
    • Categories Cone Programming, Nonlinear Optimization Tags , , , , , ,

    \(\) In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. … Read more

    A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees

  • Chuan He
  • Zhaosong Lu
  • Ting Kei Pong
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    \(\) In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. … Read more

    A first-order augmented Lagrangian method for constrained minimax optimization

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Constrained Nonlinear Optimization, Robust Optimization Tags , , ,

    \(\) In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method recently developed in [26] by the authors. Under some suitable assumptions, … Read more

    On enhanced KKT optimality conditions for smooth nonlinear optimization

  • Roberto Andreani
  • María Laura Schuverdt
  • Leonardo D. Secchin
    • Categories Nonlinear Optimization Tags , , , ,

    The Fritz-John (FJ) and KKT conditions are a fundamental tool to characterize minimizers and lie in the root of almost any method for constrained optimization. Since the seminal works of Fritz John, Karush, Kuhn and Tucker, FJ/KKT conditions have been enhanced by adding extra necessary conditions. Such an extension was first proposed by Hestenes in … Read more

    An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems

  • Arnesh Sujanani
  • Renato D.C. Monteiro
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    This work presents an adaptive superfast proximal augmented Lagrangian (AS-PAL) method for solving linearly-constrained smooth nonconvex composite optimization problems. Each iteration of AS-PAL inexactly solves a possibly nonconvex proximal augmented Lagrangian (AL) subproblem obtained by an aggressive/adaptive choice of prox stepsize with the aim of substantially improving its computational performance followed by a full Lagrangian … Read more

    Faster Lagrangian-based methods: a unified prediction-correction framework

  • Zhang Tao
  • Xia Yong
  • Li Shiru
    • Categories Convex Optimization Tags , , ,

    Motivated by the prediction-correction framework constructed by He and Yuan [SIAM J. Numer. Anal. 50: 700-709, 2012], we propose a unified prediction-correction framework to accelerate Lagrangian-based methods. More precisely, for strongly convex optimization, general linearized Lagrangian method with indefinite proximal term, alternating direction method of multipliers (ADMM) with the step size of Lagrangian multiplier not … Read more

    Partitioning through projections: strong SDP bounds for large graph partition problems

  • Frank de Meijer
  • Renata Sotirov
  • Angelika Wiegele
  • Shudian Zhao
    • Categories Semi-definite Programming Tags , , , ,

    The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more

    A novel sequential optimality condition for smooth constrained optimization and algorithmic consequences

  • Renan W. Prado
  • Sandra A. Santos
  • Lucas E. A. Simões
    • Categories Constrained Nonlinear Optimization Tags , ,

    In the smooth constrained optimization setting, this work introduces the Domain Complementary Approximate Karush-Kuhn-Tucker (DCAKKT) condition, inspired by a sequential optimality condition recently devised for nonsmooth constrained optimization problems. It is shown that the augmented Lagrangian method can generate limit points satisfying DCAKKT, and it is proved that such a condition is not related to … Read more

    Global Convergence of Augmented Lagrangian Method Applied to Mathematical Program with Switching Constraints

  • Lei Guo
  • Gao-Xi Li
  • Xinmin Yang
    • Categories Complementarity and Variational Inequalities Tags , ,

    The mathematical program with switching constraints (MPSC) is a kind of problems with disjunctive constraints. The existing convergence results cannot directly be applied to this kind of problem since the required constraint qualifications for ensuring the convergence are very likely to fail. In this paper, we apply the augmented Lagrangian method (ALM) to solve the … Read more

    Global Complexity Bound of a Proximal ADMM for Linearly-Constrained Nonseperable Nonconvex Composite Programming

  • Weiwei Kong
  • Renato D.C. Monteiro
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    This paper proposes and analyzes a dampened proximal alternating direction method of multipliers (DP.ADMM) for solving linearly-constrained nonconvex optimization problems where the smooth part of the objective function is nonseparable. Each iteration of DP.ADMM consists of: (ii) a sequence of partial proximal augmented Lagrangian (AL) updates, (ii) an under-relaxed Lagrange multiplier update, and (iii) a … Read more