IPRSOCP: A Primal-Dual Interior-Point Relaxation Algorithm for Second-Order Cone Programming

doi:10.1007/s40305-024-00538-z

Abstract

Abstract: Inspired by the smoothing barrier augmented Lagrangian function in Liu et al. (Math Methods Oper Res 96(3):351-382, 2022), we propose a primal-dual interior-point relaxation algorithm for second-order cone programming, called IPRSOCP. Two features of the IPRSOCP algorithm are as follows. One is that the iterative points of the proposed algorithm need not lie inside the interior region, convening the use of warmstart. The other is that an explicit form of the Schur complementmatrix is explored such that the low-rank structure of the Schur complement matrix can be used to improve numerical stability and efficiency. Under suitable assumptions, it is shown that the barrier parameter in the IPRSOCP algorithm tends to zero and the generated sequence of iterations is globally convergent to the solution. Numerical results demonstrate that the IPRSOCP algorithm is competitive with the open-source benchmark solvers, SeDuMi, SDPT3, and ECOS, in terms of robustness and efficiency.

Key words: Second-order cone programming, Interior-point relaxation method, Smoothing barrier augmented Lagrangian function, Schur complement matrix, Global convergence

CLC Number:

Rui-Jin Zhang, Zhao-Wei Wang, Xin-Wei Liu, Yu-Hong Dai. IPRSOCP: A Primal-Dual Interior-Point Relaxation Algorithm for Second-Order Cone Programming[J]. Journal of the Operations Research Society of China, 2026, 14(1): 1-31.

TrendMD

References

[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95(1), 3-51(2003)
[2] 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)
[3] Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769-805(1998)
[4] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)
[5] Cai, Z., Toh, K.C.: Solving second-order cone programming via a reduced augmented system approach. SIAM J. Optim. 17(3), 711-737(2006)
[6] Chen, B., Harker, P.T.: A non-interior-point continuationmethod for linear complementarity problems. SIAM J. Matrix Anal. Appl. 14(4), 1168-1190(1993)
[7] Chen, X.D., Sun, D.F., Sun, J.: Complementarity functions and numerical experiments on some smoothing Newton methods for second-order cone complementarity problems. Comput. Optim. Appl. 25(1), 39-56(2003)
[8] Chi, C.Y., Li, W.C., Lin, C.H.: Convex Optimization for Signal Processing and Communications: from Fundamentals to Applications. CRC Press, Boca Raton (2017)
[9] Chi, X.N., Liu, S.Y.: A one-step smoothing Newton method for second-order cone programming. J. Comput. Appl. Math. 223(1), 114-123(2009)
[10] 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)
[11] De Luca, T., Facchinei, F., Kanzow, C.: A theoretical and numerical comparison of some semismooth algorithms for complementarity problems. Comput. Optim. Appl. 16, 173-205(2000)
[12] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213(2002)
[13] Domahidi, A., Chu, E., Boyd, S.: ECOS: an SOCP solver for embedded systems. In: 2013 European Control Conference, pp. 3071-3076(2013)
[14] El Ghaoui, L., Oustry, F., Lebret, H.: Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9(1), 33-52(1998)
[15] Engelke, S., Kanzow, C.: Predictor-corrector smoothing methods for linear programs with a more flexible update of the smoothing parameter. Comput. Optim. Appl. 23(3), 299-320(2002)
[16] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
[17] Fukushima, M., Luo, Z.Q., Tseng, P.: Smoothing functions for second-order cone complementarity problems. SIAM J. Optim. 12(2), 436-460(2002)
[18] Gill, P.E., Kungurtsev, V., Robinson, D.P.: A shifted primal-dual penalty-barrier method for nonlinear optimization. SIAM J. Optim. 30(2), 1067-1093(2020)
[19] Goldfarb, D., Scheinberg, K.: Product-form Cholesky factorization in interior point methods for second-order cone programming. Math. Program. 103(1), 153-179(2005)
[20] Goldfarb, D., Polyak, R., Scheinberg, K., Yuzefovich, I.: A modified barrier-augmented Lagrangian method for constrained minimization. Comput. Optim. Appl. 14, 55-74(1999)
[21] Gondzio, J.:Warm start of the primal-dualmethod applied in the cutting-plane scheme.Math. Program. 83(1-3), 125-143(1998)
[22] Gondzio, J., González-Brevis, P.: A new warmstarting strategy for the primal-dual column generation method. Math. Program. 152, 113-146(2015)
[23] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15(2), 593-615(2005)
[24] Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342-361(1996)
[25] John, E., Yıldırım, E.A.: Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension. Comput. Optim. Appl. 41(2), 151-183(2008)
[26] Kamath, A.G., Elango, P., Yu, Y., Mceowen, S., Carson III, J.M., Açıkmese, B.: Real-time sequential conic optimization for multi-phase rocket landing guidance. arXiv:2212.00375(2022)
[27] Kanzow, C.: Some noninterior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17(4), 851-868(1996)
[28] Kanzow, C., Ferenczi, I., Fukushima, M.: On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity. SIAM J. Optim. 20(1), 297-320(2009)
[29] 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)
[30] Kong, L.C., Sun, J., Xiu, N.H.: A regularized smoothing Newton method for symmetric cone complementarity problems. SIAM J. Optim. 19(3), 1028-1047(2008)
[31] Kuo, Y.J., Mittelmann, H.D.: Interior point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28, 255-285(2004)
[32] 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)
[33] 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)
[34] Liu, X.W., Dai, Y.H., Huang, Y.K., Sun, J.: A novel augmented Lagrangian method of multipliers for optimization with general inequality constraints. Math. Comput. 92(341), 1301-1330(2023)
[35] Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284(1-3), 193-228(1998)
[36] Monteiro, R.D.: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7(3), 663-678(1997)
[37] Monteiro, R.D., Tsuchiya, T.: Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. Math. Program. 88(1), 61-83(2000)
[38] Narushima, Y., Sagara, N., Ogasawara, H.: A smoothing Newton method with Fischer-Burmeister function for second-order cone complementarity problems. J. Optim. Theory Appl. 149, 79-101(2011)
[39] Odonoghue, B., Chu, E., Parikh, N., Boyd, S.: Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169(3), 1042-1068(2016)
[40] Qi, L.Q., Sun, D.F., Zhou, G.L.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87(1), 1-35(2000)
[41] Skajaa, A., Ye, Y.Y.: A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Math. Program. 150, 391-422(2015)
[42] Smale, S.: Algorithms for solving equations. Proceedings of the International Congress of Mathematicians, Berkeley (1986)
[43] Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11-12, 625-653(1999)
[44] 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)
[45] 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)
[46] Tsuchiya, T.: A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11(1-4), 141-182(1999)
[47] Wright, S.J.: Primal-dual Interior-point Methods. SIAM, Philadelphia (1997)
[48] Xu, S., Burke, J.V.: A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques. Math., Program. 86(1) (1999)
[49] Yildirim, E.A., Wright, S.J.: Warm-start strategies in interior-point methods for linear programming. SIAM J. Optim. 12(3), 782-810(2002)
[50] Zhang, R.J., Liu, X.W., Dai, Y.H.: IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming. Tech. Rep. (2022)
[51] 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)