IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming
Tóm tắt
We propose an efficient primal-dual interior-point relaxation algorithm based on a smoothing barrier augmented Lagrangian, called IPRSDP, for solving semidefinite programming problems in this paper. The IPRSDP algorithm has three advantages over classical interior-point methods. Firstly, IPRSDP does not require the iterative points to be positive definite. Consequently, it can easily be combined with the warm-start technique used for solving many combinatorial optimization problems, which require the solutions of a series of semidefinite programming problems. Secondly, the search direction of IPRSDP is symmetric in itself, and hence the symmetrization procedure is not required any more. Thirdly, with the introduction of the smoothing barrier augmented Lagrangian function, IPRSDP can provide the explicit form of the Schur complement matrix. This enables the complexity of forming this matrix in IPRSDP to be comparable to or lower than that of many existing search directions. The global convergence of IPRSDP is established under suitable assumptions. Numerical experiments are made on the SDPLIB set, which demonstrate the efficiency of IPRSDP.
Từ khóa
Tài liệu tham khảo
Alizadeh, F., Haeberly, J., Nayakkankuppa, M., Overton, M., Schmieta, S.: SDPPACK User’s Guide–Version 0.9 Beta for Matlab 5.0. New York University (1997)
Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13–51 (1995)
Alizadeh, F., Haeberly, J.P.A., Overton, M.L.: Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8(3), 746–768 (1998)
Antoniou, A., Lu, W.S.: Practical Optimization: Algorithms and Engineering Applications, vol. 19. Springer, New York (2007)
Benson, S.J., Ye, Y.Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10(2), 443–461 (2000)
Borchers, B.: SDPLIB 1.2, a library of semidefinite programming test problems. Optim. Methods Softw. 11(1–4), 683–690 (1999)
Burer, S., Monteiro, R.D.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329–357 (2003)
Burer, S., Monteiro, R.D.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103(3), 427–444 (2005)
Chen, X., Tseng, P.: Non-interior continuation methods for solving semidefinite complementarity problems. Math. Program. 95(3), 431–474 (2003)
Dai, Y.H., Liu, X.W., Sun, J.: A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. J. Ind. Manag. Optim. 16(2), 1009–1035 (2020)
De Simone, C., Rinaldi, G.: A cutting plane algorithm for the max-cut problem. Optim. Methods Softw. 3(1–3), 195–214 (1994)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)
Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle approach for semidefinite cutting plane relaxations of max-cut and equipartition. Math. Program. 105(2), 451–469 (2006)
Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342–361 (1996)
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New York (2012)
Huang, Z.H., Liu, X.H.: Extension of smoothing Newton algorithms to solve linear programming over symmetric cones. J. Syst. Sci. Complex. 24, 195–206 (2011)
Kanzow, C., Nagel, C.: Semidefinite programs: new search directions, smoothing-type methods, and numerical results. SIAM J. Optim. 13(1), 1–23 (2002)
Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7(1), 86–125 (1997)
Li, Y.F., Wen, Z.W., Yang, C., Yuan, Y.X.: A semismooth Newton method for semidefinite programs and its applications in electronic structure calculations. SIAM J. Sci. Comput. 40(6), 4131–4157 (2018)
Lisser, A., Rendl, F.: Graph partitioning using linear and semidefinite programming. Math. Program. 95(1), 91–101 (2003)
Liu, X.W., Dai, Y.H.: A globally convergent primal-dual interior-point relaxation method for nonlinear programs. Math. Comput. 89(323), 1301–1329 (2019)
Liu, X.W., Dai, Y.H., Huang, Y.K.: A primal-dual interior-point relaxation method with global and rapidly local convergence for nonlinear programs. Math. Methods Oper. Res. 96(3), 351–382 (2022)
Lu, C., Liu, Y.F., Zhang, W.Q., Zhang, S.Z.: Tightness of a new and enhanced semidefinite relaxation for MIMO detection. SIAM J. Optim. 29(1), 719–742 (2019)
Luo, Z.Q., Ma, W.K., So, A.M.-C., Ye, Y.Y., Zhang, S.Z.: Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27(3), 20–34 (2010)
Mironowicz, P.: Applications of semidefinite optimization in quantum information protocols. arXiv preprint arXiv:1810.05145 (2018)
Monteiro, R.D.: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7(3), 663–678 (1997)
Monteiro, R.D.: Polynomial convergence of primal-dual algorithms for semidefinite programming based on the Monteiro and Zhang family of directions. SIAM J. Optim. 8(3), 797–812 (1998)
Monteiro, R.D.: First-and second-order methods for semidefinite programming. Math. Program. 97(1), 209–244 (2003)
Monteiro, R.D., Zanjacomo, P.: Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants. Optim. Methods Softw. 11(1–4), 91–140 (1999)
Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior point algorithms to symmetric cones. Math. Program. 96(3), 409–438 (2003)
Siddhu, V., Tayur, S.: Five starter pieces: Quantum information science via semidefinite programs. arXiv preprint arXiv:2112.08276 (2021)
Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11–12, 625–653 (1999)
Todd, M.J.: A study of search directions in primal-dual interior-point methods for semidefinite programming. Optim. Methods Softw. 11(1–4), 1–46 (1999)
Todd, M.J., Toh, K.C., Tütüncü, R.H.: On the Nesterov–Todd direction in semidefinite programming. SIAM J. Optim. 8(3), 769–796 (1998)
Toh, K.C., Todd, M.J., Tütüncü, R.H.: On the implementation and usage of SDPT3-a Matlab software package for semidefinite quadratic linear programming, version 4.0. In: Handbook on Semidefinite. Conic and Polynomial Optimization, pp. 715–754. Springer, Boston (2012)
Wen, Z.W., Goldfarb, D., Yin, W.T.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2(3–4), 203–230 (2010)
Yamashita, H., Tanabe, T.: A primal-dual exterior point method for nonlinear optimization. SIAM J. Optim. 20(6), 3335–3363 (2010)
Yang, L.Q., Sun, D.F., Toh, K.C.: SDPNAL \(+ \): a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3), 331–366 (2015)
Zhang, R.J., Liu, X.W., Dai, Y.H.: IPRQP: a primal-dual interior-point relaxation algorithm for convex quadratic programming. J. Global Optim. 87(2), 1027–1053 (2023)
Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8(2), 365–386 (1998)
Zhao, X.Y., Sun, D.F., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737–1765 (2010)
Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Chordal decomposition in operator-splitting methods for sparse semidefinite programs. Math. Program. 180(1), 489–532 (2020)