《《2016 Improved Full-Newton Step O(nL) Infeasible Interior-Point Method for Linear Optimization》.pdf

J Optim Theory Appl (2010) 145: 271–288 DOI 10.1007/s10957-009-9634-0 Improved Full-Newton Step O(nL) Infeasible Interior-Point Method for Linear Optimization G. Gu · H. Mansouri · M. Zangiabadi · Y.Q. Bai · C. Roos Published online: 4 November 2009 © The Author(s) 2009. This article is published with open access at S Abstract We present several improvements of the full-Newton step infeasible interior-point method for linear optimization introduced by Roos (SIAM J. Optim. 16(4):1110–1136, 2006). Each main step of the method consists of a feasibility step and several centering steps. We use a more natural feasibility step, which targets the μ+-center of the next pair of perturbed problems. As for the centering steps, we apply a sharper quadratic convergence result, which leads to a slightly wider neighborhood for the feasibility steps. Moreover, the analysis is much simplified and the iteration bound is slightly better. Keywords Linear optimization · Infeasible interior-point method · Full-Newton step · Homotopy method Communicated by Florian Potra. G. Gu ( ) · C. Roos Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, Netherlands e-mail: G.Gu@tudelft.nl C. Roos e-mail: C.Roos@tudelft.nl H. Mansouri · M. Zangiabadi Department of Mathematical Science, Shahrekord University, P.O. Box 115, Shahrekord, Iran H. Mansouri e-mail: H.Mansouri@tudelft.nl M. Zangiabadi e-mail: M.Zangiabadi@tudelft.nl Y.Q. Bai Department of Mathematics, Shanghai University, Shanghai, 200444, China e-mail: yqbai@ 272 J Optim Theory Appl (2010) 145: 271–288 1 Introduction We consider the linear optimization (LO) problem in the standard form (P) min{cTx : Ax = b, x ≥ 0}, with its dual problem (D) max{bT y : AT y + s = c, s