Complexity analysis for the Newton modified barrier function method

Citation

Melman, Aharon (1992) Complexity analysis for the Newton modified barrier function method. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/yrr2-5a17. https://resolver.caltech.edu/CaltechETD:etd-08082007-143657

Abstract

NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document.

The modified barrier function (MBF) is examined for linear, convex quadratic and other convex nonlinear constrained optimization problems. This new method of transforming a constrained problem into a sequence of unconstrained ones has elements of both Lagrangian function and barrier function methods. At each step, the method updates multipliers, which converge to the optimal Lagrange multipliers. Each such update entails a minimization using Newton's method.

We show that there is a ball around the primal-dual solution of the optimization problem, a so-called "hot start" ball, such that starting from any point in this ball, Newton's method converges quadratically and continues to do so after each subsequent update. We characterize the "hot start" ball in terms of the primal-dual solution of the optimization problem.

This means that from the "hot start" on, only [...] Newton steps are necessary after each update in order to reach the next update ([...] > 0 is the desired accuracy for the solution). Taking into account the basic MBF convergence properties, one obtains that the number of Newton steps from a "hot start" to the solution is [...].

To reach the "hot start" one has to spend [...], where [...] > 0 is defined by the condition number of the constrained optimization problem, which in turn can be characterized explicitly in terms of quantities defined at the solution.

Thesis Files