Groupe d’études et de recherche en analyse des décisions


From Global to Local Convergence of Interior Methods for Nonlinear Optimization

, et

We propose a modified primal-dual interior-point method for nonlinear programming that relaxes the requirement of closely following the central path and lends itself to dynamic updates of the barrier parameter. The latter promote better synchronization between the barrier parameter and the optimality residual, and increase robustness. In the framework of a generic outer iteration, we show that the dynamic barrier parameter converges to zero, that the unit Newton step is asymptotically accepted and that linear or superlinear convergence occurs when the barrier parameter goes to zero linearly or superlinearly. A salient feature of our algorithm resides in the transparent transition between the global and local regimes. Where a typical implementation of an interior-point method consists in chaining a globalization algorithm with a fast locally-convergent algorithm, the method that we propose remains one and the same in the global and local phases. Numerical experiments show that our method improves the standard interior-point implementation substantially by dramatically reducing the number of inner iterations per outer iteration and by controling the barrier parameter dynamically. It also compares favorably with other recent and less recent heuristic dynamic updates.

, 30 pages

Ce cahier a été révisé en février 2011