A polynomial predictor-corrector trust-region algorithm for linear programming

Guanghui Lan(glanisye.gatech.edu)
Renato Monteiro(monteiroisye.gatech.edu)
Takashi Tsuchiya(tsuchiyasun312.ism.ac.jp)

Abstract: In this paper we present a scaling-invariant interior-point predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling direction or a new trust-region type direction, whose construction depends on a scaling invariant bipartition of the variables determined by the AS direction. This contrasts with the layered least squares direction introduced in \cite{VAVASIS94}, whose construction depends on multiple-layered partitions of the variables that are not scaling invariant. Moreover, it is shown that the overall arithmetic complexity of the algorithm (weakly) depends on the right hand side and the cost of the LP in view of the work involved in the computation of the trust region steps.

Keywords: Interior-point algorithms, primal-dual algorithms, trust-region,strongly polynomial, linear programming

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Nonlinear Optimization

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, May, 2007.

Download: [PDF]

Entry Submitted: 06/01/2007
Entry Accepted: 06/01/2007
Entry Last Modified: 06/01/2007

Modify/Update this entry