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
    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
    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