The Newton modified barrier method for QP problems

Abstract

The Modified Barrier Functions (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, we 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 mostO(In Inɛ ^-1) Newton steps are sufficient to perform the primal minimization which is necessary for the Lagrange multiplier update. Here, ɛ>0 is the desired accuracy. Because of the linear convergence of the Lagrange multipliers, this means that onlyO(Inɛ ^-1)O(In Inɛ ^-1) Newton steps are required to reach an ɛ-approximation to the solution from any “hot start”. In order to reach the “hot start”, one has to perform$\mathcal{O}(\sqrt m {\text{ }}In{\text{ }}C)$ Newton steps, wherem characterizes the size of the problem andC>0 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.