Two Mehrotra-type predictor-corrector interior point algorithms are proposed for solving symmetric cone optimization (SCO) problems, using the Euclidean Jordan algebra. The algorithms produce sequences of iterates in the wide neighborhood of the central path. We establish
iteration complexity bound for the Nesterov-Todd (NT) scaling direction. To our knowledge, this is the best complexity result obtained so far for interior-point methods over wide neighborhood. We demonstrate the computational efficiency of the proposed algorithms by numerical test results.
References
[1]
Nesterov, Y. and Nemirovskii, A. (1994) Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611970791
[2]
Faybusovich, L. (1997) Euclidean Jordan Algebras and Interior-Point Algorithms. Positivity, 1, 331-357. https://doi.org/10.1023/a:1009701824047
[3]
Asadi, S., Mansouri, H., Darvay, Z., Lesaja, G. and Zangiabadi, M. (2019) A Long-Step Feasible Predictor-Corrector Interior-Point Algorithm for Symmetric Cone Optimization. Optimization Methods and Software, 34, 336-362. https://doi.org/10.1080/10556788.2018.1528248
[4]
Feng, Z. and Fang, L. (2014) A New-Iteration Predictor-Corrector Algorithm with Wide Neighborhood for Semidefinite Programming. Journal of Computational and Applied Mathematics, 256, 65-76.
[5]
Pirhaji, M. and Mansouri, M.H. (2017) An Wide Neighborhood Interior Point Algorithm for Semidefinite Optimization. Journal of Computational and Applied Mathematics, 36, 145-157.
[6]
Schmieta, S.H. and Alizadeh, F. (2003) Extension of Primal-Dual Interior Point Algorithms to Symmetric Cones. Mathematical Programming, 96, 409-438. https://doi.org/10.1007/s10107-003-0380-z
[7]
Liu, H., Yang, X. and Liu, C. (2013) A New Wide Neighborhood Primal-Dual Infeasible-Interior-Point Method for Symmetric Cone Programming. Journal of Optimization Theory and Applications, 158, 796-815. https://doi.org/10.1007/s10957-013-0303-y
[8]
Sayadi Shahraki, M., Mansouri, H. and Zangiabadi, M. (2017) Two Wide Neighborhood Interior-Point Methods for Symmetric Cone Optimization. Computational Optimization and Applications, 68, 29-55. https://doi.org/10.1007/s10589-017-9905-x
[9]
Sayadi Shahraki, M., Mansouri, H., Zangiabadi, M. and Mahdavi-Amiri, N. (2018) A Wide Neighborhood Primal-Dual Predictor-Corrector Interior-Point Method for Symmetric Cone Optimization. Numerical Algorithms, 78, 535-552. https://doi.org/10.1007/s11075-017-0387-9
[10]
Shahraki, M.S., Mansouri, H. and Delavarkhalafi, A. (2022) A Wide Neighbourhood Predictor-Corrector Infeasible-Interior-Point Algorithm for Symmetric Cone Programming. Optimization Methods and Software, 37, 2103-2120. https://doi.org/10.1080/10556788.2022.2060970
[11]
Mehrotra, S. (1992) On the Implementation of a Primal-Dual Interior Point Method. SIAM Journal on Optimization, 2, 575-601. https://doi.org/10.1137/0802028
[12]
Zhang, Y. and Zhang, D. (1995) On Polynomiality of the Mehrotra-Type Predictor-Corrector Interior-Point Algorithms. Mathematical Programming, 68, 303-318. https://doi.org/10.1007/bf01585769
[13]
Zhang, J. and Zhang, K. (2011) Polynomial Complexity of an Interior Point Algorithm with a Second Order Corrector Step for Symmetric Cone Programming. Mathematical Methods of Operations Research, 73, 75-90. https://doi.org/10.1007/s00186-010-0334-1
[14]
Ai, W. and Zhang, S. (2005) An Iteration Primal-Dual Path-Following Method, Based on Wide Neighborhoods and Large Updates, for Monotone LCP. SIAM Journal on Optimization, 16, 400-417.
[15]
Liu, C., Shang, Y. and Liu, H. (2016) An Iteration Mehrotra-Type Predictor-Corrector Algorithm for Monotone Linear Complementarity Problem. Optimization Letters, 10, 619-634.
[16]
Faraut, J. and Korányi, A. (1994) Analysis on Symmetric Cones. Oxford University Press.
[17]
Faybusovich, L. (1997) Linear Systems in Jordan Algebras and Primal-Dual Interior-Point Algorithms. Journal of Computational and Applied Mathematics, 86, 149-175. https://doi.org/10.1016/s0377-0427(97)00153-2
[18]
Nesterov, Y.E. and Todd, M.J. (1998) Primal-Dual Interior-Point Methods for Self-Scaled Cones. SIAM Journal on Optimization, 8, 324-364. https://doi.org/10.1137/s1052623495290209
[19]
Ai, W. (2004) Neighborhood-Following Algorithms for Linear Programming. Science in China Series A, 47, 812-820.
[20]
Gu, G., Zangiabadi, M. and Roos, C. (2011) Full Nesterov-Todd Step Infeasible Interior-Point Method for Symmetric Optimization. European Journal of Operational Research, 214, 473-484. https://doi.org/10.1016/j.ejor.2011.02.022
[21]
Liu, C. (2012) Study on Complexity of Some Interior-Point Algorithms in Conic Programming. Ph.D. Thesis, Xidian University.
[22]
Sturm, J.F. (1999) Using Sedumi 1.02, a Matlab Toolbox for Optimization over Symmetric Cones. Optimization Methods and Software, 11, 625-653. https://doi.org/10.1080/10556789908805766
[23]
Todd, M.J., Toh, K.C. and Tütüncü, R.H. (1998) On the Nesterov-Todd Direction in Semidefinite Programming. SIAM Journal on Optimization, 8, 769-796. https://doi.org/10.1137/s105262349630060x
