The Newton modified barrier method for QP problems

The Newton modified barrier method for QP problems

0.00 Avg rating0 Votes
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: ,
Keywords: barrier function
Abstract:

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 equ1 Newton steps are sufficient to perform the primal minimization which is necessary for the Lagrange multiplier update. Here, equ2 is the desired accuracy. Because of the linear convergence of the Lagrange multipliers, this means that only equ3equ4 Newton steps are required to reach an equ5-approximation to the solution from any ‘hot start’. In order to reach the ‘hot start’, one has to perform equ6 Newton steps, where m characterizes the size of the problem and equ7 is the condition number of the QP problem. This condition number will be characterized explicitly in terms of key parameters of the QP problem, which in turn depend on the input data and the size of the problem.

Reviews

Required fields are marked *. Your email address will not be published.