×

zbMATH — the first resource for mathematics

Narrowing the difficulty gap for the Celis-Dennis-Tapia problem. (English) Zbl 1328.90095
Summary: We study the Celis-Dennis-Tapia (CDT) problem: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that occurs when the Hessian of the Lagrangian is indefinite at all Karush-Kuhn-Tucker points. We prove new sufficient and necessary conditions both for local and global optimality, based on copositivity, giving a complete characterization in the degenerate case.

MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
Software:
mctoolbox
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ai, W; Zhang, S, Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J. Optim., 19, 1735-1756, (2009) · Zbl 1187.90290
[2] Beck, A; Eldar, Y, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17, 844-860, (2006) · Zbl 1128.90044
[3] 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, Portland, Oregon, USA (2014) · Zbl 1334.90130
[4] Bomze, I.M.: Copositivity for second-order optimality conditions in general smooth optimization problems. Preprint NI13033-POP, Isaac Newton Institute, Cambridge UK (2013) · Zbl 0801.65057
[5] Bomze, IM, Copositivity conditions for global optimality in indefinite quadratic programming problems, Czechoslov. J. Oper. Res., 1, 7-19, (1992) · Zbl 0972.90051
[6] Borwein, JM, Necessary and sufficient conditions for quadratic minimality, Numer. Funct. Anal. Optim., 5, 127-140, (1982) · Zbl 0507.90091
[7] Burer, S; Anstreicher, K, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23, 432-451, (2013) · Zbl 1298.90062
[8] Celis, M.R., Dennis, Jr., J.E., Tapia, R.A.: A trust region strategy for nonlinear equality constrained optimization. In: Numerical Optimization, 1984 (Boulder, Colo., 1984), pp. 71-82. SIAM, Philadelphia, PA (1985) · Zbl 1172.90501
[9] Chen, X-D; Yuan, Y-X, On local solutions of the celis-dennis-tapia subproblem, SIAM J. Optim., 10, 359-383, (1999) · Zbl 0957.65060
[10] Chen, X-D; Yuan, Y-X, Strong duality for the CDT subproblem: a necessary and sufficient condition, J. Comput. Math., 19, 113-124, (2009)
[11] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods. In: MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2000) · Zbl 0958.65071
[12] Contesse, LB, Une caractérisation complète des minima locaux, Numer. Math., 34, 315-332, (1980) · Zbl 0422.90061
[13] Dickinson, PJC; Gijben, L, On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57, 403-415, (2014) · Zbl 1330.90103
[14] Ding, B.: A Parametric Solution for Local and Global Optimization. PhD thesis, University of Waterloo, Ontario, Canada (1996)
[15] Grigoriev, D; Pasechnik, DV, Polynomial time computing over quadratic maps I: sampling in real algebraic sets, Comput. Complex., 14, 20-52, (2005) · Zbl 1082.14065
[16] Higham, N.J.: Accuracy and stability of numerical algorithms. In: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, Second edition (2002) · Zbl 1011.65010
[17] Hiriart-Urruty, J-B, Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints, J. Global Optim., 21, 445-455, (2001) · Zbl 1172.90501
[18] Jargalsaikhan, B, Indefinite copositive matrices with exactly one positive eigenvalue or exactly one negative eigenvalue, Electron. J. Linear Algebra, 26, 754-761, (2013) · Zbl 1283.15106
[19] Jeyakumar, V., Li, G.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program., to appear. 2013, doi:10.1007/s10107-013-0716-2 · Zbl 1297.90105
[20] Jeyakumar, V; Lee, GM; Li, G, Alternative theorems for quadratic inequality systems and global quadratic optimization, SIAM J. Optim., 20, 983-1001, (2009) · Zbl 1197.90315
[21] Lewis, A.S., Overton, M.L.: Nonsmooth optimization via quasi-Newton methods. Math. Program. 141(1-2, Ser. B), 135-163 (2013) · Zbl 1280.90118
[22] Majthay, A, Optimality conditions for quadratic programming, Math. Program., 1, 359-365, (1971) · Zbl 0246.90038
[23] Martínez, JM, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 159-176, (1994) · Zbl 0801.65057
[24] Murty, KG; Kabadi, SN, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39, 117-129, (1987) · Zbl 0637.90078
[25] Nesterov, Y; Wolkowicz, H; Ye, Y; Wolkowicz, H (ed.); Saigal, R (ed.); Vandenberghe, L (ed.), Nonconvex quadratic optimization, 361-420, (2000), New York
[26] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006) · Zbl 1104.65059
[27] Peng, J; Yuan, Y-X, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7, 579-594, (1997) · Zbl 0891.90150
[28] Pólik, I; Terlaky, T, A survey of the S-lemma, SIAM Rev., 49, 371-418, (2007) · Zbl 1128.90046
[29] Yang, B., Burer, S.: A two-variable analysis of the two-trust-region subproblem. Preprint, submitted to SIAM J. Optim., http://www.optimization-online.org/DB_HTML/2013/07/4126.html (2013) · Zbl 1333.90087
[30] Ye, Y; Zhang, S, New results on quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064
[31] Yuan, Y.-X.: On a subproblem of trust region algorithms for constrained optimization. Math. Program. 47(1, (Ser. B)), 53-63 (1990) · Zbl 0711.90062
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.