×

zbMATH — the first resource for mathematics

A conjugate gradient-based algorithm for large-scale quadratic programming problem with one quadratic constraint. (English) Zbl 1427.90210
Summary: In this paper, we consider the nonconvex quadratically constrained quadratic programming (QCQP) with one quadratic constraint. By employing the conjugate gradient method, an efficient algorithm is proposed to solve QCQP that exploits the sparsity of the involved matrices and solves the problem via solving a sequence of positive definite system of linear equations after identifying suitable generalized eigenvalues. Specifically, we analyze how to recognize hard case (case 2) in a preprocessing step, fixing an error in Sect. 2.2.2 of T. K. Pong and H. Wolkowicz [Comput. Optim. Appl. 58, No. 2, 273–322 (2014; Zbl 1329.90100)] which studies the same problem with the two-sided constraint. Some numerical experiments are given to show the effectiveness of the proposed method and to compare it with some recent algorithms in the literature.
MSC:
90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
90C52 Methods of reduced gradient type
Software:
GQTPAR; HSL-VF05
PDF BibTeX XML Cite
Full Text: DOI
References:
[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] Adachi, S.; Nakatsukasa, Y., Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint, Math. Program., (2017) · Zbl 1411.90246
[3] Ben-Tal, A.; Hertog, D., Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143, 1-29, (2014) · Zbl 1295.90036
[4] Crawford, CR; Moon, YS, Finding a positive definite linear combination of two Hermitian matrices, Linear Algebra Appl., 51, 37-48, (1983) · Zbl 0516.15021
[5] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[6] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19, 41-67, (2004) · Zbl 1070.65041
[7] Feng, J-M; Lin, G-X; Heu, 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
[8] Gould, NI; 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
[9] Gould, NI; Robinson, DP; Thorne, HS, On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput., 2, 21-57, (2010) · Zbl 1193.65098
[10] 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
[11] Jegelka, S.: Private communication (2015)
[12] Jian, R., Li, D.: Novel reformulations and efficient algorithms for the generalized trust region subproblem. arXiv:1707.08706 (2017)
[13] 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, 531-563, (2018) · Zbl 1390.90416
[14] Lancaster, P.; Rodman, L., Canonical forms for Hermitian matrix pairs under strict equivalence and congruence, SIAM Rev., 47, 407-443, (2005) · Zbl 1087.15014
[15] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[16] Moré, JJ, Generalizations of the trust region problem, Optim. Methods Softw., 2, 189-209, (1993)
[17] Pong, TK; Wolkowicz, H., The generalized trust region subproblem, Comput. Optim. Appl., 58, 273-322, (2014) · Zbl 1329.90100
[18] 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
[19] 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
[20] Saad, Y.: Numerical Methods for Large Eigenvalue Problems. Manchester University Press, Manchester (1992) · Zbl 0991.65039
[21] Steihaug, T., The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20, 626-637, (1983) · Zbl 0518.65042
[22] Salahi, M.; Taati, A., An efficient algorithm for solving the generalized trust region subproblem, Comput. Appl. Math., 37, 395-413, (2018) · Zbl 1393.90098
[23] Toint, PL; Duff, IS (ed.), Towards an efficient sparsity exploiting Newton method for minimization, 57-88, (1981), London
[24] Ye, Y.; Zhang, S., New results on quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064
[25] Yuan, Y., Recent advances in trust region algorithms, Math. Program., 151, 249-281, (2015) · Zbl 1317.65141
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.