Predictor-corrector interior-point algorithm for linearly constrained convex programming

Abstract

Active set method and gradient projection method are currently the main approaches for linearly constrained convex programming. Interior-point method is one of the most effective choices for linear programming. In the paper a predictor-corrector interior-point algorithm for linearly constrained convex programming under the predictor-corrector motivation was proposed. In each iteration, the algorithm first performs a predictor-step to reduce the duality gap and then a corrector-step to keep the points close to the central trajectory. Computations in the algorithm only require that the initial iterate be nonnegative while feasibility or strict feasibility is not required. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The results show that the proposed algorithm is stable and robust.

Keywords

linearly constrained convex programming / predictor-corrector interior-point algorithm / numerical experiment

References

[1] MehrotraS. On finding a vertex solution using interior-point methods[J]. Linear Algebra Appl, 1990, 152: 233-253

[2] MehrotraS. On the implementation of a primal-dual interior point method[J]. SIAM J Optim, 1992, 2: 575-601

[3] LustigI J, MaxstenR E, ShannoD F. On the implementing mehrotra’s predictor-corrector interior-point method for linear programming[J]. SIAM J Optim, 1992, 2: 435-449

[4] FletcherRPractical methods of optimization[M], 19872nd endNew York, Wiley Pub

[5] LuciaA, XuJ, D’CoutoG C. Sparse quadratic programming in chemical process optimization [J]. Ann Oper Res, 1993, 42: 55-83

[6] VasantharajanS, ViswanathanJ, BieglerL T. Reduced successive quadratic programming implementation for large-scale optimization problems with smaller degrees of freedom[J]. Comput Chem Engng, 1990, 14: 907-915

[7] DunnJ C. On the convergence of projected gradient processes to singular critical points[J]. J Optim Theory Appl, 1987, 55: 203-216

[8] GafniE M, BertsekasD P. Two-metric projection methods for constrained Optimization[J]. SIAM J Control Optim, 1984, 22: 936-964

[9] WrightS J. An interior-point algorithm for linearly constrained optimization[J]. SIAM J Optim, 1992, 2: 450-473

[10] OrtegaJ M, RheinboldtW CIterative solution of nonlinear equations in several variables[J], 1970, New York, Academic Press

[11] MizunoS, ToddM J, YeYAnticipated behavior of the path following algorithms for linear programming[A], 1989, Ithaca, NY, School of Operations Research and Industrial Engineering, Cornell University

[12] HockW, SchittkowskiKTest examples for nonlinear programming codes[M], 1981, Berlin, Springer