Journal of the Operations Research Society of China >

2025 , Vol. 13 >Issue 1: 114 - 141

DOI: https://doi.org/10.1007/s40305-023-00523-y

Monotone Splitting SQP Algorithms for Two-block Nonconvex Optimization Problems with General Linear Constraints and Applications

Expand
  • 1 School of Mathematics and Physics, Center for Applied Mathematics of Guangxi, Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Guangxi Minzu University, Nanning 530006, Guangxi, China;
    2 College of Mathematics and Information Science, Guangxi University, Nanning 530004, Guangxi, China

Received date: 2023-01-28

  Revised date: 2023-06-15

  Online published: 2025-03-20

Fold

Abstract

This work discusses a class of two-block nonconvex optimization problems with linear equality, inequality and box constraints. Based on the ideas of alternating direction method with multipliers (ADMM), sequential quadratic programming (SQP) and Armijo line search technique, we propose a novel monotone splitting SQP algorithm. First, the discussed problem is transformed into an optimization problem with only linear equality and box constraints by introduction of slack variables. Second, the idea of ADMM is used to decompose the traditional quadratic programming (QP) subproblem. In particular, the QP subproblem corresponding to the introduction of the slack variable is simple, and it has an explicit optimal solution without increasing the computational cost. Third, the search direction is generated by the optimal solutions of the subproblems, and the new iteration point is yielded by an Armijo line search with augmented Lagrange function. Fourth, the multiplier is updated by a novel approach that is different from the ADMM. Furthermore, the algorithm is extended to the associated optimization problem where the box constraints can be replaced by general nonempty closed convex sets. The global convergence of the two proposed algorithms is analyzed under weaker assumptions. Finally, some preliminary numerical experiments and applications in mid-to-large-scale economic dispatch problems for power systems are reported, and these show that the proposed algorithms are promising.

Key words： Two-block nonconvex optimization; General linear constraints; Splitting sequential quadratic programming; Alternating direction method of multipliers; Global convergence

Cite this article

Jin-Bao Jian, Guo-Dong Ma, Xiao Xu, Dao-Lan Han . Monotone Splitting SQP Algorithms for Two-block Nonconvex Optimization Problems with General Linear Constraints and Applications[J]. Journal of the Operations Research Society of China, 2025 , 13(1) : 114 -141 . DOI: 10.1007/s40305-023-00523-y

References

[1] Wang, Y., Freedman, M.T., Kung, S.Y., Luo, L.:Probabilistic principal component subspaces:a hierarchical finite mixture model for data visualization. IEEE T. Neural. Networ. 11(3), 625-636(2000)
[2] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.:Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends. Mach. Le. 3(1), 1-122(2011)
[3] Xu, Z.B., Chang, X.Y., Xu, F.M., Zhang, H.:L1/2 regularization:a thresholding representation theory and a fast solver. IEEE T. Neur. Net. Lear. 23(7), 1013-1027(2012)
[4] Zhang, C., Yang, L.F., Jian, J.B.:Two-stage fully distributed approach for unit commitment with consensus ADMM. Electr. Pow. Syst. Res. 181, 106180:1-106180:12(2020)
[5] Glowinski, R., Marrocco, A.:Approximation paréléments finis drdre un et résolution, par pénalisationdualité dúne classe de problèmes de Dirichlet non linéaires. Rev. Fr. Autom. Inform. Rech. Opér. Anal. Numeér. 2, 41-76(1975)
[6] Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17-40(1976)
[7] Peaceman, D., Rachford, J.R.H.:The numerical solution of parabolic and elliptic differential equations. J. Soc. Indust. Appl. Math. 3, 28-41(1955)
[8] He, B.S., Liu, H., Wang, Z.R., Yuan, X.M.:A strictly contractive Peaceman-Rachford splitting method for convex programming. SIAM J. Optim. 24, 1011-1040(2014)
[9] He, B.S., Ma, F., Yuan, X.M.:Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J. Imaging Sci. 9, 1467-1501(2016)
[10] Vapnik, V.N.:The Nature of Statistical Learning Theory. Springer, New York (1995)
[11] Lee, Y.J., Mangasarian, O.L.:SSVM:a smooth support vector machines for classification. Comput. Optim. Appl. 20(1), 5-22(2001)
[12] Chen, C.H., He, B.S., Ye, Y.Y., Yuan, X.M.:The direct extension of ADMM for multi-block convex minimization problems is not necessary convergent. Math. Program. 155, 57-79(2016)
[13] He, B.S., Tao, M., Yuan, X.M.:Convergence rate analysis for the alternating direction method of multipliers with a substitution procedure for separable convex programming. Math. Oper. Res. 42(3), 662-691(2017)
[14] He, B.S., Yuan, X.M.:A class of ADMM-based algorithms for three-block separable convex programming. Comput. Optim. Appl. 70, 791-826(2018)
[15] He, B.S., Xu, S.J., Yuan, X.M.:Extensions of ADMM for separable convex optimization problems with linear equality or inequality constraints. arXiv:2107.01897v2(2021)
[16] Jian, J.B.:A superlinearly convergent implicit smooth SQP algorithm for mathematical programs with nonlinear complementarity constraints. Comput. Optim. Appl. 31(3), 335-361(2005)
[17] Jian, J.B., Tang, C.M., Hu, Q.J., Zheng, H.Y.:A new superlinearly convergent strongly subfeasible sequential quadratic programming algorithm for inequality constrained optimization. Numer. Funct. Anal. Optim. 29(3-4), 376-409(2008)
[18] Solodov, M.V.:Global convergence of an SQP method without boundedness assumptions on any of the iterative sequences. Math. Program. 118(1), 1-12(2009)
[19] Jian, J.B.:Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments (in Chinese). Science Press, Beijing (2010)
[20] Jian, J.B., Hu, Q.J., Tang, C.M.:Superlinearly convergent norm-relaxed sqp method based on active set identification and new line search for constrained Minimax problems. J. Optim. Theory Appl. 163, 859-883(2014)
[21] Schiela, A., Ortiz, J.:An SQP method for equality constrained optimization on Hilbert manifolds. SIAM J. Optim. 31(3), 2255-2284(2021)
[22] Jian, J.B., Lao, Y.X., Chao, M.T., Ma, G.D.:ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization. Oper. Res. Trans. 22(2), 79-92(2018)(in Chinese)
[23] Jian, J.B., Zhang, C., Yin, J.H., Yang, L.F., Ma, G.D.:Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems. J. Optim. Theory Appl. 186(1), 226-247(2020)
[24] Jian, J.B., Liu, P.J., Yin, J.H., Zhang, C., Chao, M.T.:A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application. J. Comput. Appl. Math. 390, 113368(2021)
[25] Jian, J.B., Zhang, C., Yin, J.H.:A Peaceman-Rachford splitting sequential quadratic programming method with double step-lengths for two-block nonconvex optimization (in Chinese). Sci. Sin. Math. 52(12), 1449-1476(2022)
[26] Rockafellar, R.T., Wets, R.J.B.:Variational Analysis. Springer Verlag (2009)
[27] Wood, A.J., Wollenberg, B.F., Sheblé, G.B.:Power Generation, Operation, and Control. Wiley, New York (2014)
[28] Theerthamalai, A., Maheswarapu, S.:An effective non-iterative "λ-logic based" algorithm for economic dispatch of generators with cubic fuel cost function. Int. J. Elec.l Power. 32(5), 539-542(2010)
[29] Wang, H., Banerjee, A.:Bregman alternating direction method of multipliers. In:Advances in Neural Information Processing Systems 27(NIPS 2014), Curran Associates, 2816-2824(2014)
[30] Wang, F.H., Xu, Z.B., Xu, H.K.:Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems. arXiv:1410.8625(2014)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016