×

A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones. (English) Zbl 1346.90580

Summary: We propose a Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones by using a wide neighborhood. In the corrector step, we adopt a special strategy, which can ensure the existence of a step size to keep every iteration in the given small neighborhood. By using an elegant analysis, we obtain the iteration bounds for a commutative class of directions. In particular, the iteration bound is \(\mathcal{O}(r\log \varepsilon^{-1})\) for the Nesterov-Todd search direction, and \(\mathcal{O}(r^{3/2}\log \varepsilon^{-1})\) for the \(xs\) and \(sx\) search direction. To our knowledge, the obtained iteration bounds match the currently best known iteration bounds for infeasible-interior-point method. Some preliminary numerical results are provided as well.

MSC:

90C05 Linear programming
90C25 Convex programming
90C51 Interior-point methods

Software:

SDPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Güler, O.: Barrier functions in interior-point methods. Math. Oper. Res. 21, 860-885 (1996) · Zbl 0867.90090 · doi:10.1287/moor.21.4.860
[2] Faraut, J., Korányi, A.: Analysis on Symmetric Cone. Oxford University Press, New York (1994) · Zbl 0841.43002
[3] Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior point algorithm to symmetric cones. Math. Program. 96, 409-438 (2003) · Zbl 1023.90083 · doi:10.1007/s10107-003-0380-z
[4] Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM Publications, Philsdephia, USA (1997) · Zbl 0863.65031 · doi:10.1137/1.9781611971453
[5] Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. Eur. J. Oper. Res. 214, 473-484 (2011) · Zbl 1245.90144 · doi:10.1016/j.ejor.2011.02.022
[6] 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
[7] Muramatsu, M.: On a commutative class of search directions for linear programming over symmetric cones. J. Optim. Theory Appl. 112, 595-625 (2002) · Zbl 0994.90095 · doi:10.1023/A:1017920200889
[8] Rangarajan, B.K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16, 1211-1229 (2006) · Zbl 1131.90043 · doi:10.1137/040606557
[9] Schmieta, S., Alizadeh, F.: Associative and Jordan algebras, and polynomial time interiorpoint algorithms for symmetric cones. Math. Oper. Res. 26, 543-564 (2001) · Zbl 1073.90572 · doi:10.1287/moor.26.3.543.10582
[10] 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
[11] 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
[12] Zhang, Y., Zhang, D.: On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Math. Program. 68, 303-318 (1995) · Zbl 0837.90087 · doi:10.1007/BF01585769
[13] Zhang, J., Zhang, K.: Polynomiality complexity of an interior point algorithm with a second order corrector step for symmetric cone programming. Math. Meth. Oper. Res. 73, 75-90 (2011) · Zbl 1229.90084 · doi:10.1007/s00186-010-0334-1
[14] Ye, Y., Tapia, R.A., Zhang, Y.: A superlinearly convergent O(\sqrt{n}L)\(O(\sqrt{n}L)\)-iteration algorithm for linear programming. Math. Program. 50, 239-258 (1991) · Zbl 0734.90057 · doi:10.1007/BF01594937
[15] 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. Program. 59, 151-162 (1993) · Zbl 0778.90037 · doi:10.1007/BF01581242
[16] Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. 61, 263-280 (1993) · Zbl 0808.90093 · doi:10.1007/BF01582151
[17] Zangiabadi, M., Gu, G., Roos, C.: A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization. J. Optim. Theory Appl. 158, 816-858 (2013) · Zbl 1274.90496 · doi:10.1007/s10957-013-0278-8
[18] Potra, F.A.: On a predictor-corrector method for solving linear programming from infeasible starting points. Reprots on computational mathematics 34, Department of mathematics. The University of Iowa City, IA 52242, USA (1992)
[19] Potra, F.A.: A quadratically convergent infeasible interior-point algorithm for linear programming. Reports on computational mathematics 28, Department of Mathematics. The University of Iowa, Iowa City, IA 52242, USA (1992)
[20] Kojima, M., Shida, M.A., Shindoh, S.: Local convergence of predictor-corrector infeasible-interior-point algorithm for sdps and sdlcps. Math. Program. 80, 129-160 (1998) · Zbl 0897.90183
[21] Ye, Y., Todd, M.J., Mizuno, S.: An O(\sqrt{n}L)\(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53-67 (1994) · Zbl 0799.90087 · doi:10.1287/moor.19.1.53
[22] Zhang, Y.: On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4, 208-227 (1994) · Zbl 0803.90092 · doi:10.1137/0804012
[23] 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
[24] Yang, X., Liu, H., Zhang, Y.: A new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming. Journal of Optimal Theory and Applications (2014) · Zbl 1311.65075
[25] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86, 149-175 (1997) · Zbl 0889.65066 · doi:10.1016/S0377-0427(97)00153-2
[26] Liu, C.: Study on complexity of some interior-point algorithms in conic programming (in chinese). Ph.D. thesis, Xidian University (2012) · Zbl 1274.90389
[27] Yang, X., Liu, H., Liu, C.: A Mehrotra-type predictorCcorrector infeasible-interior-point method with a new one-norm neighborhood for symmetric optimization. J. Comput. Appl. Math. 283, 106-121 (2015) · Zbl 1311.65075 · doi:10.1016/j.cam.2015.01.027
[28] Borchers, B.: Sdplib 1.2, a library of semidefinite programming test problems. Optim. Methods Softw. 11, 683-690 (1999) · Zbl 0973.90522 · doi:10.1080/10556789908805769
[29] Todd, M.J., Toh, K.C., Tütüncü, R.H.: On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. 8, 769-796 (1998) · Zbl 0913.90217 · doi:10.1137/S105262349630060X
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.