Citation
Melman, Aharon (1992) Complexity analysis for the Newton modified barrier function method. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd08082007143657
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 primaldual solution of the optimization problem, a socalled "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 primaldual 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:  Restricted to Caltech community only 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  18 February 1992 
Record Number:  CaltechETD:etd08082007143657 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd08082007143657 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  3054 
Collection:  CaltechTHESIS 
Deposited By:  Imported from ETDdb 
Deposited On:  14 Aug 2007 
Last Modified:  26 Dec 2012 02:56 
Thesis Files
PDF (Melman_a_1992.pdf)
 Final Version
Restricted to Caltech community only See Usage Policy. 3059Kb 
Repository Staff Only: item control page