×

An \(O(\sqrt nL)\) wide neighborhood interior-point algorithm for semidefinite optimization. (English) Zbl 1359.90153

Summary: In this paper, we propose a primal-dual interior-point method for semidefinite optimization problems. The algorithm is based on a new class of search directions and the Ai-Zhang’s wide neighborhood for monotone linear complementarity problems. The theoretical complexity of the new algorithm is calculated. It is investigated that the proposed algorithm has polynomial iteration complexity \(O(\sqrt nL)\) and coincides with the best known iteration bound for semidefinite optimization problems.

MSC:

90C51 Interior-point methods
90C22 Semidefinite programming

Software:

SeDuMi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ai W (2004) Neighborhood-following algorithm for linear programming. Sci China Ser A 47:812-820 · Zbl 1081.90040 · doi:10.1360/02ys0141
[2] Ai W, Zhang SZ (2005) 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 · Zbl 1122.90078 · doi:10.1137/040604492
[3] Alizadeh F (1991) Combinatorial optimization with interior-point methods and semi-definite matrices. Ph.D. thesis, Computer Science Department, University of Minnesota, Minneapolis · Zbl 0773.90047
[4] Alizadeh F (1995) Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J Optim 5:13-51 · Zbl 0833.90087 · doi:10.1137/0805002
[5] Boyd S, El Ghaoui L, Feron E, Balakrishnan V (1994) Linear matrix inequalities in system and control theory. SIAM, Philadelphia · Zbl 0816.93004 · doi:10.1137/1.9781611970777
[6] Feng ZZ, Fang L, Guoping H (2014) An \[O(\sqrt{n}L)O\](\sqrt{n}L) iteration primal-dual path-following method, based on wide neighbourhood and large update, for second-order cone programming. Optimization 63(5):679-691 · Zbl 1295.65069 · doi:10.1080/02331934.2012.678849
[7] Feng ZZ, Fang L (2014) 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 · Zbl 1314.65082 · doi:10.1016/j.cam.2013.07.011
[8] Halicka M, Klerk E, Roos C (2002) On the convergence of the central path in semidefinite optimization. SIAM J Optim 12(40):1090-1099 · Zbl 1035.90100 · doi:10.1137/S1052623401390793
[9] Helmberg C, Rendl F, Vanderbei RJ, Wolkowicz H (1996) An interior-point method for semidefinite programming. SIAM J Optim 6:342-361 · Zbl 0853.65066 · doi:10.1137/0806020
[10] Klerk E (2002) Aspects of semidefinite programming: interior point methods and selected applications. Kluwer, Dordrecht · Zbl 0991.90098 · doi:10.1007/b105286
[11] Kojima M, Shindoh M, Hara S (1997) Interior point methods for the monotone linear complementarity problem in symmetric matrices. SIAM J Optim 7:86-125 · Zbl 0872.90098 · doi:10.1137/S1052623494269035
[12] Li Y, Terlaky T (2010) A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with \[O(\sqrt{n}\log \frac{Tr(X^0S^0)}{\epsilon })O\](\sqrt{n}logTr(X0S0)ϵ) iteration complexity. SIAM J Optim 20:2853-2875 · Zbl 1228.90072 · doi:10.1137/080729311
[13] Liu C, Liu H (2012) A new second-order corrector interior-point algorithm for semi-definite programming. J Math Oper Res 75:165-183 · Zbl 1277.90093 · doi:10.1007/s00186-012-0379-4
[14] Liu H, Yang X, Liu C (2013) A new wide neighborhood primal-dual infeasible interior-point method for symetric cone programming. J Optim Theory Appl 158:796-815 · Zbl 1274.90389 · doi:10.1007/s10957-013-0303-y
[15] Mansouri H, Roos C (2009) A new full-Newton step \[O(nL)O\](nL) infeasible interior-point algorithm for semidefinite optimization. Numer Algorithm 52(2):225-255 · Zbl 1180.65079 · doi:10.1007/s11075-009-9270-7
[16] Mansouri H (2012) Full-Newton step infeasible interior-point algorithm for SDO problems. J Kybern 48(5):907-923 · Zbl 1292.90229
[17] Mehrotra S (1992) On the implementation of a primal-dual interior point method. SIAM J Optim 2:575-601 · Zbl 0773.90047 · doi:10.1137/0802028
[18] Monteiro RDC, Zhang Y (1998) A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinie programming. Math Program 81:281-299 · Zbl 0919.90109
[19] Nesterov YE, Nemirovskii AS (1994) Interior-point polynomial algorithms in convex programming. SIAM, Philadelphia · Zbl 0824.90112 · doi:10.1137/1.9781611970791
[20] Nesterov YE, Todd MJ (1998) Primal-dual interior-point methods for self-scaled cones. SIAM J Optim 8:324-364 · Zbl 0922.90110 · doi:10.1137/S1052623495290209
[21] Potra FA (2014) 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):1-28 · Zbl 1291.90314 · doi:10.1137/120884341
[22] Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim Method Soft 11:625-653 · Zbl 0973.90526 · doi:10.1080/10556789908805766
[23] Vandenberghe L, Boyd S (1995) A primal-dual potential reduction method for problems involving matrix inequalities. Math Program 69:205-236 · Zbl 0857.90104
[24] Wang GQ, Bai YQ, Gao XY, Wang DZ (2014) Improved complexity analysis of full Nesterove-Todd step interior-point methods for semidefinite optimization. J Optim Theory Appl. doi:10.1007/s10957-014-0619-2 · Zbl 0913.65050
[25] Wang GQ, Bai YQ (2009) A new primal-dual path-following interior-point algorithm for semidefinite optimization. J Math Anal Appl 353(1):339-349 · Zbl 1172.90011 · doi:10.1016/j.jmaa.2008.12.016
[26] Wolkowicz H, Saigal R, Vandenberghe L (1999) Handbook of semidefinite programming: theory, algorithms and applications. Kluwer, Norwell · Zbl 0951.90001
[27] Yang X, Liu H, Zhang Y (2013) A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighborhood for semidefinte programming. Int J Comput Math 91(5):1082-1096 · Zbl 1297.90112 · doi:10.1080/00207160.2013.827784
[28] Zhang Y (1998) On extending some primal-dual algorithms from linear programming to semidefinite programming. SIAM J Optim 8:365-386 · Zbl 0913.65050 · doi:10.1137/S1052623495296115
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.