augmented lagrangian method

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

    A new exact penalty function

  • Waltraud Huyer
  • Arnold Neumaier
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    For constrained smooth or nonsmooth optimization problems, new continuously differentiable penalty functions are derived. They are proved exact in the sense that under some nondegeneracy assumption, local optimizers of a nonlinear program are precisely the optimizers of the associated penalty function. This is achieved by augmenting the dimension of the program by a variable that … Read more

    Smoothing Method of Multipliers for Sum-Max Problems

  • Michael Zibulevsky
    • Categories Convex Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , ,

    We study nonsmooth unconstrained optimization problem, which includes sum of pairwise maxima of smooth functions. Minimum $l_1$-norm approximation is a particular case of this problem. Combining ideas Lagrange multipliers with smooth approximation of max-type function, we obtain a new kind of nonquadratic augmented Lagrangian. Our approach does not require artificial variables, and preserves sparse structure … Read more