augmented lagrangian method

Global minimization using an Augmented Lagrangian method with variable lower-level constraints

  • Ernesto G. Birgin
  • Christodoulos A. Floudas
  • José Mario Martínez
    • Categories Global Optimization Tags , , ,

    A novel global optimization method based on an Augmented Lagrangian framework is introduced for continuous constrained nonlinear optimization problems. At each outer iteration the method requires the $\varepsilon$-global minimization of the Augmented Lagrangian with simple constraints. Global convergence to an $\varepsilon$-global minimizer of the original problem is proved. The subproblems are solved using the $\alpha$BB … Read more

    Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs

  • Michael P. Friedlander
  • Sven Leyffer
    • Categories Quadratic Programming Tags , , , , ,

    We present a two-phase algorithm for solving large-scale quadratic programs (QPs). In the first phase, gradient-projection iterations approximately minimize an augmented Lagrangian function and provide an estimate of the optimal active set. In the second phase, an equality-constrained QP defined by the current inactive variables is approximately minimized in order to generate a second-order search … Read more

    The Rate of Convergence of the Augmented Lagrangian Method for Nonlinear Semidefinite Programming

  • Jie Sun
  • Defeng Sun
  • Liwei Zhang
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We analyze the rate of local convergence of the augmented Lagrangian method for nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and certain variational analysis on the projection operator in the symmetric-matrix space. Without … Read more

    Blind Source Separation using Relative Newton Method combined with Smoothing Method of Multipliers

  • Michael Zibulevsky
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , , , ,

    We study a relative optimization framework for quasi-maximum likelihood blind source separation and relative Newton method as its particular instance. The structure of the Hessian allows its fast approximate inversion. In the second part we present Smoothing Method of Multipliers (SMOM) for minimization of sum of pairwise maxima of smooth functions, in particular sum of … Read more

    On Augmented Lagrangian methods with general lower-level constraints

  • Roberto Andreani
  • Ernesto G. Birgin
  • José Mario Martínez
  • María Laura Schuverdt
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    Augmented Lagrangian methods with general lower-level constraints are considered in the present research. These methods are useful when efficient algorithms exist for solving subproblems where the constraints are only of the lower-level type. Two methods of this class are introduced and analyzed. Inexact resolution of the lower-level constrained subproblems is considered. Global convergence is proved … Read more

    Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification

  • Roberto Andreani
  • Ernesto G. Birgin
  • José Mario Martínez
  • María Laura Schuverdt
    • Categories Nonlinear Optimization Tags , , ,

    Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under … Read more

    Constrained optimization in seismic reflection tomography: an SQP augmented Lagrangian approach

  • Frederic Delbos
  • Jean Charles Gilbert
  • R. Glowinski
  • D. Sinoquet
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Quadratic Programming Tags , , , , , ,

    Seismic reflection tomography is a method for determining a subsurface velocity model from the traveltimes of seismic waves reflecting on geological interfaces. From an optimization viewpoint, the problem consists in minimizing a nonlinear least-squares function measuring the mismatch between observed traveltimes and those calculated by ray tracing in this model. The introduction of a priori … Read more

    Solving Lift-and-Project Relaxations of Binary Integer Programs

  • Samuel Burer
  • Dieter Vandenbussche
    • Categories 0-1 Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lov\’asz and Schrijver. In particular, we study both linear and semidefinite relaxations. The key idea is a restructuring of the relaxations, which isolates the complicating constraints and allows for a Lagrangian approach. We detail an enhanced subgradient method and discuss … Read more

    Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems

  • Frederic Delbos
  • Jean Charles Gilbert
    • Categories Quadratic Programming Tags , , , , , , ,

    We consider an augmented Lagrangian algorithm for minimizing a convex quadratic function subject to linear inequality constraints. Linear optimization is an important particular instance of this problem. We show that, provided the augmentation parameter is large enough, the constraint value converges {\em globally\/} linearly to zero. This property is viewed as a consequence of the … Read more

    Double-Regularization Proximal Methods, with Complementarity Applications

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

    We consider the variational inequality problem formed by a general set-valued maximal monotone operator and a possibly unbounded “box” in $R^n$, and study its solution by proximal methods whose distance regularizations are coercive over the box. We prove convergence for a class of double regularizations generalizing a previously-proposed class of Auslender et al. We apply … Read more