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 am trying to prove a set is convex. This is a problem from Boyd's Convex Optimization text.

The set is $\{\hat{x} + tv | \alpha t^2 + \beta t + \gamma \leq 0\}$. This is actually an intersection of a line and a set, the line can be thought of as the part before the | symbol, and the original set contributed the part after the | symbol.

To prove convexity, I must show: $x,y \in C \Rightarrow \theta x + (1-\theta)y \in C$, with $0 \leq \theta \leq 1$. For this particular set, I tried:

$\theta (\hat{x}+t_1 v) + (1-\theta)(\hat{x}+t_2 v) = \theta \hat{x} + \theta t_1 v + \hat{x} + t_2 v - \theta \hat{x} - \theta t_2 v = \hat{x} + v(\theta t_1 + (1-\theta)t_2)$.

I must show: $\hat{x} + v(\theta t_1 + (1-\theta)t_2) \in \{\hat{x} + tv | \alpha t^2 + \beta t + \gamma \leq 0\}$.

This is the same as showing: $\alpha (\theta t_1 + (1-\theta)t_2)^2 + \beta(\theta t_1 + (1-\theta)t_2) + \gamma \leq 0$.

By setting $t = \theta t_1$, I can simplify a little. Somehow, I'm supposed to reach the conclusion $\alpha \geq 0$.

Can someone tell me a hint? Thanks.

share|improve this question
    
+1 for showing some thought before posting –  Ross Millikan Mar 15 '11 at 3:54

2 Answers 2

Think geometrically. Assuming $\alpha \ge 0$ (which is necessary, as Ross remarked) $\alpha t^2 + \beta t + \gamma \le 0$ for $t$ in an interval of the real line. Then $x + t v$ for such $t$ forms what kind of object?

share|improve this answer
    
Ok. Let me explore the behaviour of $\{t|f(t)\leq0\}$. This function, $\alpha t^2 + \beta t + \gamma \leq 0$ is a parabola, that opens up if $\alpha > 0$ and opens down if $\alpha < 0$. But there is another issue here. The gamma controls the level of the parabola. So I see 4 different scenarios. 1) open up, vertex above origin. 2) open up, vertex below origin. 3) open down, vertex above. 4) open down, vertex below. Note that we can immediately rule out (3), because that yields two different intervals of t on the real line, which causes the original lie to have a gap (not convex). –  jrand Mar 15 '11 at 6:26
    
(1) yields the null set, which gives $x+tv = null$, which is convex. (2) yields an interval, which gives a valid line segment, which is convex. But for (4), isn't it possible to have a scenario where f(t) lies below the origin, and points down? Then we have t valid for all real numbers, then $x+tv$ is a line, which is convex? Or maybe there's something here with the size of $\alpha$ and $\beta$? –  jrand Mar 15 '11 at 6:41
    
The only case where it is not convex is $\alpha$ negative and vertex above the x axis. –  Tim Seguine Sep 28 '11 at 20:25

$\alpha$ is a given and could be positive or negative. The conclusion you are looking for is exactly what you said: $\alpha (\theta t_1 + (1-\theta)t_2)^2 + \beta(\theta t_1 + (1-\theta)t_2) + \gamma \leq 0$. This shows that the point $\theta t_1 + (1-\theta)t_2 \in C$. You have that the quadratic is $\leq 0$ for both $t_1$ and $t_2$. Can you combine those two to get the result?

share|improve this answer
    
I must show: $\alpha (\theta t_1 + (1-\theta)t_2)^2 + \beta(\theta t_1 + (1-\theta)t_2) + \gamma \leq 0$. I know: $\alpha t_1^2 + \beta t_1 + \gamma \leq 0$ and $\alpha t_2^2 + \beta t_1 + \gamma \leq 0$. If I multiply the first by $\theta$, I get $\theta \alpha t_1^2 + \theta \beta t_1 + \theta \gamma \leq 0$. If I multiply the second by $(1-\theta)$, I get $(1-\theta) \alpha t_2^2 + (1-\alpha) \beta t_1 + (1-\alpha) \gamma \leq 0$. Since $a \leq 0 \wedge b \leq 0, a+b \leq 0$, I can combine the previous two equations. –  jrand Mar 15 '11 at 4:07
    
But if I combine, I get: $\theta \alpha t_1^2 + (1-\theta) \alpha t_2^2 + \theta \beta t_1 + (1-\theta) \beta t_2 + \gamma \leq 0$. The last three terms match exactly what I want to show. The only differing term between what I have and I want to show is $\alpha 2 \theta (1-\theta) t_1 t_2$ –  jrand Mar 15 '11 at 4:15
    
Are you sure $\alpha \gt 0$ wasn't specified? If $\alpha \lt 0$, unbounded $t$ satisfy the relation, but small $t$ may fail (take $\beta=0, \gamma \gt 0$) and the set is not convex. –  Ross Millikan Mar 15 '11 at 4:36
    
In this set, $\{t|\alpha t^2 + \beta t + \gamma \leq 0\}$, $\alpha, \beta, \gamma$ could be any values in $R$. Then, $\alpha > 0 \vee \alpha \leq 0$. If $\alpha > 0$, then $t = \text{interval} \vee t = \emptyset$. In either case, $\alpha > 0 \Rightarrow x+tv \text{is convex}$. That is, positive $\alpha$ guarantees the set is convex. But there exist certain values of negative $\alpha$ that can make the set convex. For instance, the parabola opens down and the vertex lies below the origin. Then, $t = \text{all real numbers}$. Then, certainly, $x+tv$ is convex. –  jrand Mar 16 '11 at 14:28
    
So I agree alpha positive guarantees convexity, but alpha negative can cause the set to be convex, if we pick values of beta and gamma. –  jrand Mar 16 '11 at 14:28

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.