Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have two quadratic inequalities of the form $$ a_1x^TAx + b_1^Tx + c_1 \le 0\\ a_2x^TAx + b_2^Tx + c_2 \le 0 $$ where $A\in\mathbb{R}^{n\times n}$ is positive semidefinite, $x\in\mathbb{R}^n$, $b_i\in\mathbb{R}^n$, and $a_i,c_i\in\mathbb{R}$, $i=1,2$.

I wish to determine if the set formed by the two inequalities is bounded. I began by thinking of the case where $n=1$, so we just have parabolic functions. I claimed that as long as the two central axes of the parabolas (the line of symmetry) were not parallel then the intersection would be bounded. I have not proved this claim, but I have a feeling it is true. If so, I am hoping it may be possible to generalize to higher dimensions. If this can be done then we could rule out an unbounded intersection if the two functions do not specify the stringent requirement of parallel central axes.

Any tips or better directions?

share|improve this question
2  
Why don't you diagonalize $A$ to start with? –  copper.hat Feb 1 '13 at 20:30
    
For $n=1$ the parabolas will have parallel axes. So I do not see how the investigation in intersection of two parabolas with non-parallel axes fits in above discussion. –  Maesumi Feb 1 '13 at 20:41
    
@Maesumi good point, so one sufficient condition for $n=1$ reduces to if $a_1$ and $a_2$ are different signs then the set will be bounded (I suppose another condition would be related to the curvature if $a_1$ and $a_2$ are the same sign). Will the axes always be parallel for any $n$? –  Erik Miehling Feb 1 '13 at 20:59
1  
For $n=1$ you get $(a_1-a_2)x^2+(b_1-b_2)x+(c_1-c_2)=0$ which is a quadratic equation. If it has two roots then you have a bounded region. For higher $n$ The surfaces will depend heavily on $A$. For example, consider $n=3$. If $A$ is identity then they are spheres. You can see it can be paraboloid, hyperboloid, etc. –  Maesumi Feb 1 '13 at 21:10
1  
A suggestion: a quick check to settle most cases is to form a "convex linear combination" of your equations. i.e pick a $\lambda \in (0,1)$, replace the $a_i$ in your equation by $\lambda a_1 + (1 - \lambda) a_2$ and do the same thing to $b_i, c_i$. If for some $\lambda$, the resulting $a A$ is positive definite, then the intersection of your original equations is contained within a ellipsoid and hence bounded. –  achille hui Feb 1 '13 at 21:17
show 4 more comments

1 Answer 1

up vote 1 down vote accepted

We may assume $\mathbf A$ to be symmetric, though it is not specified in your question, because everything remains unchanged by replacing $\mathbf A$ with its symmetric part $\frac12(\mathbf A+\mathbf A^T)$. Now, two easy cases:

First, suppose $\mathbf A$ is positive definite and $a_i\ne 0$. Then there is a radius $r_i$ outside which $\mathbf x^T\mathbf A\mathbf x+(\mathbf b_i^T\mathbf x+c_i)/a_i\ge0$ for all $\lVert\mathbf x\rVert\ge r_i$. So, if either $a_i$ is positive, then the intersection is bounded. If one is negative and the other is nonpositive, the intersection is unbounded. If both $a_i$ are zero, then you're looking at the intersection of two half-spaces $\mathbf b_i^T\mathbf x+c_i\le 0$, which is unbounded unless $n=1$ and the $\mathbf b_i$ are scalars of opposite signs.

Second, suppose $\mathbf A$ is positive semidefinite and both $a_i$ are positive. Let $\mathbf x=t\mathbf u$ for some fixed vector $\mathbf u$. As $t\to\infty$, the condition $a_i\mathbf x^T\mathbf A\mathbf x+\mathbf b_i^T\mathbf x+c_i\le0$ can hold only if $\mathbf u^T\mathbf A\mathbf u=0$, so $\mathbf u$ belongs to the null space of $\mathbf A$. Then we can restrict our attention to $\mathbf u\in\operatorname{Null}(\mathbf A)$, in which the problem reduces to finding whether the intersection of the half-spaces $\mathbf b_i^T\mathbf u+c_i\le 0$ is unbounded. This was already discussed above: it is unbounded unless the null space is one-dimensional, i.e. $\operatorname{Null}(\mathbf A)=\{\alpha\mathbf u_0\}$ for a fixed $\mathbf u_0$, and $\mathbf b_i^T\mathbf u_0$ have different signs.

You could probably extend this analysis to all the other cases, but that's more effort than I have time for right now.

share|improve this answer
    
Thank you for this answer, really helpful! –  Erik Miehling Feb 3 '13 at 17:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.