0

The solution of the exercise 2.10 from the textbook Convex Optimization by Boyd & Vandenberghe, they say that the set:

$\{\hat{x} + tv \space |\space \alpha t^2 + \beta t + \gamma \le 0\}$

$\space \space \space \space \space \space \space \space$ with $\alpha = v^T Av, \space \beta = b^Tv + 2\hat{x}^T Av, \space and \space \gamma = c + b^T \hat{x} + \hat{x}^TA \hat{x} $

is convex if $\alpha \ge 0$. This is true for any $v$, if $v^T Av \ge 0$ for all $v$, i.e, $A \succeq 0$

I don't understant why "(the set) is convex if $\alpha \ge 0$." and why "This is true for any $v$, if $v^T Av \ge 0$ for all $v$, i.e, $A \succeq 0$".

Does someone has an idea?

Rodrigo de Azevedo
  • 1
Le Noff
  • 125

1 Answers1

2

When $\alpha \ge 0$, the quadratic function is convex,

The set of $t$ where $\alpha t^2 +\beta t + \gamma \le 0$ can be written in the form of $p \le t \le q$ where $p$ and $q$ are the roots of the quadratic polynomial, $q \ge p$. The correponding $\hat{x}+tv$ is a line segment.

If $\alpha < 0$, the corresponding set is the union of $\{t:t > q\}$ and $\{t:t <p\} $, which is not convex.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Thank you for your answer. Now I see why $\alpha$ needs to be greater than or equal to 0. If you don't mind I have two more questions 1) why is $\alpha$ positive for all $v$ if $v^T Av \ge 0$ ? 2) Does your answer means that we can rewrite ${\hat{x}+tv \space | \space \alpha t^2 + \beta t + \gamma \le }$ as ${t \space | \space \alpha t^2 + \beta t + \gamma \le }$ ? – Le Noff Jun 08 '20 at 11:20
  • $\alpha$ is defined to be $v^TAv$. It is nonnegative if $v^TAv$ is nonnegative. 2), No, I mean ${\hat{x}+tv|\alpha t^2+\beta t+\gamma \le 0} = {\hat{x}+tv | p \le t \le q}$ when $\alpha \ge 0$. It is a line segment.
    • – Siong Thye Goh Jun 08 '20 at 11:29
  • Thanks, I've got it now. – Le Noff Jun 08 '20 at 12:10