×

zbMATH — the first resource for mathematics

On local non-global minimizers of quadratic optimization problem with a single quadratic constraint. (English) Zbl 07191112
Summary: In this paper, we consider the nonconvex quadratic optimization problem with a single quadratic constraint. First we give a theoretical characterization of the local non-global minimizers. Then we extend the recent characterization of the global minimizer via a generalized eigenvalue problem to the local non-global minimizers. Finally, we use these results to derive an efficient algorithm that finds the global minimizer of the problem with an additional linear inequality constraint.
Reviewer: Reviewer (Berlin)
MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
Software:
GQTPAR; HSL-VF05
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adachi, S.; Nakatsukasa, Y., Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint, Math. Program., 173, 1-2, 79-116 (2019) · Zbl 1411.90246
[2] Ben-Tal, A.; Hertog, D. D., Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143, 1-2, 1-29 (2014) · Zbl 1295.90036
[3] Ben-Tal, A.; Teboulle, M., Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72, 1, 51-63 (1996) · Zbl 0851.90087
[4] Fallahi, S.; Salahi, M.; Terlaky, T., Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint, Optimization, 67, 1, 55-65 (2018) · Zbl 1398.90116
[5] Feng, J.-M.; Lin, G.-X.; Sheu, R.-L.; Xia, Y., Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint, J. Glob. Optim., 54, 2, 275-293 (2012) · Zbl 1281.90032
[6] Jiang, R.; Li, D., Novel reformulations and efficient algorithms for the generalized trust region subproblem, SIAM J. Optim., 29, 2, 1603-1633 (2019) · Zbl 1421.90105
[7] Jiang, R.; Li, D.; Wu, B., SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices, Math. Program., 169, 2, 531-563 (2018) · Zbl 1390.90416
[8] Moré, J. J., Generalizations of the trust region problem, Optim. Methods Softw., 2, 3-4, 189-209 (1993)
[9] Pong, T. K.; Wolkowicz, H., The generalized trust region subproblem, Comput. Optim. Appl., 58, 2, 273-322 (2014) · Zbl 1329.90100
[10] Salahi, M.; Taati, A., An efficient algorithm for solving the generalized trust region subproblem, Comput. Appl. Math., 37, 1, 395-413 (2018) · Zbl 1393.90098
[11] Ye, Y.; Zhang, S., New results on quadratic minimization, SIAM J. Optim., 14, 1, 245-267 (2003) · Zbl 1043.90064
[12] Ai, W.; Zhang, S., Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J. Optim., 19, 4, 1735-1756 (2009) · Zbl 1187.90290
[13] Heinkenschloss, M., On the solution of a two ball trust region subproblem, Math. Program., 64, 1-3, 249-276 (1994) · Zbl 0819.90067
[14] Jeyakumar, V.; Li, G., Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Math. Program., 147, 1-2, 171-206 (2014) · Zbl 1297.90105
[15] Peng, J. M.; Yuan, Y., Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7, 3, 579-594 (1997) · Zbl 0891.90150
[16] Sakaue, S.; Nakatsukasa, Y.; Takeda, A.; Iwata, S., Solving generalized CDT problems via two-parameter eigenvalues, SIAM J. Optim., 26, 3, 1669-1694 (2016) · Zbl 1346.49050
[17] Salahi, M.; Taati, A., A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality, Comput. Appl. Math., 37, 1, 329-347 (2018) · Zbl 1393.90097
[18] Salahi, M.; Taati, A.; Wolkowicz, H., Local nonglobal minima for solving large-scale extended trust-region subproblems, Comput. Optim. Appl., 66, 2, 223-244 (2017) · Zbl 1391.90496
[19] Locatelli, M., Some results for quadratic problems with one or two quadratic constraints, Oper. Res. Lett., 43, 2, 126-131 (2015) · Zbl 1408.90224
[20] Conn, A. R.; Gould, N. I. M.; Toint, P. L., Trust Region Methods (2000), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 0958.65071
[21] Yuan, Y., Recent advances in trust region algorithms, Math. Program., 151, 1, 249-281 (2015) · Zbl 1317.65141
[22] Adachi, S.; Iwata, S.; Nakatsukasa, Y.; Takeda, A., Solving the trust region subproblem by a generalized eigenvalue problem, SIAM J. Optim., 27, 1, 269-291 (2017) · Zbl 1359.49009
[23] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19, 1, 41-67 (2004) · Zbl 1070.65041
[24] Gould, N. I.; Lucidi, S.; Roma, M.; Toint, P. L., Solving the trust-region subproblem using the lanczos method, SIAM J. Optim., 9, 2, 504-525 (1999) · Zbl 1047.90510
[25] Gould, N. I.; Robinson, D. P.; Thorne, H. S., On solving trust-region and other regularised subproblems in optimization, Math. Prog. Comput., 2, 1, 21-57 (2010) · Zbl 1193.65098
[26] Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 3, 553-572 (1983) · Zbl 0551.65042
[27] Rendl, F.; Wolkowicz, H., A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program., 77, 1, 273-299 (1997) · Zbl 0888.90137
[28] Rojas, M.; Santos, S. A.; Sorensen, D. C., A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11, 3, 611-646 (2001) · Zbl 0994.65067
[29] Martínez, J. M., Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 1, 159-176 (1994) · Zbl 0801.65057
[30] Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (2006), Hoboken, NJ: Wiley, Hoboken, NJ · Zbl 1140.90040
[31] Wang, S.; Xia, Y., Strong duality for generalized trust region subproblem: S-lemma with interval bounds, Optim. Lett., 9, 1036-1073 (2015) · Zbl 1354.90089
[32] Ben-Tal, A.; Nemirovski, A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (2001), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 0986.90032
[33] Boyd, S. P.; Vandenberghe, L., Convex Optimization (2004), Camberidge: Cambridge University Press, Camberidge
[34] Hsia, Y.; Lin, G.-X.; Sheu, R.-L., A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil, Pac. J. Optim., 10, 3, 461-481 (2014) · Zbl 1327.90168
[35] Lancaster, P.; Rodman, L., Canonical forms for Hermitian matrix pairs under strict equivalence and congruence, SIAM Rev., 47, 3, 407-443 (2005) · Zbl 1087.15014
[36] Saad, Y., Numerical Methods for Large Eigenvalue Problems (1992), Manchester: Manchester University Press, Manchester · Zbl 0991.65039
[37] Crawford, C. R.; Moon, Y. S., Finding a positive definite linear combination of two hermitian matrices, Linear Algebra Appl., 51, 37-48 (1983) · Zbl 0516.15021
[38] Guo, C.-H.; Higham, N.; Tisseur, F., An improved arc algorithm for detecting definite Hermitian pairs, SIAM J. Matrix Anal. Appl., 31, 3, 1131-1151 (2010) · Zbl 1202.65054
[39] Grant, M.; Boyd, S., 21-57 (2014)
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.