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