×

Further development of multiple centrality correctors for interior point methods. (English) Zbl 1168.90643

Summary: This paper addresses the role of centrality in the implementation of interior point methods. We provide theoretical arguments to justify the use of a symmetric neighbourhood, and translate them into computational practice leading to a new insight into the role of re-centering in the implementation of interior point methods. Second-order correctors, such as Mehrotra’s predictor-corrector, can occasionally fail: we derive a remedy to such difficulties from a new interpretation of multiple centrality correctors. Through extensive numerical experience we show that the proposed centrality correcting scheme leads to noteworthy savings over second-order predictor-corrector technique and previous implementations of multiple centrality correctors.

MSC:

90C51 Interior-point methods

Software:

HOPDM; PCx; SDPpack
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Andersen, E.D., Gondzio, J., Mészáros, C., Xu, X.: Implementation of interior point methods for large scale linear programming. In: Terlaky, T. (ed.) Interior Point Methods in Mathematical Programming, pp. 189–252. Kluwer Academic, Dordrecht (1996) · Zbl 0874.90127
[2] Carpenter, T.J., Lustig, I.J., Mulvey, J.M., Shanno, D.F.: Higher-order predictor-corrector interior point methods with application to quadratic objectives. SIAM J. Optim. 3, 696–725 (1993) · Zbl 0794.90043 · doi:10.1137/0803036
[3] Cartis, C.: Some disadvantages of a Mehrotra-type primal–dual corrector interior-point algorithm for linear programming. Technical report 04/27, Numerical Analysis Group, Computing Laboratory, Oxford University (2004) · Zbl 1163.90042
[4] Cartis, C.: On the convergence of a primal–dual second-order corrector interior point algorithm for linear programming. Technical report 05/04, Numerical Analysis Group, Computing Laboratory, Oxford University (2005)
[5] Czyzyk, J., Mehrotra, S., Wright, S.: PCx user guide. Technical report OTC 96/01, Optimization Technology Center (May 1996)
[6] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[7] Gondzio, J.: HOPDM (version 2.12)–a fast LP solver based on a primal–dual interior point method. Eur. J. Oper. Res. 85, 221–225 (1995) · Zbl 0925.90284 · doi:10.1016/0377-2217(95)00163-K
[8] Gondzio, J.: Multiple centrality corrections in a primal–dual method for linear programming. Comput. Optim. Appl. 6, 137–156 (1996) · Zbl 0860.90084
[9] Haeberly, J.-P., Nayakkankuppam, M., Overton, M.: Extending Mehrotra and Gondzio higher order methods to mixed semidefinite-quadratic–linear programming. Optim. Methods Softw. 11, 67–90 (1999) · Zbl 0957.90102 · doi:10.1080/10556789908805748
[10] Jarre, F., Wechs, M.: Extending Merhotra’s corrector for linear programs. Adv. Model. Optim. 1, 38–60 (1999) · Zbl 1115.90395
[11] Lustig, I.J., Marsten, R.E., Shanno, D.F.: On implementing Mehrotra’s predictor–corrector interior-point method for linear programming. SIAM J. Optim. 2, 435–449 (1992) · Zbl 0771.90066 · doi:10.1137/0802022
[12] Mehrotra, S.: On the implementation of a primal–dual interior point method. SIAM J. Optim. 2, 575–601 (1992) · Zbl 0773.90047 · doi:10.1137/0802028
[13] Mehrotra, S., Li, Z.: Convergence conditions and Krylov subspace-based corrections for primal–dual interior-point method. SIAM J. Optim. 15, 635–653 (2005) · Zbl 1077.90078 · doi:10.1137/S1052623403431494
[14] Mizuno, S., Todd, M., Ye, Y.: On adaptive step primal–dual interior-point algorithms for linear programming. Math. Oper. Res. 18, 964–981 (1993) · Zbl 0810.90091 · doi:10.1287/moor.18.4.964
[15] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970) · Zbl 0241.65046
[16] Salahi, M., Peng, J., Terlaky, T.: On Mehrotra-type predictor–corrector algorithms. AdvOl report 2005/4, McMaster University (2005) · Zbl 1165.90569
[17] Tapia, R., Zhang, Y., Saltzman, M., Weiser, A.: The Mehrotra predictor–corrector interior-point method as a perturbed composite Newton method. SIAM J. Optim. 6, 47–56 (1996) · Zbl 0846.65024 · doi:10.1137/0806004
[18] Vavasis, S.A., Ye, Y.: A primal–dual interior point method whose running time depends only on the constraint matrix. Math. Program. 74, 79–120 (1996) · Zbl 0868.90081
[19] Wright, S.J.: Primal–Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.