Effects of finite-precision arithmetic on interior-point methods for nonlinear programming

Stephen J. Wright

We show that the effects of finite-precision arithmetic in forming and solving the linear system that arises at each iteration of primal-dual interior-point algorithms for nonlinear programming are benign. Even when we replace the standard assumption that the active constraint gradients are independent by the weaker Mangasarian-Fromovitz constraint qualification, rapid convergence usually is attainable, even when cancellation and roundoff errors occur during the calculations. This conclusion holds for all three of the standard formulations of the linear system that is solved at each iteration of a primal-dual method. In deriving our main results, we prove a key technical result about the size of the exact primal-dual step. This result can be used to modify existing analysis of primal-dual interior-point methods for convex programming, making it possible to extend the superlinear local convergence results to the nonconvex case.

Preprint ANL/MCS-P705-0198, Mathematics and Computer Science Division, Argonne National Laboratory, January, 1998.

Also: OTC Technical Report 98/03, Optimization Tecnology Center, January, 1998.

Contact: wright@mcs.anl.gov