A Caltech Library Service

Complexity analysis for the Newton modified barrier function method


Melman, Aharon (1992) Complexity analysis for the Newton modified barrier function method. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/yrr2-5a17.


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.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Keller, Herbert Bishop
Thesis Committee:
  • Unknown, Unknown
Defense Date:18 February 1992
Record Number:CaltechETD:etd-08082007-143657
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3054
Deposited By: Imported from ETD-db
Deposited On:14 Aug 2007
Last Modified:16 Apr 2021 22:34

Thesis Files

PDF (Melman_a_1992.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page