How is inequality condition reduced to this?

Question

From Convex Optimization:

How is the condition in the red box reduced to this?

---

Answer 1

After having derived the condition $\nabla f_0(x) \succeq 0$, you know $\nabla f_0(x)^T y \geq 0$. Since the inequality has to hold for all $y \succeq 0$, it also has to hold for the $y$ which attains the minimum of $\nabla f_0(x)^T y $: $y=0$. For $y=0$ you get $-\nabla f_0(x)^Tx \geq 0$.

So you need all three conditions: $x \succeq 0$, $\nabla f_0(x) \succeq 0$, and $-\nabla f_0(x)^Tx \geq 0$.

Answer 2

I figured it out. Since it's for all $y$, it doesn't matter what $y$ we choose so it just matters that $-()$ is positive because it's a subtraction.

Answer 3

Think about the optimality condition. You have a $ y \succeq 0$ hypothesis. But you need to check $$ \nabla f_0(x)^T(y-x) \geq 0$$

So as $\succeq$ is understood entry-wise, this means every $y_i \geq 0$ and so $y_i - x_i \geq -x_i$, so $$ \nabla f_0(x)^T(y-x) \geq \nabla f_0(x)^T(-x) \: \: \forall y \succeq 0$$

$y\succeq 0$ includes the case $ y = 0$ for which the optimality condition means $\nabla f_0(x)^T(-x) \geq 0 $

Do you see why it is sufficient?

$$ \nabla f_0(x)^T(y-x) \geq \nabla f_0(x)^T(-x) \geq 0 $$