Accession Number:

ADA453102

Title:

The Mehrotra Predictor-Corrector Interior-Point Method as a Perturbed Composite Newton Method

Descriptive Note:

Corporate Author:

RICE UNIV HOUSTON TX DEPT OF COMPUTATIONAL AND APPLIED MATHEMATICS

Report Date:

1993-07-01

Pagination or Media Count:

21.0

Abstract:

It is well known that the celebrated Kojima-Mizuno-Yoshise primal-dual interior-point method for linear programming can be viewed as a damped perturbed Newtons method. Recently, Mehrotra suggested a predictor-corrector variant of this method. It is currently the interior-point method of choice for linear programming. The simplified Newton method, at the expense of fast convergence, reduces the work required by Newtons method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton Step. In this work we demonstrate that if the Newton component in the Kojima-Mizuno-Yoshise primal-dual method is replaced with a composite Newton component, then the resulting method is the Mehrotra predictor- corrector method.

Subject Categories:

  • Numerical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE