Optimization Online


How the augmented Lagrangian algorithm can deal with an infeasible convex quadratic optimization problem

Alice Chiche(Alice.Chiche***at***artelys.com)
Jean Charles Gilbert(Jean-Charles.Gilbert***at***inria.fr)

Abstract: This paper analyses the behavior of the augmented Lagrangian algorithm when it deals with an infeasible convex quadratic optimization problem. It is shown that the algorithm finds a point that, on the one hand, satisfies the constraints shifted by the smallest possible shift that makes them feasible and, on the other hand, minimizes the objective on the corresponding shifted constrained set. The speed of convergence to such a point is globally linear, with a rate that is inversely proportional to the augmentation parameter. This suggests us a rule for determining the augmentation parameter that aims at controlling the speed of convergence of the shifted constraint norm to zero; this rule has the advantage of generating bounded augmentation parameters even when the problem is infeasible.

Keywords: augmented Lagrangian algorithm, augmentation parameter update, closest feasible problem, convex quadratic optimization, feasible shift, global linear convergence, infeasible problem, proximal point algorithm, quasi-global error bound, shifted constraint

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Convex and Nonsmooth Optimization

Citation: INRIA Research Report RR-8583 (August 23, 2014). INRIA Paris-Rocquencourt, Pomdapi team - BP 105, F-78153 Le Chesnay Cedex (France).

Download: [PDF]

Entry Submitted: 08/25/2014
Entry Accepted: 08/25/2014
Entry Last Modified: 08/25/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society