A Predictor-corrector Infeasible-interior-point Algorithm for Semidefinite Optimization in a Wide Neighborhood

• Autorzy: Kheirfam B.

Identyfikatory

DOI

10.3233/FI-2017-1511

• Języki publikacji: EN

Abstrakty

EN

In this paper, we propose a predictor-corrector infeasible interior-point algorithm for semidefinite optimization based on the Nesterov-Todd scaling scheme. In each iteration, the algorithm computes the new iterate using a new combination of the predictor and corrector directions. Using the Ai-Zhang's wide neighborhood for linear complementarity problems, and extended to semidefinite optimization by Li and Terlaky, it is shown that the iteration complexity bound of the algorithm is O(n^5/4 log ɛ^-1 1), where n is the dimension of the problem and ɛ is the required precision.

Słowa kluczowe

EN

semidefinite optimization; wide neighborhood; infeasible-interior-point method; predictorcorrector method; polynomial complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 1
• Strony: 33--50
• Opis fizyczny: Bibliogr.32 poz.

Twórcy

autor

Kheirfam B.

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

Bibliografia

• [1] Boyd LFE S Ghaoui, 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] Nesterov Y, Nemirovsky 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.
• [4] Ye Y. A class of projective transformations for linear programming. SIAM Journal on Computing, 1990; 19(3):457–466. doi:10.1137/0219030.
• [5] Nesterov YE, Todd MJ. Self-scaled barriers and interior-point methods for convex programming. Mathematics of Operations Research, 1997;22(1):1–42.
• [6] 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.
• [7] Kheirfam B. A full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular proximity. The ANZIAM Journal, 2011;53(1):48–67. doi:10.1017/S144618111200003X.
• [8] Kheirfam B. Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step. Numerical Algorithms, 2012;59(4):589–606. doi:10.1007/s11075-011-9506-1.
• [9] 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.
• [10] Kheirfam B. A corrector-predictor path-following algorithm for semidefinite optimization. Asian-European Journal of Mathematics, 2014;7(2):1450028 (15 pages). doi:org/10.1142/S1793557114500284.
• [11] Kojima M, Shida M, Shindoh S. Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Mathematical Programming, 1998;80(2):129–160. doi:10.1007/BF01581723.
• [12] Luo ZQ, Sturm JF, Zhang S. Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming. SIAM Journal on Optimization, 1998;8(1):59–81. doi:10.1137/S1052623496299187.
• [13] Mehrotra S. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, 1992;2(4):575–601. doi:10.1137/0802028.
• [14] Monteiro RDC. Primal-dual path-following algorithms for semidefenite programming. SIAM Journal on Optimization, 1997;7(3):663–67. doi:10.1137/S1052623495293056.
• [15] 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.
• [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] Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√nlog tr(X0S0)) iteration complexity. SIAM Journal on Optimization, 2010; 20(6):2853–2875. doi:10.1137/080729311.
• [18] Potra FA. Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM Journal on Optimization, 2014;24(1):1–28. doi:10.1137/120884341.
• [19] Feng Z, Fang L. A wide neighborhood interior-point method with O(√nL) iteration-complexity bound for semidefinite programming. Optimization, 2010;59(8):1235–1246 doi:org/10.1080/02331930903104382.
• [20] 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.
• [21] 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.
• [22] 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.
• [23] Rangarajan BK. Polynomial convergence of infeasible interior-point methods over symmetric cones. SIAM Journal on Optimization, 2006;16(4):1211–1229. doi:10.1137/040606557.
• [24] Liu H, Yang X, Liu C. A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. Journal of Optimization Theory and Applications, 2013;158(3):796–815. doi:10.1007/s10957-013-0303-y.
• [25] Yang X, Liu H, Liu C. A Mehrotra-type predictor-corrector infeasible-interior-point method with a new one-norm neighborhood for symmetric optimization. Journal of Computational and Applied Mathematics, 2015;283:106–121. doi:org/10.1016/j.cam.2015.01.027.
• [26] 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.
• [27] DeKlerk E. Aspects of Semidefinite Programming. Applied Optimization. Kluwer Academic, Dordrecht. ISBN 978-1402005473.
• [28] Wolkowicz H, Saigal R, Vandenberghe L. Handbook of semidefinite Programming, Theory, Algorithm, and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands. ISBN 978-1-4615-4381-7.
• [29] Monteiro RD, Zhang Y. A unified analysis for a class of long-step primal-dual path-following interiorpoint algorithms for semidefinite programming. Mathematical Programming, 1998;81(3):281–299. doi:10.1007/BF01580085.
• [30] 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.
• [31] 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.
• [32] Schmieta SH, Alizadeh F. Extension of primal-dual interior-point algorithms to symmetric cones. Mathematical Programming, 2003;96(3):409–438. doi:10.1007/s10107-003-0380-z.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).