Article ID: | iaor19971598 |
Country: | Netherlands |
Volume: | 62 |
Issue: | 1 |
Start Page Number: | 465 |
End Page Number: | 519 |
Publication Date: | Mar 1996 |
Journal: | Annals of Operations Research |
Authors: | Polyak R., Melman A. |
Keywords: | barrier function |
The Modified Barrier Function (MBF) have elements of both Classical Lagrangians (CL) and Classical Barrier Functions (CBF). The MBF methods find an unconstrained minimizer of some smooth barrier function in primal space and then update the Lagrange multipliers, while the barrier parameter either remains fixed or can be updated at each step. The numerical realization of the MBF method leads to the Newton MBF method, where the primal minimizer is found by using Newton's method. This minimizer is then used to update the Lagrange multipliers. In this paper, the authors examine the Newton MBF method for the Quadratic Programming (QP) problem. It will be shown that under standard second-order optimality conditions, there is a ball around the primal solution and a cut cone in the dual space such that for a set of Lagrange multipliers in this cut cone, the method converges quadratically to the primal minimizer from any point in the aforementioned ball, and continues to do so after each Lagrange multiplier update. The Lagrange multipliers remain within the cut cone and converge linearly to their optimal values. Any point in this ball will be called a ‘hot start’. Starting at such a ‘hot start’, at most