×

zbMATH — the first resource for mathematics

Tilt stability for quadratic programs with one or two quadratic inequality constraints. (English) Zbl 1453.90111
Summary: This paper examines tilt stability for quadratic programs with one or two quadratic inequality constraints. Exploiting specific features of these problems and using some known results on tilt stability in nonlinear programming, we establish quite simple characterizations of tilt-stable local minimizers for quadratic programs with one quadratic inequality constraint under metric subregularity constraint qualification. By the same way, we also derive various tilt stability conditions for quadratic programs with two quadratic inequality constraints and satisfying certain suitable assumptions. Especially, the obtained results show that some tilt stability conditions only known to be sufficient in nonlinear programming become the necessary ones when the considered problems are quadratic programs with one or two quadratic inequality constraints.
MSC:
90C20 Quadratic programming
90C31 Sensitivity, stability, parametric optimization
90C46 Optimality conditions and duality in mathematical programming
Software:
HSL-VF05
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 (2008) · Zbl 1187.90290
[2] Bomze, IM; Overton, ML, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math. Program., 151, 459-476 (2015) · Zbl 1328.90095
[3] Bonnans, JF; Shapiro, A., Perturbation Analysis of Optimization Problems (2000), New York: Springer, New York
[4] Beck, A.; Vaisbourd, Y., Globally Solving the trust region subproblem using simple first-order methods, SIAM J. Optim., 28, 1951-1967 (2018) · Zbl 1455.90104
[5] Bienstock, D., A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26, 488-498 (2016) · Zbl 1382.90083
[6] Celis, M. R., Dennis, J. E., Tapia, R. A.: A trust region algorithm for nonlinear equality constrained optimization. In: Optimization Numerical, Boggs, P. T., Byrd, R. H., Schnabel, R. B. (eds.) , pp 71-82. SIAM, Philadelphia (1985)
[7] Chieu, NH; Hien, LV, Computation of graphical derivative for a class of normal cone mappings under a very weak condition, SIAM J. Optim., 27, 190-204 (2017) · Zbl 1357.49072
[8] Chieu, NH; Hien, LV; Nghia, TTA, Characterization of tilt stability via subgradient graphical derivative with applications to nonlinear programming, SIAM J. Optim., 28, 2246-2273 (2018) · Zbl 1397.49037
[9] Conn, AR; Gould, NIM; Toint, PHL, Trust-Region methods MPS-SIAM series on optimization, vol. 01 (2000), Philadelphia: SIAM, Philadelphia
[10] Consolini, L.; Locatelli, M., On the complexity of quadratic programming with two quadratic constraints, Math. Program., 164, 91-128 (2017) · Zbl 1396.90055
[11] Drusvyatskiy, D.; Lewis, AS, Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential, SIAM J. Optim., 23, 256-267 (2013) · Zbl 1275.49026
[12] Eberhard, AC; Wenczel, R., A study of tilt-stable optimality and suffcient conditions, Nonlinear Anal., 75, 1260-1281 (2012) · Zbl 1236.49049
[13] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optim. Methods Software, 19, 41-67 (2004) · Zbl 1070.65041
[14] Gfrerer, H.; Mordukhovich, BS, Complete characterizations of tilt stability in nonlinear programming under weakest qualification conditions, SIAM J. Optim., 25, 2081-2119 (2015) · Zbl 1357.49074
[15] 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
[16] Gould, N. I. M., Toint, P.H.L.A: Quadratic programming bibliography. Numerical Analysis Group Internal Report 2000-1, Rutherford Appleton Laboratory, Chilton, Oxfordshire UK (2000)
[17] Lee, GM; Tam, NN; Yen, ND, Quadratic Programming and Affine Variational Inequalities: a Qualitative Study (2005), New York: Springer-Verlag, New York
[18] Lee, GM; Tam, NN; Yen, ND, Stability of linear-quadratic minimization over Euclidean balls, SIAM J. Optim., 22, 936-952 (2012) · Zbl 1268.90039
[19] Levy, AB; Poliquin, RA; Rockafellar, RT, Stability of locally optimal solutions, SIAM J. Optim., 10, 580-604 (2000) · Zbl 0965.49018
[20] Lewis, AS; Zhang, S., Partial smoothness, tilt stability, and generalized Hessians, SIAM J. Optim., 23, 74-94 (2013) · Zbl 1267.90147
[21] MartĂ­nez, JM, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 159-176 (1994) · Zbl 0801.65057
[22] Mordukhovich, BS, Maximum principle in problems of time optimal control with nonsmooth constraints, J. Appl. Math. Mech., 40, 960-969 (1976) · Zbl 0362.49017
[23] Mordukhovich, BS, Variational Analysis and Generalized Differentiation I: Basic Theory (2006), Berlin: Springer, Berlin
[24] Mordukhovich, BS; Nghia, TTA, Second-order characterizations of tilt stability with applications to nonlinear programming, Math. Program., 149, 83-104 (2015) · Zbl 1312.49016
[25] Mordukhovich, BS; Outrata, JV, Tilt stability in nonlinear programming under Mangasarian-Fromovitz constraint qualification, Kybernetika, 49, 446-464 (2012) · Zbl 1305.90391
[26] Mordukhovich, BS; Rockafellar, RT, Second-order subdifferential calculus with applications to tilt stability in optimization, SIAM J. Optim., 22, 953-986 (2012) · Zbl 1260.49022
[27] Nocedal, J.; Wright, SJ, Numerical Optimization (2006), New York: Springer, New York
[28] Nghi, TV, Coderivatives related to parametric extended trust region subproblem and their applications, Taiwanese J. Math., 22, 485-511 (2018) · Zbl 1401.90234
[29] Pham Dinh, T.; Le Thi, HA, A DC optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8, 476-505 (1998) · Zbl 0913.65054
[30] Peng, JM; Yuan, Y., Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7, 579-594 (1997) · Zbl 0891.90150
[31] Poliquin, RA; Rockafellar, RT, Tilt stability of a local minimum, SIAM J. Optim., 8, 287-299 (1998) · Zbl 0918.49016
[32] Rockafellar, RT; Wets, RJ-B, Variational Analysis (1998), Berlin: Springer, Berlin
[33] Rojas, M.; Santos, SA; Sorensen, DC, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11, 611-646 (2000) · Zbl 0994.65067
[34] 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
[35] Salahi, M.; Taati, A.; Wolkowicz, H., Local nonglobal minima for solving large-scale extended trust-region subproblems, Comput. Optim. Appl., 66, 223-244 (2017) · Zbl 1391.90496
[36] Tuy, H.: Convex Analysis and Global Optimization (second edition). Springer International Publishing AG (2016) · Zbl 1362.90001
[37] Tuy, H.; Tuan, HD, Generalized S-Lemma and strong duality in nonconvex quadratic programming, J. Global Optim., 56, 1045-1072 (2013) · Zbl 1300.90020
[38] Ye, Y., On affine scaling algorithms for nonconvex quadratic programming, Math. Program., 56, 285-300 (1992) · Zbl 0767.90065
[39] Ye, Y.: A new complexity result on minimization of a quadratic function with a sphere constraint. In: Recent Advances in Global Optimization, 19-31. Princeton University Press (1992)
[40] Ye, Y.; Zhang, S., New results on quadratic minimization, SIAM J. Optim., 14, 245-267 (2003) · Zbl 1043.90064
[41] Yuan, Y., On a subproblem of trust region algorithms for constrained optimization, Math. Program., 47, 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.