Melman, Aharon (1992) Complexity analysis for the Newton modified barrier function method. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-08082007-143657
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:||Restricted to Caltech community only|
|Defense Date:||18 February 1992|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||14 Aug 2007|
|Last Modified:||26 Dec 2012 02:56|
- Final Version
Restricted to Caltech community only
See Usage Policy.
Repository Staff Only: item control page