A matrix-free interior point continuous trajectory for linearly constrained convex programming
Preprint
Abstract
Interior point methods for solving linearly constrained convex programming involve a variable projection matrix at each iteration to deal with the linear constraints. This matrix often becomes ill-conditioned near the boundary of the feasible region that results in wrong search directions and extra computational cost. A matrix-free interior point augmented Lagrangian continuous trajectory is therefore proposed and studied for linearly constrained convex programming. A closely related ordinary differential equation (ODE) system is formulated. In this ODE system, the variable projection matrix is no longer needed. By only assuming the existence of an optimal solution, we show that, starting from any interior feasible point, (i) the interior point augmented Lagrangian continuous trajectory is convergent; and (ii) the limit point is indeed an optimal solution of the original optimization problem. Moreover, with the addition of the strictly complementarity condition, we show that the associated Lagrange multiplier converges to an optimal solution of the Lagrangian dual problem. Based on the studied ODE system, several possible search directions for discrete algorithms are proposed and discussed.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programmingMathematical Programming, 2007
- Examples of ill-behaved central paths in convex optimizationMathematical Programming, 2004
- A convergence analysis for a convex version of Dikin's algorithmAnnals of Operations Research, 1996
- A simple proof of a primal affine scaling methodAnnals of Operations Research, 1996
- A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptionsMathematical Programming, 1993
- On the convergence of the exponential multiplier method for convex programmingMathematical Programming, 1993
- Global convergence of the affine scaling methods for degenerate linear programming problemsMathematical Programming, 1991
- Limiting behavior of the affine scaling continuous trajectories for linear programming problemsMathematical Programming, 1991
- An extension of Karmarkar's projective algorithm for convex quadratic programmingMathematical Programming, 1989
- Dynamics of games and genes: Discrete versus continuous timeJournal of Mathematical Biology, 1983