3
$\begingroup$

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.

2 Answers 2

1

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?

  • 0
    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).2011-03-15
  • 0
    (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$?2011-03-15
  • 0
    The only case where it is not convex is $\alpha$ negative and vertex above the x axis.2011-09-28
0

$\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?

  • 0
    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.2011-03-15
  • 0
    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$2011-03-15
  • 0
    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.2011-03-15
  • 0
    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.2011-03-16
  • 0
    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.2011-03-16