The Mehrotra Predictor-Corrector Interior-Point Method as a Perturbed Composite Newton Method
Tapia, Richard A.
The simplified Newton method reduces the work required by Newton's method per iteration by reusing the initial Jacobian matrix. However, fast convergence is sacrificed. The level-m composite Newton method attempts to balance the trade-off between work and fast convergence by composing one Newton step with m simplified Newton steps. In this work we demonstrate that Mehrotra's predictor-corrector interior-point method is the level-1 composite Newton variant of the Newton interior-point method. The level-1 composite Newton method is well known to give cubic convergence. Hence we find it mathematically enlightening that the interior-point aspect of the predictor-corrector method, i.e. choosing the steplength so that the iterates remain nonnegative, precludes the standard proof of cubic convergence, but does support the proof of quadratic convergence. We next demonstrate that by choosing steplength one in a neighborhood of the solution (therefore allowing negative iterates) cubic convergence can be retained for nondegenerate problems. Preliminary numerical experiments with this locally modified algorithm are most impressive and are an important and appropriate part of a companion paper that numerically studies the local behavior of the predictor-corrector algorithm.
Citable link to this pagehttps://hdl.handle.net/1911/101682
MetadataShow full item record
- CAAM Technical Reports