In this paper, we propose an interior-point algorithm based on a wide neighborhood for convex quadratic semidefinite optimization problems. Using the Nesterov-Todd direction as the search direction, we prove the convergence analysis and obtain the polynomial complexity bound of the proposed algorithm. Although the algorithm belongs to the class of large-step interior-point algorithms, its complexity coincides with the best iteration bound for short-step interior-point algorithms. The algorithm is also implemented to demonstrate that it is efficient.
Mohammad Pirhaji, Maryam Zangiabadi, Hossien Mansouri, Ali Nakhaei, Ali Shojaeifard
. A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization[J]. Journal of the Operations Research Society of China, 2020
, 8(1)
: 145
-164
.
DOI: 10.1007/s40305-018-0219-1
[1] Karmarkar, N.:New polynomial-time algorithm for linear programming. Combinattorica 4, 373-395(1984)
[2] Nie, J., Yuan, Y.:A predictor-corrector algorithm for QSDP combining Dikin-type and Newton centering steps. Ann. Oper. Res. 103, 115-133(2001)
[3] Toh, K.:An inexact primal-dual path following algorithm for convex quadratic SDP. Math. Program. 112, 221-254(2008)
[4] Xiao, X., Zhang, L., Zhang, J.:A smoothing Newton method for a type of inverse semidefinite quadratic programming problem. J. Comput. Appl. Math. 223, 485-498(2009)
[5] Achache, M., Guerra, L.:A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimizationJ. Appl. Math. Comput. 231, 581-590(2014)
[6] Ai, W., Zhang, S.:An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J. Optim. 16, 400-417(2005)
[7] Ai, W.:Neighborhood-following algorithms for linear programming. Sci. China Ser. A 47, 812-820(2004)
[8] Li, Y., Terlaky, T.:A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√n log(Tr(X0S0)/ε)) iteration complexity. SIAM J. Optim. 20, 2853-2875(2010)
[9] Liu, H., Yang, X., Liu, C.:A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. J. Optim. Theory Appl. 158, 796-815(2013)
[10] Liu, H., Yang, X., Liu, C.:A Mehrotra-type predictor-corrector infeasible-interior point method with a new one-norm neighborhood for symmetric optimization. J. Comput. Appl. Math. 283, 106-121(2015)
[11] Liu, C., Wu, D., Shang, Y.:A new infeasible interior-point algorithm based on wide neighborhood for symmetric cone programming. J. Oper. Res. Soc. China 4, 147-165(2016)
[12] Yang, X., Liu, H., Zhang, Y.:A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming. J. Comput. Math. 91, 1082-1096(2013)
[13] Horn, R., Johnson, C.:Topics in Matrix Analysis. Cambridge University Press, New York (1991)
[14] Zhang, Y.:On extending some primal-dual algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8, 365-386(1998)
[15] Kojima, M., Shindoh, S., Hara, S.:Interior-point methods for the monotone semidefinite linear complementarity problems. SIAM J. Optim. 7, 86-125(1997)
[16] Alizadeh, F., Haeberly, J., Overton, M.:Primal-dual interior-point methods for semidefinite programming:convergence rates, stability and numerical results. SIAM J. Optim. 8, 746-768(1998)
[17] Monteiro, R.D.C.:Polynomial convergence of primal-dual algorithm for semidefinite programming based on Monteiro and Zhang family of direction. SIAM J. Optim. 8, 797-812(1998)
[18] Nesterov, Y., Todd, M.:Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324-364(1998)
[19] Klerk, E.:Interior Point Methods for Semidefinite Programming. Dissertation, University of Pretoria (1970)
[20] Schmieta, S., Alizadeh, F.:Extension of primal-dual interior point algorithms to symmetric cones. Math. Program. Ser. A 96, 409-438(2003)
[21] Wang, G.Q., Yu, C.J., Teo, K.L.:A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization. Appl. Math. Comput. 221, 329-343(2013)
[22] Chun-liang, F., Yan-qin, B., Jing, Z., Wei, X.:New primal-dual interior-point algorithm for solving semidefinite optimization. Commun. Appl. Math. Comput. (2014). https://doi.org/10.3969/j.issn.1006-6330.2013.03.009
[23] Liu, C., Liu, H.:A new second-order corrector interior-point algorithm for semidefinite programming. Math. Methods Oper. Res. 75, 165-183(2012)
