$x^∗ ∈ C$ is an optimal solution of the problem iff $〈∇f (x),x∗ − x〉 ≤ 0$ for all $x ∈ C$.

Question

Let $f$ be a continuously differentiable convex function over a closed and convex set $C ⊆ \mathbb{R}^n$. Show that $x∗ ∈ C$ is an optimal solution of the problem (P) min$\{ f (x) : x ∈ C\}$
if and only if
$〈∇f (x),x∗ − x〉 ≤ 0$ for all $x ∈ C$

.
The first part where I assume that $x^*$ is optimal solution and then showing the inequality I've managed to show , at the second part I've tried assuming that $x^*$ is not optimal solution and then show the inequality doesn't hold but got stuck. any hint?

Answer 1

Since $f$ is convex, then by the Gradient Inequality $$f(\mathbf{x})\geq f(\mathbf{x}^*)+\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*), \quad \forall\mathbf{x}\in C.$$ Next, we assume that $\nabla f(\mathbf{x}^*)^T(\mathbf{x}^*-\mathbf{x})\leq 0$, which is the same as $\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*)\geq 0$. Using this assumption in the Gradient Inequality means that $$f(\mathbf{x})\geq f(\mathbf{x}^*), \quad \forall\mathbf{x}\in C$$ which proves the optimality of $\mathbf{x}^*$.