In this paper, we study a nonconvex quadratic minimization problem with two quadratic constraints, one of which being convex. We introduce two convex quadratic relaxations (CQRs) and discuss cases, where the problem is equivalent to exactly one of the CQRs. Particularly, we show that the global optimal solution can be recovered from an optimal solution of the CQRs. Through this equivalence, we introduce new conditions under which the problem enjoys strong Lagrangian duality, generalizing the recent condition in the literature. Finally, under the new conditions, we present necessary and sufficient conditions for global optimality of the problem.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020130
Keywords: Quadratically constrained quadratic programming, convex quadratic relaxation, strong duality, SDO-relaxation
@article{RO_2021__55_S1_S2905_0,
author = {Hamdi, Abdelouahed and Taati, Akram and Almaadeed, Temadher A.},
title = {Quadratic problems with two quadratic constraints: convex quadratic relaxation and strong lagrangian duality},
journal = {RAIRO. Operations Research},
pages = {S2905--S2922},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020130},
mrnumber = {4223210},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020130/}
}
TY - JOUR AU - Hamdi, Abdelouahed AU - Taati, Akram AU - Almaadeed, Temadher A. TI - Quadratic problems with two quadratic constraints: convex quadratic relaxation and strong lagrangian duality JO - RAIRO. Operations Research PY - 2021 SP - S2905 EP - S2922 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020130/ DO - 10.1051/ro/2020130 LA - en ID - RO_2021__55_S1_S2905_0 ER -
%0 Journal Article %A Hamdi, Abdelouahed %A Taati, Akram %A Almaadeed, Temadher A. %T Quadratic problems with two quadratic constraints: convex quadratic relaxation and strong lagrangian duality %J RAIRO. Operations Research %D 2021 %P S2905-S2922 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020130/ %R 10.1051/ro/2020130 %G en %F RO_2021__55_S1_S2905_0
Hamdi, Abdelouahed; Taati, Akram; Almaadeed, Temadher A. Quadratic problems with two quadratic constraints: convex quadratic relaxation and strong lagrangian duality. RAIRO. Operations Research, Tome 55 (2021), pp. S2905-S2922. doi: 10.1051/ro/2020130
[1] and , Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint. Math. Program. 173 (2019) 79–116. | MR | DOI
[2] , , and , Solving the trust region subproblem by a generalized eigenvalue problem. SIAM J. Optim. 27 (2017) 269–291. | MR | DOI
[3] and , Second-order cone programming. Math. Program. 95 (2003) 3–51. | MR | Zbl | DOI
[4] and , Strong duality for the CDT subproblem: a necessary and sufficient condition. SIAM J. Optim. 19 (2009) 1735–1756. | MR | Zbl | DOI
[5] and , Quadratic optimization with two ball constraints. Numer. Algebra Control Optim. 10 (2020) 165–175. | MR | DOI
[6] and , Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM J. Optim. 17 (2006) 844–860. | MR | Zbl | DOI
[7] and , Hidden conic quadratic representation of some nonconvex quadratic optimization problems. Math. Program. 143 (2014) 1–29. | MR | Zbl | DOI
[8] and , Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72 (1996) 51–63. | MR | Zbl | DOI
[9] , A note on polynomial solvability of the CDT problem. SIAM J. Optim. 26 (2016) 488–498. | MR | DOI
[10] and , Sequential quadratic programming. Acta Numer. 4 (1995) 1–51. | MR | Zbl | DOI
[11] and , Narrowing the difficulty gap for the Celis–Dennis–Tapia problem. Math. Program. 151 (2015) 459–476. | MR | DOI
[12] , and , Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations. J. Global Optim. 71 (2018) 551–569. | MR | DOI
[13] , and , A trust region strategy for nonlinear equality constrained optimization, edited by , and . In: Numerical Optimization. SIAM, Philadelphia (1985) 71–82. | MR | Zbl
[14] and , On local solutions of the Celis–Dennis–Tapia subproblem. SIAM J. Optim. 10 (1999) 359–383. | MR | Zbl | DOI
[15] , and , Trust Region Methods. SIAM, Philadelphia, PA (2000). | MR | Zbl
[16] , , and , Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint. J. Global Optim. 54 (2012) 275–293. | MR | Zbl | DOI
[17] , and , An algorithm for quadratic optimization with one quadratic constraint and bounds on the variables. Inverse Prob. 14 (1998) 893–901. | MR | Zbl | DOI
[18] and , The trust region subproblem and semidefinite programming. Optim. Methods Softw. 19 (2004) 41–67. | MR | Zbl | DOI
[19] and , Quadratically constrained least squares and quadratic problems. Numer. Math. 59 (1991) 186–197. | MR | Zbl | DOI
[20] , , and , Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9 (1999) 504–525. | MR | Zbl | DOI
[21] and , CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2014) 21–57.
[22] and , A Second-order cone based approach for solving the trust-region subproblem and its variants. SIAM J. Optim. 27 (2017) 1485–1512. | MR | DOI
[23] and , Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity. Preprint arXiv:1312.1398 (2013).
[24] , and , A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil. Pac. J. Optim. 10 (2014) 461–481. | MR | Zbl
[25] and , Strong duality in robust convex programming: complete characterizations. SIAM J. Optim. 20 (2010) 3384–3407. | MR | Zbl | DOI
[26] and , A robust von-Neumann minimax theorem for zero-sum games under bounded payoff uncertainty. Oper. Res. Lett. 39 (2011) 109–114. | MR | Zbl | DOI
[27] and , Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. 147 (2014) 171–206. | MR | Zbl | DOI
[28] and , Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming, SIAM J. Optim. 26 (2016) 1649–1668. | MR | DOI
[29] and , Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29 (2019) 1603–1633. | MR | DOI
[30] , and , SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices. Math. Program. 169 (2018) 531–563. | MR | DOI
[31] and , Canonical forms for hermitian matrix pairs under strict equivalence and congruence. SIAM Rev. 47 (2005) 407–443. | MR | Zbl | DOI
[32] , Some results for quadratic problems with one or two quadratic constraints. Oper. Res. Lett. 43 (2015) 126–131. | MR | DOI
[33] , Exactness conditions for an SDP relaxation of the extended trust region problem. Optim. Lett. 10 (2016) 1141–1151. | MR | DOI
[34] , Generalizations of the trust region problem. Optim. Methods Softw. 2 (1993) 189–209. | DOI
[35] and , Computing a trust region step. SIAM J. Sci. Stat. Comput. 4 (1983) 553–572. | MR | Zbl | DOI
[36] and , Distributed Parameter Systems: Theory and Applications. Clarendon Press (1989). | MR | Zbl
[37] and , The generalized trust region subproblem. Comput. Optim. App. 58 (2014) 273–322. | MR | Zbl | DOI
[38] and , A trust region algorithm for equality constrained optimization. Math. Program. 49 (1991) 189–211. | MR | Zbl | DOI
[39] , and , A new matrix-free algorithm for the large-scale trust-region subproblem. SIAM J. Optim. 11 (2001) 611–646. | MR | Zbl | DOI
[40] , , and , Solving generalized CDT problems via two-parameter eigenvalues. SIAM J. Optim. 26 (2016) 1669–1694. | MR | DOI
[41] and , An efficient algorithm for solving the generalized trust region subproblem. Comput. Appl. Math. 37 (2018) 395–413. | MR | DOI
[42] and , A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality. Comput. Appl. Math. 37 (2018) 329–347. | MR | DOI
[43] , and , Local nonglobal minima for solving large-scale extended trust-region subproblems. Comput. Optim. App. 66 (2017) 223–244. | MR | DOI
[44] and , On cones of nonnegative quadratic functions. Math. Oper. Res. 28 (2003) 246–267. | MR | Zbl | DOI
[45] and , A conjugate gradient-based algorithm for large-scale quadratic programming problem with one quadratic constraint. Comput. Optim. App. 74 (2019) 195–223. | MR | DOI
[46] and , On local non-global minimizers of quadratic optimization problem with a single quadratic constraint. Numer. Funct. Anal. Optim. 41 (2020) 969–1005. | MR | DOI
[47] and , On the tightness of SDP relaxations of QCQPs. Technical Report, arXiv:1911.09195 (2019).
[48] and , New results on quadratic minimization. SIAM J. Optim. 14 (2003) 245–267. | MR | Zbl | DOI
[49] , On a subproblem of trust region algorithms for constrained optimization. Math. Program. 47 (1990) 53–63. | MR | Zbl | DOI
[50] , A dual algorithm for minimizing a quadratic function with two quadratic constraints. J. Comput. Math. 9 (1991) 348–359. | MR | Zbl
[51] , Computing a Celis–Dennis–Tapia trust-region step for equality constrained optimization. Math. Program. 55 (1992) 109–124. | MR | Zbl | DOI
Cité par Sources :
