×

zbMATH — the first resource for mathematics

S-lemma with equality and its applications. (English) Zbl 1333.90086
Summary: Let \(f(x)=x^TAx+2a^Tx+c\) and \(h(x)=x^TBx+2b^Tx+d\) be two quadratic functions having symmetric matrices \(A\) and \(B\). The S-lemma with equality asks when the unsolvability of the system \(f(x)<0\), \(h(x)=0\) implies the existence of a real number \(\mu\) such that \(f(x)+\mu h(x)\geq 0\), \(\forall x\in\mathbb R^n\). The problem is much harder than the inequality version which asserts that, under Slater condition, \(f(x)<0\), \(h(x)\leq 0\) is unsolvable if and only if \(f(x)+\mu h(x)\geq 0\), \(\forall x\in\mathbb R^n\) for some \(\mu\geq 0\). In this paper, we show that the S-lemma with equality does not hold only when the matrix \(A\) has exactly one negative eigenvalue and \(h(x)\) is a non-constant linear function \((B=0, b\neq 0)\). As an application, we can globally solve \(\inf\{f(x):h(x)=0\}\) as well as the two-sided generalized trust region subproblem \(\inf\{f(x):l\leq h(x)\leq u\}\) without any condition. Moreover, the convexity of the joint numerical range \(\{(f(x),h_1(x),\dots,h_p(x)):x\in\mathbb R^n\}\) where \(f\) is a (possibly non-convex) quadratic function and \(h_1(x),\dots,h_p(x)\) are affine functions can be characterized using the newly developed S-lemma with equality.

MSC:
90C20 Quadratic programming
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Anstreicher, KM; Wright, MH, A note on the augmented hessian when the reduced Hessian is semidefinite, SIAM J. Optim., 11, 243-253, (2000) · Zbl 1047.90040
[2] Beck, A, On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of ball, J. Global Optim., 39, 113-126, (2007) · Zbl 1151.90036
[3] Beck, A; Eldar, YC, Strong duality in nonconvex quadratic optimization with two quadratic constraint, SIAM J. Optim., 17, 844-860, (2006) · Zbl 1128.90044
[4] Ben-Tal, A; Hertog, D, Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program. Ser. A., 143, 1-9, (2014) · Zbl 1295.90036
[5] Ben-Tal, A; Teboulle, M, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Math. Program., 72, 51-63, (1996) · Zbl 0851.90087
[6] Brickman, L, On the field of values of a matrix, Proc. Am. Math. Soc., 12, 61-66, (1961) · Zbl 0104.01204
[7] Derinkuyu, K; Pınar, MÇ, On the S-procedure and some variants, Math. Meth. Oper. Res., 64, 55-77, (2006) · Zbl 1115.93025
[8] Dines, LL, On the mapping of quadratic forms, Bull. Am. Math. Soc., 47, 494-498, (1941) · Zbl 0027.15004
[9] Fang, S.C., Gao, D.Y., Lin, G.X., Sheu, R.L., Xing, W.: Double well potential function and its optimization in the n-dimenstional real space—Part I. Math. Mech. Solids (2015). doi:10.1177/1081286514566704
[10] Feng, JM; Lin, GX; Sheu, RL; Xia, Y, Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint, J. Global Optim., 54, 275-293, (2012) · Zbl 1281.90032
[11] Finsler, P, Über das vorkommen definiter und semidefiniter formen in scharen quadratischer formen, Comment. Math. Helv., 9, 188-192, (1937) · Zbl 0016.19901
[12] Fradkov, AL; Yakubovich, VA, The S-procedure and the duality relation in convex quadratic programming problems, Vestnik Leningrad. Univ., 1, 81-87, (1973) · Zbl 0259.93033
[13] Hestenes, M.R.: Optimization Theory. Wiley, New York (1975) · Zbl 0327.90015
[14] Hmam, H.: Quadratic optimization with one quadratic equality constraint. Electronic Warfare and Radar Division DSTO Defence Science and Technology Organisation, Australia, Report DSTO-TR-2416 (2010) · Zbl 1128.90046
[15] Horn, R., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001
[16] Hsia, Y; Lin, GX; Sheu, RL, A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil, Pac. J. Optim., 10, 461-481, (2014) · Zbl 1327.90168
[17] Jerrard, RL, Lower bounds for generalized Ginzburg-Landau functionals, SIAM J. Math. Anal., 30, 721-746, (1999) · Zbl 0928.35045
[18] Jeyakumar, V, Farkas lemma: generalizations, Encycl. Optim., 2, 87-91, (2000)
[19] Jeyakumar, V; Huy, NQ; Li, G, Necessary and sufficient conditions for S-lemma and nonconvex quadratic optimization, Optim. Eng., 10, 491-503, (2009) · Zbl 1273.90141
[20] Jeyakumar, V; Lee, GM; Li, GY, Alternative theorems for quadratic inequality systems and global quadratic optimization, SIAM J. Optim., 20, 983-1001, (2009) · Zbl 1197.90315
[21] Jeyakumar, V; Li, GY, Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Math. Program., 147, 171-206, (2014) · Zbl 1297.90105
[22] Martínez-Legaz, JE, On brickman’s theorem, J. Convex Anal., 12, 139-143, (2005) · Zbl 1077.15024
[23] Moré, JJ, Generalizations of the trust region problem, Optim. Methods Softw., 2, 189-209, (1993)
[24] Nguyen, VB; Sheu, RL; Xia, Y, An SDP approach for quadratic fractional problems with a two-sided quadratic constraint, Optim. Methods Softw., (2015) · Zbl 1385.90027
[25] Palanthandalam-Madapusi, HJ; Pelt, THV; Bernstein, DS, Matrix pencils and existence conditions for quadratic programming with a sign-indefinite quadratic equality constraint, J. Global Optim., 45, 533-549, (2009) · Zbl 1201.90148
[26] Pólik, I; Terlaky, T, A survey of the S-lemma, SIAM Rev., 49, 371-418, (2007) · Zbl 1128.90046
[27] Polyak, BT, Convexity of quadratic transformations and its use in control and optimization, J. Optim. Theory App., 99, 553-583, (1998) · Zbl 0961.90074
[28] Pong, TK; Wolkowicz, H, The generalized trust region subprobelm, Comput. Optim. Appl., 58, 273-322, (2014) · Zbl 1329.90100
[29] Shor, NZ, Quadratic optimization problems, Sov. J. Comput. Syst. Sci., 25, 1-11, (1987) · Zbl 0655.90055
[30] Sturm, JF; Wolkowicz, H, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5, 286-313, (1995) · Zbl 0846.49017
[31] Sturm, JF; Zhang, S, On cones of nonnegtive quadratic functions, Math. Oper. Res., 28, 246-267, (2003) · Zbl 1082.90086
[32] Tuy, H; Tuan, HD, Generalized S-lemma and strong duality in nonconvex quadratic programming, J. Global Optim., 56, 1045-1072, (2013) · Zbl 1300.90020
[33] Wang, S., Xia, Y.: Strong duality for generalized trust region subproblem: S-lemma with interval bounds. Optim. Lett. (2014). doi:10.1007/s11590-014-0812-0 · Zbl 1354.90089
[34] Xia, Y., Sheu, R.L., Fang, S.C., Xing, W.: Double well potential function and its optimization in the n-dimenstional real space—Part II. Math. Mech. Solids (2015). doi:10.1177/1081286514566723 · Zbl 1128.90044
[35] Yakubovich, VA, S-procedure in nonlinear control theory, Vestnik Leningrad. Univ., 1, 62-77, (1971) · Zbl 0232.93010
[36] Yakubovich, VA, S-procedure in nonlinear control theory, Vestnik Leningrad. Univ., 4, 73-93, (1977)
[37] Ye, Y; Zhang, S, New results on quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064
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.