A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization. (English) Zbl 1424.90202
Summary: This paper proposes a second-order Mehrotra-type predictor-corrector feasible interior-point algorithm for semidefinite optimization problems. In each iteration, the algorithm computes the Newton search directions through a new form of combination of the predictor and corrector directions. Using the Ai-Zhang wide neighborhood for linear complementarity problems, it is shown that the complexity bound of the algorithm is \(O(\sqrt{n}\log \varepsilon^{-1})\) for the Nesterov-Todd search direction and \(O({n}\log \varepsilon^{-1})\) for the Helmberg-Kojima-Monteiro search directions.
Keywords:
semidefinite optimization; Mehrotra-type predictor-corrector algorithm; polynomial complexitySoftware:
SeDuMiReferences:
| [1] | Ai WB, Zhang SZ. An O(nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J Optimiz 2005; 16: 400-417. · Zbl 1122.90078 · doi:10.1137/040604492 |
| [2] | Alizadeh F. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J Optimiz 1995; 5: 13-51. · Zbl 0833.90087 · doi:10.1137/0805002 |
| [3] | Ben-Tal A, Nemirovski A. Lectures on Modern Convex Optimization. MPS/SIAM Series on Optimization. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics (SIAM), 2001. · Zbl 0986.90032 |
| [4] | Boyd S, Vandenberghe L. Convex Optimization. Cambridge, UK: Cambridge University Press, 2004. 183 · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [5] | Feng Z, Fang L. A wide neighborhood interior-point method with O (nL) iteration-complexity bound for semidefinte programming. Optimization 2010; 59: 1235-1246. · Zbl 1209.65058 · doi:10.1080/02331930903104382 |
| [6] | Helmberg C, Rendl F, Vanderbei RJ, Wolkowicz H. An interior-point method for semidefinite programming. SIAM J Optimiz 1996; 6: 342-361. · Zbl 0853.65066 · doi:10.1137/0806020 |
| [7] | Klerk ED. Aspects of Semidefinite Programming: Interior Point Methods and Selected Applications. Dordrecht, the Netherlands: Kluwer Academic Publishers, 2002. · Zbl 0991.90098 · doi:10.1007/b105286 |
| [8] | Lasserre JB, Prieto-Rumeau T. SDP vs. LP relaxations for the moment approach in some performance evaluation problems. Stoch Models 2004; 20: 439-456. · Zbl 1067.60059 |
| [9] | Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite (√()) · Zbl 1228.90072 · doi:10.1137/080729311 |
| [10] | Lisser A, Rendl F. Graph partitioning using linear and semidefinite programming. Math Program 2003; 95: 91-101. · Zbl 1030.90079 · doi:10.1007/s10107-002-0342-x |
| [11] | Liu C, Liu H. A new second-order corrector interior-point algorithm for semidefinite programming. Math Oper Res 2012; 75: 165-183. · Zbl 1277.90093 · doi:10.1007/s00186-012-0379-4 |
| [12] | Mansouri H. Full-Newton step infeasible interior-point algorithm for SDO problem. Kybernetika 2012; 48: 907-923. · Zbl 1292.90229 |
| [13] | Mansouri H, Roos C. A new full-Newton step O(nL) infeasible interior-point algorithm for semidefinite optimization. Numer Algorithms 2009; 52: 225-255. · Zbl 1180.65079 · doi:10.1007/s11075-009-9270-7 |
| [14] | Monteiro RDC, Zhang Y. A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming. Math Program 1998; 81: 281-299. · Zbl 0919.90109 · doi:10.1007/BF01580085 |
| [15] | Nesterov Y, Nemirovskii A. Interior-Point Polynomial Algorithms in Convex Programming. Philadelphia, PA, USA: SIAM, 1994. · Zbl 0824.90112 · doi:10.1137/1.9781611970791 |
| [16] | Pirhaji M, Mansouri H, Zangiabadi M. An O (nL) wide neighborhood interior-point algorithm for semidefinite optimization. Comput Appl Math 2015; 34: 1-13. · Zbl 1359.90153 |
| [17] | Salahi M, Amiri NM. Polynomial time second order Mehrotra-type predictor-corrector algorithms. Appl Math Comput 2006; 183: 646-658. · Zbl 1112.65057 |
| [18] | Salahi M, Peng J, Terlaky T. On Mehrtora Type Predictor-Corrector Algorithms. Technical Report. Hamilton, ON, Canada: McMaster University, 2005. · Zbl 1165.90569 |
| [19] | Sturm JF. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim Method Softw 1999; 11: 625-653. · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [20] | Todd MJ, Toh KC, Tutuncu RH. On the Nesterov-Todd direction in semidefinite programming. SIAM J Optimiz 1998; 8: 769-796. · Zbl 0913.90217 · doi:10.1137/S105262349630060X |
| [21] | Vandenberghe L, Boyd S. A primal-dual potential reduction method for problems involving matrix inequalities. Math Program 1995; 69: 205-236. · Zbl 0857.90104 · doi:10.1007/BF01585558 |
| [22] | Wang GQ, Bai YQ. A new primal-dual path-following interior-point algorithm for semidefinite optimization. J Math Anal Appl 2009; 353: 339-349. · Zbl 1172.90011 · doi:10.1016/j.jmaa.2008.12.016 |
| [23] | Wolkowicz H, Saigal R, Vandenberghe L. Handbook of Semidefinite Programming: Theory, Algorithms and Applications. Norwell, MA, USA: Springer, 1999. · Zbl 0962.90001 |
| [24] | 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 2013; 91: 1082-1096. · Zbl 1297.90112 · doi:10.1080/00207160.2013.827784 |
| [25] | Yang X, Liu H, Zhang Y. An interior-point method with a new iterative scheme. Appl Math Mech 2014; 35: 1063-1070 (in Chinese). |
| [26] | Zhang M. A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization. J Syst Sci Complex 2012; 25: 1108-1121. · Zbl 1305.90329 · doi:10.1007/s11424-012-0317-9 |
| [27] | Zhang Y. On extending some primal-dual algorithms from linear programming to semidefinite programming. SIAM J Optimiz 1998; 8: 365-386. · Zbl 0913.65050 · doi:10.1137/S1052623495296115 |
| [28] | Zhang Y, Zhang D. On polynomiality of the Mehrotra-type predictor corrector interior-point algorithms. Math Program 1995; 68: 303-318. · Zbl 0837.90087 · doi:10.1007/BF01585769 |
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.
