A Second-Order Cone Relaxation-Based Branch-and-Bound Algorithm for Complex Quadratic Programs on Acyclic Graphs

doi:10.1007/s40305-023-00506-z

Journal of the Operations Research Society of China ›› 2025, Vol. 13 ›› Issue (4): 989-1017.doi: 10.1007/s40305-023-00506-z

Previous Articles Next Articles

A Second-Order Cone Relaxation-Based Branch-and-Bound Algorithm for Complex Quadratic Programs on Acyclic Graphs

Yang-He Liu¹, Ying-Zhe Xu¹, Cheng Lu¹, Zhi-Bin Deng^2,3

1 School of Economics and Management, North China Electric Power University, Beijing 102206, China;
2 School of Economics and Management, University of Chinese Academy of Sciences, Beijing 100190, China;
3 MOE Social Science Laboratory of Digital Economic Forecasts and Policy Simulation, University of Chinese Academy of Sciences, Beijing 100190, China

Received:2022-10-26 Revised:2023-08-24 Online:2025-12-30 Published:2025-12-19
Contact: Cheng Lu E-mail:lucheng1983@163.com
Supported by:
Cheng Lu’s research was supported by the National Natural Science Foundation of China (No. 12171151). Zhi-Bin Deng’s research was supported by the National Natural Science Foundation of China (No. T2293774), Fundamental Research Funds for the Central University (No.E2ET0808X2), and a grant from MOE Social Science Laboratory of Digital Economic Forecasts and Policy Simulation at UCAS.

Abstract

Abstract: Complex quadratically constrained quadratic programs (QCQPs) with underlying acyclic graph structures have special interests in some important practical applications. In this paper, we propose a new second-order cone relaxation for complex QCQPs, and prove some sufficient conditions under which the proposed relaxation is tight. Then, based on the proposed second-order cone relaxation, a branch-and-bound algorithm is developed. The main feature of the proposed branch-and-bound algorithm is that some complex variables are selected with their bounds on modules or phase angles partitioned in the branching procedure. Numerical results indicate that the proposed branch-and-bound algorithm runs faster than Baron on randomly generated test instances, and is also effective in solving some publicly available test instances of optimal power flow problems.

Key words: Complex quadratic optimization, Second-order cone relaxation, Branch-and-bound algorithm

CLC Number:

Yang-He Liu, Ying-Zhe Xu, Cheng Lu, Zhi-Bin Deng. A Second-Order Cone Relaxation-Based Branch-and-Bound Algorithm for Complex Quadratic Programs on Acyclic Graphs[J]. Journal of the Operations Research Society of China, 2025, 13(4): 989-1017.

TrendMD

References

[1] Low, S.H.: Convex relaxation of optimal power flow-part I: formulations and equivalence. IEEE Trans. Control Netw. 1(1), 15–27 (2014)
[2] Low, S.H.: Convex relaxation of optimal power flow-part Ⅱ: exactness. IEEE Trans. Control Netw. 1(2), 177–189 (2014)
[3] Zimmerman, R.D., Murillo-Sánchez, C.E., Thomas, R.J.: MATPOWER: steady-state operations, planning and analysis tools for power systems research and education. IEEE Trans. Power Syst. 26(1), 12–19 (2011)
[4] Gershman, A.B., Sidiropoulos, N.D., Shahbazpanahi, S., Bengtsson, M., Ottersten, B.: Convex optimization-based beamforming: from receive to transmit and network designs. IEEE Signal Process. Mag. 27(3), 62–75 (2010)
[5] Luo, Z.-Q., Ma, W.-K., So, A.M.-C., Ye, Y., Zhang, S.: Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27(3), 20–34 (2010)
[6] Zhang, S., Huang, Y.: Complex quadratic optimization and semidefinite programming. SIAM J. Optim. 16(3), 871–890 (2006)
[7] Bose, S., Gayme, D.F., Chandy, K.M., Low, S.H.: Quadratically constrained quadratic programs on acyclic graphs with application to power flow. IEEE Trans. Control Netw. 2(3), 278–287 (2015)
[8] Lavaei, J., Tse, D., Zhang, B.: Geometry of power flows and optimization in distribution networks. IEEE Trans. Netw. Syst. 29(2), 572–583 (2014)
[9] Lehmann, K., Grastien, A., Van Hentenryck, P.: AC-feasibility on tree networks is NP-Hard. IEEE Trans. Power Syst. 31(1), 798–801 (2016)
[10] Sojoudi, S., Lavaei, J.: Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure. SIAM J. Optim. 24(4), 1746–1778 (2014)
[11] Azuma, G., Fukuda, M., Kim, S., Yamashita, M.: Exact SDP relaxations of quadratically constrained quadratic programs with forest structures. J. Global Optim. 82, 243–262 (2022)
[12] Jin, Q., Tian, Y., Deng, Z., Fang, S.-C.: Exact computable representation of some second-order cone constrained quadratic programming problems. J. Oper. Res. Soc. China 1, 107–134 (2013)
[13] Kim, S., Kojima, M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26, 143–154 (2003)
[14] Sturm, J.F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28(2), 246–267 (2003)
[15] Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14(1), 245–267 (2003)
[16] Grone, R., Johnson, C.R., Sá, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58, 109–124 (1984)
[17] Lu, C., Deng, Z., Zhang, W.-Q., Fang, S.-C.: Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming. J. Global Optim. 70, 171–187 (2018)
[18] Lu, C., Liu, Y.-F., Zhou, J.:AnenhancedSDRbasedglobalalgorithmfornonconvexcomplexquadratic programs with signal processing applications. IEEE Open J. Signal Process. 1, 120–134 (2020)
[19] Chen, C., Atamtürk, A., Oren, S.S.: A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables. Math. Program. 165(2), 549–577 (2017)
[20] Mosek ApS 2022. http://www.mosek.com.
[21] Bao, X., Sahinidis, N.V., Tawarmalani, M.: Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim. Method Softw. 24(4–5), 485–504 (2009)
[22] Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)
[23] Kocuk, B., Dey, S.S., Sun, X.A.: Inexactness of SDP relaxation and valid inequalities for optimal power flow. IEEE Trans. Power Syst. 31(1), 642–651 (2016)

A Second-Order Cone Relaxation-Based Branch-and-Bound Algorithm for Complex Quadratic Programs on Acyclic Graphs

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	Xin-Rui Li, Ya-Kui Huang. A Note on R-Linear Convergence of Nonmonotone Gradient Methods [J]. Journal of the Operations Research Society of China, 2025, 13(1): 313-325.
[2]	Shan Jiang, Ka-Meng Nip. An Enhanced Conic Reformulation for Capacity-Constrained Assortment Optimization Under the Mixture of Multinomial Logit Model [J]. Journal of the Operations Research Society of China, 2024, 12(3): 757-771.
[3]	Jia-Bin Zhou, Yan-Qin Bai, Yan-Ru Guo, Hai-Xiang Lin. Intuitionistic Fuzzy Laplacian Twin Support Vector Machine for Semi-supervised Classification [J]. Journal of the Operations Research Society of China, 2022, 10(1): 89-112.
[4]	Julien Collonge. Necessary Optimality Conditions for Semi-vectorial Bi-level Optimization with Convex Lower Level: Theoretical Results and Applications to the Quadratic Case [J]. Journal of the Operations Research Society of China, 2021, 9(3): 691-712.
[5]	Yong Xia. A Survey of Hidden Convex Optimization [J]. Journal of the Operations Research Society of China, 2020, 8(1): 1-28.
[6]	Qian-Qian Gao, Yan-Qin Bai, Ya-Ru Zhan. Quadratic Kernel-Free Least Square Twin Support Vector Machine for Binary Classification Problems [J]. Journal of the Operations Research Society of China, 2019, 7(4): 539-559.