×

A superlinearly convergent wide-neighborhood predictor-corrector interior-point algorithm for linear programming. (English) Zbl 1374.90378

Summary: In this paper we propose a new predictor-corrector algorithm with superlinear convergence in a wide neighborhood for linear programming problems. We let the centering parameter in a predictor step is chosen adaptively, which is different from other algorithms in the same wide neighborhood. The choice is a key for the local convergence of the new algorithm. In addition, we use the classical affine scaling direction as a part in a corrector step, not in a predictor step, which contributes to the complexity result. We prove that the new algorithm has a polynomial complexity of \(O(\sqrt{n}L)\), and the duality gap sequence is superlinearly convergent to zero, under the assumption that the iterate points sequence is convergent. Finally, numerical tests indicate its effectiveness.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49M15 Newton-type methods
65K15 Numerical methods for variational inequalities and related problems

Software:

LIPSOL; McIPM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wright, S.J.: Primal-dual interior-point methods. SIAM, Philadephia (1997) · Zbl 0863.65031 · doi:10.1137/1.9781611971453
[2] Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1997) · Zbl 0943.90070
[3] Potra, F.A., Wright, S.J.: Interior-point methods. J. Comput. Appl. Math. 24, 281-302 (2000) · Zbl 0967.65078 · doi:10.1016/S0377-0427(00)00433-7
[4] Güler, O., Ye, Y.: Convergence behavior of interior-point algorithms. Math. Progr. 60, 215-228 (1993) · Zbl 0803.90087 · doi:10.1007/BF01580610
[5] Zhang, Y., Tapia, R.A., Dennis, J.E.: On the Superlinear and quadratic convergence of primal-dual interior-point linear programming algorithms. SIAM J. Optim. 2, 304-323 (1992) · Zbl 0763.90066 · doi:10.1137/0802015
[6] Zhang, Y., Tapia, R.A.: Superlinear and quadratic convergence of primal-dual interior point algorithms for linear programming revisited. J. Optim. Theory Appl. 73, 229-242 (1992) · Zbl 0792.90078 · doi:10.1007/BF00940179
[7] Zhang, Y., Tapia, R.A.: A superlinearly convergent polynomial primal-dual interior-point algorithm for linear programming. SIAM J. Optim. 3, 118-133 (1993) · Zbl 0781.90067 · doi:10.1137/0803006
[8] Mizuno, S., Todd, M.J., 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
[9] Ye, Y., Güler, O., Tapia, R.A., Zhang, Y.: A quadratically convergent \[O(\sqrt{n}L)O\](\sqrt{n}L)-iteration algorithm for linear programming. Math. Progr. 59, 151-162 (1993) · Zbl 0778.90037 · doi:10.1007/BF01581242
[10] Roos, C., Peng, J., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2002) · Zbl 1136.90045
[11] Ai, W., Zhang, S.: An \[O(\sqrt{n}L)O\](\sqrt{n}L) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J. Optim. 16, 400-417 (2005) · Zbl 1122.90078 · doi:10.1137/040604492
[12] Liu, C., Liu, H., Cong, W.: An \[O(\sqrt{n}L)O\](\sqrt{n}L) iteration primal-dual second-order corrector algorithm for linear programming. Optim. Lett. 5(4), 729-743 (2011) · Zbl 1269.90058 · doi:10.1007/s11590-010-0242-6
[13] Liu, C., Liu, H., Liu, X.: Polynomial convergence of second-order Mehrotra-type predictor-corrector algorithms over symmetric cones. J. Optim. Theory Appl. 154, 949-965 (2012) · Zbl 1268.90128 · doi:10.1007/s10957-012-0018-5
[14] Liu, H., Liu, X., Liu, C.: Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem. Appl. Numer. Math. 62, 1685-1700 (2012) · Zbl 1262.65067 · doi:10.1016/j.apnum.2012.05.009
[15] Liu, H., Yang, X., Liu, C.: A new wide neighborhood primal-dual infeasible interior-point method for symmetric cone programming. J. Optim. Theory Appl. 158, 796-815 (2013) · Zbl 1274.90389 · doi:10.1007/s10957-013-0303-y
[16] Feng, Z., Fang, L.: A new \[O(\sqrt{n}L)O\](\sqrt{n}L)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming. J. Comput. Appl. Math. 256, 65-76 (2014) · Zbl 1314.65082 · doi:10.1016/j.cam.2013.07.011
[17] Potra, F.A.: Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM J. Optim. 24, 1-28 (2014) · Zbl 1291.90314 · doi:10.1137/120884341
[18] Yang, X., Liu, H., Zhang, Y.: A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighborhood for semi-definite programming. Int. J. Comput. Math. 91, 1082-1096 (2014) · Zbl 1297.90112 · doi:10.1080/00207160.2013.827784
[19] Zhang, Y.: Solving large-scale linear programs by interior-point methods under the MATLAB environment. Optim. Methods Softw. 10, 1-31 (1999) · Zbl 0916.90208 · doi:10.1080/10556789808805699
[20] Zhu X., Peng J., Terlaky T. and Zhang G.: On implementing self-regular proximity based feasible IPMs. Technical report 2003-02-01. http://www.cas.mcmaster.ca/oplab/publication (2003) · Zbl 1122.90078
[21] Cartis, C.: On the convergence of a primal-dual second-0rder corrector interior point algorithm for linear programming. Transpl. Proc. 41(8), 2949-2951 (2005)
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.