Arc-Search Path-Following Interior-Point Algorithms for Linear Programming

Yaguang Yang (yaguang.yangverizon.net)

Abstract: Arc-search is developed in optimization algorithms. In this paper, simple analytic arcs are used to approximate the central path of the linear programming. The primal-dual path-following interior-point method is then used to search optimizers along the arcs for linear programming. They require fewer iterations to find the optimal solutions in all the tested problems in Netlib than Matlab optimization toolbox {\tt linprog} which implements the state-of-art Mehrotra's predictor-corrector algorithm.

Keywords: Arc-search, path-following, linear programming

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

Citation: NRC, Office of Research, 21 Church Street, Rockville, 20850, July, 2009

Download: [PDF]

Entry Submitted: 08/14/2009
Entry Accepted: 08/14/2009
Entry Last Modified: 09/19/2009

Modify/Update this entry