A Wide Neighborhood Second-order Predictor-corrector Interior-point Algorithm for Semidefinite Optimization with Modified Corrector Directions

• Autorzy: Kheirfam B. , Mohamadi-Sangachin M.

Identyfikatory

DOI

10.3233/FI-2017-1543

• Języki publikacji: EN

Abstrakty

EN

In this paper, we present a new second-order predictor-corrector interior-point method for semidefinite optimization. The algorithm is based on the wide neighborhood of the central path and modified corrector directions. In the corrector step, we derive the step size and corrector directions which guarantee that new iterate lies in the wide neighborhood. The iteration complexity bound is O(√nlog X0•S0/ɛ) for the Nesterov-Todd direction, which coincides with the best known complexity results for semidefinite optimization. Some numerical results are provided as well.

Słowa kluczowe

EN

iteration complexity bound; predictor-corrector interior-point method; second-order methods; semidefinite optimization; wide neighborhood

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 4
• Strony: 327--346
• Opis fizyczny: Bibliogr. 31 poz., tab.

Twórcy

autor

Kheirfam B.

• Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran

autor

Mohamadi-Sangachin M.

• Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran

Bibliografia

• [1] Boyd S, Ghaoui L, Feron E, Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. SIAM Philadelphia PA. ISBN 0-89871-334-X.
• [2] Alizadeh F. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 1995. 5(1):13–51. doi:10.1137/0805002.
• [3] Lewis AS, Overton ML. Eigenvalue optimization. Acta Numerica, 1996. pp. 149–190.
• [4] Nesterov YE, Todd MJ. Self-scaled barriers and interior-point methods for convex programming. Mathematics of Operations Research, 1997. 22(1):1–42.
• [5] Nesterov YE, Todd MJ. Primal-dual interior-point methods for self-scaled cones. SIAM Journal on Optimization, 1998. 8(2):324–364. doi:10.1137/S1052623495290209.
• [6] Monteiro RDC, Zhang Y. A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming. Mathematical Programming, 1998. 81(3):281–299. doi:10.1007/BF01580085.
• [7] Wang G, Bai Y, Gao X, Wang D. Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization. Journal of Optimization Theory and Applications, 2015. 165(1):242–262. doi:10.1007/s10957-014-0619-2.
• [8] Kheirfam B. An Adaptive Infeasible Interior-point Algorithm with Full Nesterov-Todd Step for Semidefinite Optimization. Journal of Mathematical Modelling and Algorithms in Operations Research, 2015. 14(1):55–66. doi:10.1007/s10852-014-9257-9.
• [9] Kheirfam B. Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numerical Algorithms, 2012. 61(4):659–680. doi:10.1007/s11075-012-9557-y.
• [10] Monteiro RDC. Primal-dual path-following algorithms for semidefenite programming. SIAM Journal on Optimization, 1997. 7(3):663–678. doi:10.1137/S1052623495293056.
• [11] Monteiro RDC. Polynomial convergence of primal-dual algorithms for semidefnite programming based on Monteiro and Zhang family of directions. SIAM Journal on Optimization, 1998. 8(3):797–812. doi:10.1137/S1052623496308618.
• [12] Monteiro RDC. First- and second-order methods for semidefnite programming. Mathematical Programming, 2003. 97(1):209–244. doi:10.1007/s10107-003-0451-1.
• [13] Sturm JF. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. SIAM Journal on Computing, 1999. 11(1-4):625–653. doi:10.1080/10556789908805766.
• [14] Todd MJ, Toh KC, Tütüncü R. On the Nesterov-Todd direction in semidefinite programming. SIAM Journal on Optimization, 1998. 8(3):769–796. doi:10.1137/S105262349630060X.
• [15] Zhang YZ. On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Mathematical Programming, 1995. 68(1):303–318. doi:10.1007/BF01585769.
• [16] Ai W, Zhang S. An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM Journal on Optimization, 2005. 16(2):400–417. doi:10.1137/040604492.
• [17] Feng Z, Fang L. A wide neighborhood interior-point method with O(√nL) iteration-complexity bound for semidefinite programming. Optimization, 1235–1246. 59(8):2010. doi:org/10.1080/02331930903104382.
• [18] Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√n log […] iteration complexity. SIAM Journal on Optimization, 2010. 20(6):2853–2875. doi:10.1137/080729311.
• [19] Feng Z, Fang L. A new O(√nL)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming. Journal of Computational and Applied Mathematics, 2014. 256:65–76. doi:org/10.1016/j.cam.2013.07.011.
• [20] Liu C, Liu H. A new second-order corrector interior-point algorithm for semidefinite programming. Mathematical Methods of Operations Research, 2012. 75(2):165–183. doi:10.1007/s00186-012-0379-4.
• [21] Zhang M. A second-order Mehrotra-type predictor-corrector algorithm for semidefinite optimization. Journal of Systems Science and Complexity, 2012. 25(6):1108–1121. doi:10.1007/s11424-012-0317-9.
• [22] Yang X, Liu H, Zhang Y. A second-order Mehrotra-tye predictor-corrector algorithm with a new neighborhood for semi-definite programming. International Journal of Computer Mathematics, 2014. 91(5):1082–1096. doi:org/10.1080/00207160.2013.827784.
• [23] Kheirfam B. An arc-search interior point method in the N∞ neighborhood for symmetric optimization. Fundamenta Informaticae, 2016. 146(3):255–269. doi:10.3233/FI-2016-1385.
• [24] Kheirfam B. A predictor-corrector infeasible-interior-point algorithm for semidefinite optimization in awide neighborhood. Fundamenta Informaticae, 2017. 152(1):33–50. doi:10.3233/FI-2017-1511.
• [25] Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM Journal on Optimization, 1998. 8(2):365–386. doi:10.1137/S1052623495296115.
• [26] Kojima M, Shindoh S, Hara S. Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM Journal on Optimization, 1997. 7(1):86–125. doi:10.1137/S1052623494269035.
• [27] Nesterov Y, Nemirovski A. Interior Point Methods in Convex Programming: Theory and Applications. SIAM Philadelphia PA., 1994. ISBN 978-0-89871-319-0. doi:10.1137/1.9781611970791.
• [28] Halicka M, de Klerk E, Roos C. On the convergence of the central path in semidefinite optimization. SIAM Journal on Optimization, 2002. 12(4):1090–1099. doi:10.1137/S1052623401390793.
• [29] Horn RA, Johnson CR. Matrix analysis. Cambridge University Press, New York. ISBN 978-0521386326.
• [30] Roos C, Terlaky T, Vial JP. Interior point methods for linear optimization. Springer, Boston, MA. ISBN 978-0-387-26379-3.
• [31] Helmberg C, Rendl F, Vanderbei RJ, Wolkowicz H. An interior-point method for semidefinite programming. SIAM Journal on Optimization, 1996. 6(2):342–361. doi:10.1137/0806020.