×

Solving generalized CDT problems via two-parameter eigenvalues. (English) Zbl 1346.49050

Summary: We consider solving a nonconvex quadratic minimization problem with two quadratic constraints, one of which being convex. This problem is a generalization of the Celis-Denis-Tapia (CDT) problem and thus we refer to it as GCDT (generalized CDT) problem. The CDT problem has been widely studied, but no polynomial-time algorithm was known until Bienstock’s recent work. His algorithm solves the CDT problem in polynomial time with respect to the number of bits in the data and \(\log\epsilon^{-1}\) by admitting an \(\epsilon\) error in the constraints. The algorithm, however, appears to be difficult to implement. In this paper, we present another algorithm for GCDT problems, which is guaranteed to find a global solution for almost all GCDT instances (and slightly perturbed ones in some exceptionally rare cases), in exact arithmetic (including eigenvalue computation). Our algorithm is based on the approach proposed by [S. Iwata et al., SIAM J. Optim. 25, No. 4, 2359–2384 (2015; Zbl 1334.49100)] for computing the signed distance between overlapping ellipsoids. Our algorithm computes all the Lagrange multipliers of the GCDT problem by solving a two-parameter linear eigenvalue problem, obtains the corresponding KKT points, and finds a global solution as the KKT point with the smallest objective value. In practice, in finite precision arithmetic, our algorithm requires \(O(n^6\log\log u^{-1})\) computational time, where \(n\) is the number of variables and \(u\) is the unit roundoff. Although we derive our algorithm under the unrealistic assumption that exact eigenvalues can be computed, numerical experiments illustrate that our algorithm performs well in finite precision arithmetic.

MSC:

49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming

Citations:

Zbl 1334.49100

Software:

rootsb; mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda, {\it Solving the Trust Region Subproblem by a Generalized Eigenvalue Problem}, Technical report, METR 2015-14, University of Tokyo, Tokyo, 2015. · Zbl 1359.49009
[2] W. Ai and S. Zhang, {\it Strong duality for the CDT subproblem: A necessary and sufficient condition}, SIAM J. Optim., 19 (2009), pp. 1735-1756. · Zbl 1187.90290
[3] A. I. Barvinok, {\it Feasibility testing for systems of real quadratic equations}, Discrete Comput. Geom., 10 (1993), pp. 1-13. · Zbl 0812.12006
[4] É. Bézout, {\it Théorie Générale des Équations Algébriques}, Ph.D. thesis, Pierres, Paris, 1779. · Zbl 1129.12001
[5] D. Bienstock, {\it A note on polynomial solvability of the CDT problem}, SIAM J. Optim., 26 (2016), pp. 488-498. · Zbl 1382.90083
[6] I. M. Bomze and M. L. Overton, {\it Narrowing the difficulty gap for the Celis-Dennis-Tapia problem}, Math. Program. Ser. B, 151 (2015), pp. 459-476. · Zbl 1328.90095
[7] P. A. Browne, {\it Numerical Methods for Two Parameter Eigenvalue Problems}, Ph.D. thesis, Department of Mathematical Sciences, University of Bath, Bath, England, 2008.
[8] S. Burer and K. M. Anstreicher, {\it Second-order-cone constraints for extended trust-region subproblems}, SIAM J. Optim., 23 (2013), pp. 432-451. · Zbl 1298.90062
[9] M. R. Celis, J. E. Dennis, and R. A. Tapia, {\it A trust region strategy for nonlinear equality constrained optimization}, in Numerical Optimization, P. T. Boggs, R. H. Byrd, and R. B. Schnabel, eds., SIAM Philadelphia, 1985, pp. 71-82. · Zbl 0566.65048
[10] X. Chen and Y.-X. Yuan, {\it On local solutions of the Celis-Dennis-Tapia subproblem}, SIAM J. Optim., 10 (2000), pp. 359-383. · Zbl 0957.65060
[11] I. Gohberg, P. Lancaster, and L. Rodman, {\it Matrix Polynomials}, Classics App. Math. 58, SIAM, Philadelphia, 2009.
[12] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, 4th ed., The Johns Hopkins University Press, Baltimore, MD, 2012. · Zbl 1268.65037
[13] N. J. Higham, {\it Accuracy and Stability of Numerical Algorithms}, 2nd ed., SIAM, Philadelphia, 2002. · Zbl 1011.65010
[14] S. Iwata, Y. Nakatsukasa, and A. Takeda, {\it Computing the signed distance between overlapping ellipsoids}, SIAM J. Optim., 25 (2015), pp. 2359-2384. · Zbl 1334.49100
[15] F. John, {\it Extremum problems with inequalities as subsidiary conditions}, in Traces and Emergence of Nonlinear Programming, G. Giorgi and T. Hoff Kjeldsen, eds., Springer, Basel, 2014, pp. 197-215.
[16] F. C. Kirwan, {\it Complex Algebraic Curves}, Cambridge University Press, Cambridge, 1992. · Zbl 0744.14018
[17] L. Lerer and M. Tismenetsky, {\it The Bézoutian and the eigenvalue-separation problem for matrix polynomials}, Integral Equations Operator Theory, 5 (1982), pp. 386-445. · Zbl 0504.47020
[18] G. Li and Y. Yuan, {\it Compute a Celis-Dennis-Tapia step}, J. Comput. Math., 23 (2005), pp. 463-478. · Zbl 1080.65048
[19] O. L. Mangasarian and S. Fromovitz, {\it The Fritz John necessary optimality conditions in the presence of equality and inequality constraints}, J. Math. Anal. Appl., 17 (1967), pp. 37-47. · Zbl 0149.16701
[20] C. B. Moler and G. W. Stewart, {\it An algorithm for generalized matrix eigenvalue problems}, SIAM J. Numer. Anal., 10 (1973), pp. 241-256. · Zbl 0253.65019
[21] Y. Nakatsukasa, V. Noferini, and A. Townsend, {\it Computing the common zeros of two bivariate functions via Bézout resultants}, Numer. Math., 129 (2015), pp. 181-209. · Zbl 1308.65076
[22] Y. Nesterov, H. Wolkowicz, and Y. Ye, {\it Noconvex quadratic optimization}, in Handbook of Semidefinite Programming, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer, New York, 2000, pp. 361-420. · Zbl 0957.90528
[23] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer, New York, 1999. · Zbl 0930.65067
[24] J.-M. Peng and Y.-X. Yuan, {\it Optimality conditions for the minimization of a quadratic with two quadratic constraints}, SIAM J. Optim., 7 (1997), pp. 579-594. · Zbl 0891.90150
[25] M. J. D. Powell and Y. Yuan, {\it A trust-region algorithm for equality constrained optimization}, Math. Program., 49 (1991), pp. 189-211. · Zbl 0816.90121
[26] R. J. Stern and H. Wolkowicz, {\it Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations}, SIAM J. Optim., 5 (1995), pp. 286-313. · Zbl 0846.49017
[27] J. F. Sturm and S. Zhang, {\it On cones of nonnegative quadratic functions}, Math. Oper. Res., 28 (2003), pp. 246-267. · Zbl 1082.90086
[28] F. Tisseur, {\it Backward error and condition of polynomial eigenvalue problems}, Linear Algebra Appl., 309 (2000), pp. 339-361. · Zbl 0955.65027
[29] B. Yang and S. Burer, {\it A two-variable approach to the two-trust-region subproblem}, SIAM J. Optim., 26 (2016), pp. 661-680. · Zbl 1333.90087
[30] Y. Yuan, {\it On a subproblem of trust region algorithms for constrained optimization}, Math. Program., 47 (1990), pp. 53-63. · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.