zbMATH — the first resource for mathematics

Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint. (English) Zbl 1411.90246
Summary: A nonconvex quadratically constrained quadratic programming (QCQP) with one constraint is usually solved via a dual SDP problem, or Moré’s algorithm based on iteratively solving linear systems. In this work we introduce an algorithm for QCQP that requires finding just one eigenpair of a generalized eigenvalue problem, and involves no outer iterations other than the (usually black-box) iterations for computing the eigenpair. Numerical experiments illustrate the efficiency and accuracy of our algorithm. We also analyze the QCQP solution extensively, including difficult cases, and show that the canonical form of a matrix pair gives a complete classification of the QCQP in terms of boundedness and attainability, and explain how to obtain a global solution whenever it exists.

90C20 Quadratic programming
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
Full Text: DOI
[1] Adachi, S.; Iwata, S.; Nakatsukasa, Y.; Takeda, A., Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim., 27, 269-291, (2017) · Zbl 1359.49009
[2] Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., van der Vorst, H.: Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM, Philadelphia (2000) · Zbl 0965.65058
[3] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, Philadelphia (2001) · Zbl 0986.90032
[4] Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[5] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[6] Crawford, CR; Moon, YS, Finding a positive definite linear combination of two Hermitian matrices, Linear Algebra Appl., 51, 37-48, (1983) · Zbl 0516.15021
[7] Demmel, J.; Kågström, B., The generalized schur decomposition of an arbitrary pencil \(A- \lambda B\): robust software with error bounds and applications. Part I: theory and algorithms, ACM Trans. Math. Soft., 19, 160-174, (1993) · Zbl 0889.65042
[8] Fehmers, GC; Kamp, LPJ; Sluijter, FW, An algorithm for quadratic optimization with one quadratic constraint and bounds on the variables, Inverse Probl., 14, 893, (1998) · Zbl 0909.65035
[9] 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, 275-293, (2012) · Zbl 1281.90032
[10] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19, 41-67, (2004) · Zbl 1070.65041
[11] Gander, W.; Golub, GH; Matt, U., A constrained eigenvalue problem, Linear Algebra Appl., 114, 815-839, (1989) · Zbl 0666.15006
[12] Golub, G.H., Loan, C.F.V.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2012) · Zbl 1268.65037
[13] Gould, NIM; Lucidi, S.; Roma, M.; Toint, PL, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 504-525, (1999) · Zbl 1047.90510
[14] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2014)
[15] Guo, C-H; Higham, NJ; Tisseur, F., An improved arc algorithm for detecting definite Hermitian pairs, SIAM J. Matrix Anal. Appl., 31, 1131-1151, (2009) · Zbl 1202.65054
[16] 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, 461-481, (2014) · Zbl 1327.90168
[17] Iwata, S., Nakatsukasa, Y., Takeda, A.: Global optimization methods for extended Fisher discriminant analysis. In: Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, pp. 411-419 (2014)
[18] Jegelka, S.: Private communication (2015)
[19] Jiang, R., Li, D., Wu, B.: SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices. Math. Prog. (2017). https://doi.org/10.1007/s10107-017-1145-4 · Zbl 1390.90416
[20] Johansson, S., Johansson, P.: StratiGraph and MCS Toolbox Homepage. Department of Computing Science, Umeå University, Sweden. http://www.cs.umu.se/english/research/groups/matrix-computations/stratigraph (2016)
[21] Lancaster, P.; Rodman, L., Canonical forms for Hermitian matrix pairs under strict equivalence and congruence, SIAM Rev., 47, 407-443, (2005) · Zbl 1087.15014
[22] Lehoucq, R.B., Sorensen, D.C., Yang, C.: ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, vol. 6. SIAM, Philadelphia (1998) · Zbl 0901.65021
[23] Mackey, DS; Mackey, N.; Mehl, C.; Mehrmann, V., Möbius transformations of matrix polynomials, Linear Algebra Appl., 470, 120-184, (2015) · Zbl 1309.65042
[24] Moré, JJ, Generalizations of the trust region problem, Optim. Methods Softw., 2, 189-209, (1993)
[25] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[26] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (1999) · Zbl 0930.65067
[27] Pólik, I.; Terlaky, T., A survey of the s-lemma, SIAM Rev., 49, 371-418, (2007) · Zbl 1128.90046
[28] Pong, TK; Wolkowicz, H., The generalized trust region subproblem, Comput. Optim. Appl., 58, 273-322, (2014) · Zbl 1329.90100
[29] 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
[30] Rojas, M.; Santos, SA; Sorensen, DC, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11, 611-646, (2001) · Zbl 0994.65067
[31] Rojas, M.; Santos, SA; Sorensen, DC, Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Soft., 34, 11:1-11:28, (2008) · Zbl 1291.65177
[32] Sahni, S., Computationally related problems, SIAM J. Comput., 3, 262-279, (1974) · Zbl 0272.68040
[33] Sakaue, S.; Nakatsukasa, Y.; Takeda, A.; Iwata, S., Solving generalized CDT problems via two-parameter eigenvalues, SIAM J. Optim., 26, 1669-1694, (2016) · Zbl 1346.49050
[34] Salahi, M.; Taati, A.; Wolkowicz, H., Local nonglobal minima for solving large-scale extended trust-region subproblems, Comput. Optim. Appl., 66, 223-244, (2016) · Zbl 1391.90496
[35] Sorensen, DC, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7, 141-161, (1997) · Zbl 0878.65044
[36] Sturm, JF, Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 625-653, (1999) · Zbl 0973.90526
[37] Thompson, RC, The characteristic polynomial of a principal subpencil of a hermitian matrix pencil, Linear Algebra Appl., 14, 135-177, (1976) · Zbl 0386.15011
[38] Thompson, RC, Pencils of complex and real symmetric and skew matrices, Linear Algebra Appl., 147, 323-371, (1991) · Zbl 0726.15007
[39] Toh, K-C; Todd, MJ; Tütüncü, RH, SDPT3 Matlab software package for semidefinite programming, version 1.3, Optim. Methods Softw., 11, 545-581, (1999) · Zbl 0997.90060
[40] Vavasis, SA, Quadratic programming is in NP, Inf. Process. Lett., 36, 73-77, (1990) · Zbl 0719.90052
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.