The analyticity of interior-point-paths at strictly complementary solutions of linear programs

1 January 1998

journal article
other
Published by Taylor & Francis in Optimization Methods and Software

Vol. 9 (1-3) , 209-243
https://doi.org/10.1080/10556789808805693

Abstract

This paper investigates the analyticity of certain paths that arise in the context of feasible interior-point-methods. It is shown that there exists a neigborhood surrounding a strictly complementary optimal point where the path is analytic and all its derivatives with respect to the path parameter exist, even if the linear program is degenerate. For this reason it is possible to extend the path through the feasible region from the positive real axis to the left complex half plane. This is done by a canonical transformation of the linear program. The analyticity provides the theoretical foundation for numerical methods following the path by higher-order approximations

Keywords

This publication has 8 references indexed in Scilit:

An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
Mathematics of Operations Research, 1994
Limiting behavior of weighted central paths in linear programming
Mathematical Programming, 1994
Infeasible Interior Point Methods for Solving Linear Programs
Published by Springer Nature ,1994
A primal—dual infeasible-interior-point algorithm for linear programming
Mathematical Programming, 1993
On the Implementation of a Primal-Dual Interior Point Method
SIAM Journal on Optimization, 1992
On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
SIAM Journal on Optimization, 1992
An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations
Mathematical Programming, 1990
A new polynomial-time algorithm for linear programming
Combinatorica, 1984