iteration complexity – Page 6 – Optimization Online

Enlarging Neighborhoods of Interior-Point Algorithms for Linear Programming via Least Values of Proximity measure Functions

Published: 2005/06/27

Linear Programming interior point methods, iteration complexity, linear programming, neighborhoods

It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than those small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far … Read more

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

Published: 2003/12/05, Updated: 2004/09/24

Frederic Delbos

Jean Charles Gilbert

Quadratic Programming augmented lagrangian method, convex quadratic programming, distance to a polyhedron, error bound, global linear convergence, iteration complexity, linear constraints, proximal algorithm

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