augmented lagrangian method

On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization

  • Geovani Nunes Grapiglia
  • Ya-xiang Yuan
    • Categories Nonlinear Optimization Tags , , ,

    In this paper we study the worst-case complexity of an inexact Augmented Lagrangian method for nonconvex constrained problems. Assuming that the penalty parameters are bounded, we prove a complexity bound of $\mathcal{O}(|\log(\epsilon)|)$ outer iterations for the referred algorithm to generate an $\epsilon$-approximate KKT point, for $\epsilon\in (0,1)$. When the penalty parameters are unbounded, we prove … Read more

    Indefinite linearized augmented Lagrangian method for convex programming with linear inequality constraints

  • Bingsheng He
  • Shengjie Xu
  • Jing Yuan
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    The augmented Lagrangian method (ALM) is a benchmark for tackling the convex optimization problem with linear constraints; ALM and its variants for linearly equality-constrained convex minimization models have been well studied in the literatures. However, much less attention has been paid to ALM for efficiently solving the linearly inequality-constrained convex minimization model. In this paper, … Read more

    An Augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem

  • Ernesto G. Birgin
  • Walter Gómez
  • Gabriel Haeser
  • Leonardo M. Mito
  • Daiana O. Santos
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming Tags , , ,

    In this work we present an Augmented Lagrangian algorithm for nonlinear semidefinite problems (NLSDPs), which is a natural extension of its consolidated counterpart in nonlinear programming. This method works with two levels of constraints; one that is penalized and other that is kept within the subproblems. This is done in order to allow exploiting the … Read more

    A two-level distributed algorithm for nonconvex constrained optimization

  • Xu Andy Sun
  • Kaizhao Sun
    • Categories Network Optimization, Nonlinear Optimization, Parallel Algorithms Tags , ,

    This paper aims to develop distributed algorithms for nonconvex optimization problems with complicated constraints associated with a network. The network can be a physical one, such as an electric power network, where the constraints are nonlinear power flow equations, or an abstract one that represents constraint couplings between decision variables of different agents. Despite the … Read more

    Towards an efficient Augmented Lagrangian method for convex quadratic programming

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Luiz-Rafael Santos
    • Categories Constrained Nonlinear Optimization, Linear Programming, Quadratic Programming Tags , , , ,

    Interior point methods have attracted most of the attention in the recent decades for solving large scale convex quadratic programming problems. In this paper we take a different route as we present an augmented Lagrangian method for convex quadratic programming based on recent developments for nonlinear programming. In our approach, box constraints are penalized while … Read more

    A Partial PPA block-wise ADMM for Multi-Block Constrained Separable Convex Optimization

  • Yuan Shen
    • Categories Applications - OR and Management Sciences, Unconstrained Optimization Tags , , ,

    The alternating direction method of multipliers(ADMM) has been proved to be effective for solving two-block separable convex optimization subject to linear constraints. However, it is not necessarily convergent when it is extended to multiple-block case directly. One remedy could be regrouping multiple-block variables into two groups firstly and then adopting the classic ADMM to the … Read more

    A Shifted Primal-Dual Interior Method for Nonlinear Optimization

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

    Interior methods provide an effective approach for the treatment of inequality constraints in nonlinearly constrained optimization. A new primal-dual interior method is proposed based on minimizing a sequence of shifted primal-dual penalty-barrier functions. Certain global convergence properties are established. In particular, it is shown that every limit point is either an infeasible stationary point, or … Read more

    Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and their Practical Implications

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Frank Navarro Rojas
    • Categories Constrained Nonlinear Optimization, Game Theory Tags , , , ,

    Generalized Nash Equilibrium Problems (GNEPs) are a generalization of the classic Nash Equilibrium Problems (NEPs), where each player’s strategy set depends on the choices of the other players. In this work we study constraint qualifications and optimality conditions tailored for GNEPs and we discuss their relations and implications for global convergence of algorithms. Surprisingly, differently … Read more

    A sequential optimality condition related to the quasinormality constraint qualification and its algorithmic consequences

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

    In the present paper, we prove that the augmented Lagrangian method converges to KKT points under the quasinormality constraint qualification, which is associated with the external penalty theory. For this purpose, a new sequential optimality condition for smooth constrained optimization, called PAKKT, is defined. The new condition takes into account the sign of the dual … Read more

    A Primal-Dual Augmented Lagrangian Penalty-Interior-Point Filter Line Search Algorithm

  • Christof Büskens
  • Renke Kuhlmann
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    Interior-point methods have been shown to be very efficient for large-scale nonlinear programming. The combination with penalty methods increases their robustness due to the regularization of the constraints caused by the penalty term. In this paper a primal-dual penalty-interior-point algorithm is proposed, that is based on an augmented Lagrangian approach with an l2-exact penalty function. … Read more