Optimization Online


Optimized choice of parameters in interior-point methods for linear programming

Luiz Rafael Santos(lrsantos11***at***gmail.com)
Fernando Villas-Bas(fernandovillasboas***at***gmail.com)
Aurelio Ribeiro Leite Oliveira(aurelio***at***ime.unicamp.br)
Clovis Perin(clovisperin***at***gmail.com)

Abstract: In this work, we propose a predictor-corrector interior point method for linear programming in a primal-dual context, where the next iterate is chosen by the minimization of a polynomial merit function of three variables: the first is the steplength, the second defines the central path and the third models the weight of a corrector direction. The merit function minimization is performed by restricting it to constraints defined by a neighborhood of the central path that allows wide steps. In this framework, we combine different directions, such as the predictor, the corrector and the centering directions, with the aim of producing a better one. The proposed method generalizes most of predictor-corrector interior point methods, depending on the choice of the variables described above. Convergence analysis of the method is carried out, considering an initial point that has a good practical performance, which results in Q-linear convergence of the iterates with polynomial complexity. Numerical experiments using the Netlib test set are made, which show that this approach is competitive when compared to well established solvers, such as PCx.

Keywords: linear programming, infeasible-interior-point method, optimized choice of parameters.

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

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: IMECC/Unicamp report. October/2016

Download: [PDF]

Entry Submitted: 10/10/2016
Entry Accepted: 10/10/2016
Entry Last Modified: 10/10/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society