×

zbMATH — the first resource for mathematics

Quadratic programs with hollows. (English) Zbl 1401.90147
Summary: Let \(\mathcal {F}\) be a quadratically constrained, possibly nonconvex, bounded set, and let \(\mathcal {E}_1, \dots , \mathcal {E}_l\) denote ellipsoids contained in \(\mathcal {F}\) with non-intersecting interiors. We prove that minimizing an arbitrary quadratic \(q(\cdot )\) over \(\mathcal {G}:= \mathcal {F}{\setminus } \cup _{k=1}^\ell {{\mathrm{int}}}(\mathcal {E}_k)\) is no more difficult than minimizing \(q(\cdot )\) over \(\mathcal {F}\) in the following sense: if a given semidefinite-programming (SDP) relaxation for \(\min \{ q(x) : x \in \mathcal {F}\}\) is tight, then the addition of \(l\) linear constraints derived from \(\mathcal {E}_1, \dots , \mathcal {E}_l\) yields a tight SDP relaxation for \(\min \{ q(x) : x \in \mathcal {G}\}\). We also prove that the convex hull of \(\{ (x,xx^T) : x \in \mathcal {G}\}\) equals the intersection of the convex hull of \(\{ (x,xx^T) : x \in \mathcal {F}\}\) with the same \(l\) linear constraints. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed-integer nonconvex quadratic programming.

MSC:
90C20 Quadratic programming
90C22 Semidefinite programming
90C25 Convex programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstreicher, KM; Burer, S, Computable representations for convex hulls of low-dimensional quadratic forms, Math. Program., 124, 33-43, (2010) · Zbl 1198.90311
[2] Beck, A; Eldar, YC, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17, 844-860, (2006) · Zbl 1128.90044
[3] Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003) · Zbl 1030.15022
[4] Bienstock, D., Michalka, A.: Polynomial solvability of variants of the trust-region subproblem. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 380-390. doi:10.1137/1.9781611973402.28 · Zbl 0846.49017
[5] Buchheim, C; Traversi, E, On the separation of split inequalities for non-convex quadratic integer programming, Discret. Optim., 15, 1-14, (2015) · Zbl 1308.90120
[6] Burer, S, A gentle, geometric introduction to copositive optimization, Math. Program., 151, 89-116, (2015) · Zbl 1327.90162
[7] Burer, S; Anstreicher, KM, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23, 432-451, (2013) · Zbl 1298.90062
[8] Burer, S; Letchford, AN, Unbounded convex sets for non-convex mixed-integer quadratic programming, Math. Program., 143, 231-256, (2014) · Zbl 1291.90146
[9] Burer, S; Yang, B, The trust region subproblem with non-intersecting linear constraints, Math. Program., 149, 253-264, (2015) · Zbl 1308.90121
[10] Conn, A., Gould, N., Toint, P.: Trust Region Methods. Society for Industrial and Applied Mathematics. Philadelphia, PA (2000). doi:10.1137/1.9780898719857
[11] D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: On interval-subgradient and no-good cuts. Oper. Res. Let. 38(5), 341-345 (2010). doi:10.1016/j.orl.2010.05.010. http://www.sciencedirect.com/science/article/pii/S0167637710000738 · Zbl 1202.90238
[12] Hiriart-Urruty, J.B., Lemaréchal, C.: Fundamentals of Convex Analysis, 1st edn. Springer, Berlin Heidelberg (2001). doi:10.1007/978-3-642-56468-0 · Zbl 0998.49001
[13] Jeyakumar, V; Li, G, Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Math. Program., 147, 171-206, (2014) · Zbl 1297.90105
[14] Martínez, JM, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 159-176, (1994) · Zbl 0801.65057
[15] Moré, JJ, Generalizations of the trust region problem, Optim. Methods Softw., 2, 189-209, (1993)
[16] Nesterov, Y.E., Nemirovskii, A.S.: Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, Philadelphia (1994) · Zbl 0824.90112
[17] Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), pp. 339-358 (1998). http://www.jstor.org/stable/3690515 · Zbl 0977.90051
[18] Pong, T; Wolkowicz, H, The generalized trust region subproblem, Comput. Optim. Appl., 58, 273-322, (2014) · Zbl 1329.90100
[19] Rendl, F; Wolkowicz, H, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program., 77, 273-299, (1997) · Zbl 0888.90137
[20] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970) · Zbl 0193.18401
[21] Stern, RJ; Wolkowicz, H, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5, 286-313, (1995) · Zbl 0846.49017
[22] Sturm, JF; Zhang, S, On cones of nonnegative quadratic functions, Math. Oper. Res., 28, 246-267, (2003) · Zbl 1082.90086
[23] Tunçel, L, On the Slater condition for the sdp relaxations of nonconvex sets, Oper. Res. Let., 29, 181-186, (2001) · Zbl 0993.90075
[24] Ye, Y; Zhang, S, New results on quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.