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

Expand
  • 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 date: 2022-10-26

  Revised date: 2023-08-24

  Online published: 2025-12-19

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

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.

Cite this article

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 . DOI: 10.1007/s40305-023-00506-z

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)
Options
Outlines

/