S-Lemma with Equality and Its Applications

Abstract

Let $f(x)=x^{T}Ax+2a^{T}x+c$ and $h(x)=x^{T}Bx+2b^{T}x+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)\ge 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)\le 0$ is unsolvable if and only if $f(x)+\mu h(x)\ge 0,\forall x\in {\mathbb{R}}^n$ for some $\mu \ge 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\ne 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\le h(x)\le 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.

34 pages

References in corpus (1)

• Strong Duality for Generalized Trust Region Subproblem: S-Lemma with Interval Bounds

Cited by in corpus (17)

• Strong Duality for Generalized Trust Region Subproblem: S-Lemma with Interval Bounds
• On the convexity for the range set of two quadratic functions
• Positive polynomials on unbounded domains
• On Local Convexity of Quadratic Transformations
• Fast Algorithms for Stackelberg Prediction Game with Least Squares Loss
• Uniform Quadratic Optimization and Extensions
• Arrangement of level sets of quadratic constraints and its relation to nonconvex quadratic optimization problems
• Solving a new type of quadratic optimization problem having a joint numerical range constraint
• Unifying Farkas lemma and S-lemma: new theory and applications in nonquadratic nonconvex optimization
• A survey of hidden convex optimization
• Invex Optimization Revisited
• On-Demand Trajectory Predictions for Interaction Aware Highway Driving
• A fast algorithm for globally solving Tikhonov regularized total least squares problem
• Joint-range convexity for a pair of inhomogeneous quadratic functions and applications to QP
• Explicit minimisation of a convex quadratic under a general quadratic constraint: a global, analytic approach
• On Separation of level sets for a pair of quadratic functions
• Deciding whether two quadratic surfaces actually intersect