Exactness Conditions for Semidefinite Programming Relaxations of Generalization of the Extended Trust Region Subproblem

References

• [1] Ben-Tal A, den Hertog D (2014) Hidden conic quadratic representation of some nonconvex quadratic optimization problems. Math. Programming 143(1-2):1–29.Crossref, Google Scholar
• [2] Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2 (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [3] Ben-Tal A, Teboulle M (1996) Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Programming 72(1):51–63.Crossref, Google Scholar
• [4] Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [5] Bienstock D, Michalka A (2014) Polynomial solvability of variants of the trust-region subproblem. Chekur C, ed. Proc. Twenty-Fifth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 380–390.Google Scholar
• [6] Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [7] Burer S, Anstreicher KM (2013) Second-order-cone constraints for extended trust-region subproblems. SIAM J. Optim. 23(1):432–451.Crossref, Google Scholar
• [8] Burer S, Yang B (2015) The trust region subproblem with non-intersecting linear constraints. Math. Programming 149(1-2):253–264.Crossref, Google Scholar
• [9] Burer S, Ye Y (2020) Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. Math. Programming 181(1):1–17.Crossref, Google Scholar
• [10] Conn AR, Gould NI, Toint PL (2000) Trust Region Methods, vol. 1 (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [11] Fallahi S, Salahi M, Karbasy SA (2018) On SOCP/SDP formulation of the extended trust region subproblem. Preprint, submitted July 20, https://arxiv.org/abs/1807.07815.Google Scholar
• [12] Feng JM, Lin GX, Sheu RL, Xia Y (2012) Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint. J. Global Optim. 54(2):275–293.Crossref, Google Scholar
• [13] Fujie T, Kojima M (1997) Semidefinite programming relaxation for nonconvex quadratic programs. J. Global Optim. 10(4):367–380.Crossref, Google Scholar
• [14] Hazan E, Koren T (2016) A linear-time algorithm for trust region problems. Math. Programming 158(1-2):363–381.Crossref, Google Scholar
• [15] Ho-Nguyen N, Kilinç-Karzan F (2017) A second-order cone based approach for solving the trust-region subproblem and its variants. SIAM J. Optim. 27(3):1485–1512.Crossref, Google Scholar
• [16] Hsia Y, Sheu RL (2013) Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity. Preprint, submitted December 5, https://arxiv.org/abs/1312.1398.Google Scholar
• [17] Huang K, Sidiropoulos ND (2016) Consensus-ADMM for general quadratically constrained quadratic programming. IEEE Trans. Signal Processing 64(20):5297–5310.Crossref, Google Scholar
• [18] Jeyakumar V, Li G (2014) Trust-region problems with linear inequality constraints: Exact sdp relaxation, global optimality and robust optimization. Math. Programming 147(1-2):171–206.Crossref, Google Scholar
• [19] Jeyakumar V, Li G (2018) Exact second-order cone programming relaxations for some nonconvex minimax quadratic optimization problems. SIAM J. Optim. 28(1):760–787.Crossref, Google Scholar
• [20] Jiang R, Li D (2016) Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming. SIAM J. Optim. 26(3):1649–1668.Crossref, Google Scholar
• [21] Jiang R, Li D (2019) Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29(2):1603–1633.Crossref, Google Scholar
• [22] Jiang R, Li D (2020) A linear-time algorithm for generalized trust region subproblems. SIAM J. Optim. 30(1):915–932.Crossref, Google Scholar
• [23] Jiang R, Li D, Wu B (2018) Socp reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices. Math. Programming 169(2):531–563.Crossref, Google Scholar
• [24] Locatelli M (2016) Exactness conditions for an SDP relaxation of the extended trust region problem. Optim. Lett. 10(6):1141–1151.Crossref, Google Scholar
• [25] Luo H, Chen Y, Zhang X, Li D (2020) Effective algorithms for optimal portfolio deleveraging problem with cross-impact. Preprint, submitted December 14, https://arxiv.org/abs/2012.07368.Google Scholar
• [26] Martínez JM (1994) Local minimizers of quadratic functions on Euclidean balls and spheres. SIAM J. Optim. 4(1):159–176.Crossref, Google Scholar
• [27] Moré JJ (1993) Generalizations of the trust region problem. Optim. Methods Software 2(3-4):189–209.Crossref, Google Scholar
• [28] Moré JJ, Sorensen DC (1983) Computing a trust region step. SIAM J. Sci. Statist. Comput. 4(3):553–572.Crossref, Google Scholar
• [29] Nesterov Y (2013) Introductory Lectures on Convex Optimization: A Basic Course, vol. 87 (Springer, New York).Google Scholar
• [30] Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming, vol. 13 (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [31] Pardalos PM (1991) Global optimization algorithms for linearly constrained indefinite quadratic problems. Comput. Math. Appl. 21(6):87–97.Crossref, Google Scholar
• [32] Pólik I, Terlaky T (2007) A survey of the S-lemma. SIAM Rev. 49(3):371–418.Crossref, Google Scholar
• [33] Rendl F, Wolkowicz H (1997) A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Programming 77(1):273–299.Crossref, Google Scholar
• [34] Stern RJ, Wolkowicz H (1995) Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM J. Optim. 5(2):286–313.Crossref, Google Scholar
• [35] Sturm JF, Zhang S (2003) On cones of nonnegative quadratic functions. Math. Oper. Res. 28(2):246–267.Link, Google Scholar
• [36] Wang AL, Kilinç-Karzan F (2022) The generalized trust region subproblem: Solution complexity and convex hull results. Math. Programming 191(2):445–486.Crossref, Google Scholar
• [37] Yakubovich VA (1971) S-procedure in nonlinear control theory. Vestnik Leningrad University 4(1):73–93 [English translation; original Russian publication in Vestnik Leningradskogo Universiteta, Seriya Matematika, Leningrad, Russia, 1971, 62–77].Google Scholar
• [38] Yang B, Burer S (2016) A two-variable approach to the two-trust-region subproblem. SIAM J. Optim. 26(1):661–680.Crossref, Google Scholar
• [39] Ye Y (1992) A new complexity result on minimization of a quadratic function with a sphere constraint. Floudas CA, Pardalos PM, eds. Recent Advances in Global Optimization (Princeton University Press, Princeton, NJ), 19–31.Google Scholar
• [40] Ye Y, Zhang S (2003) New results on quadratic minimization. SIAM J. Optim. 14(1):245–267.Crossref, Google Scholar