Let $f$ be a convex function and $C$ some convex set and let
\begin{align}
x^\star= \arg \min_{x \in C} f(x)
\end{align} Is it true that $\langle x-x^\star, \nabla f(x^\star) \rangle \ge 0$ for all $x\in C$.
I was trying to show this by using the fact that if $f$ is convex, then
\begin{align}
f(u)\ge f(w) + \langle u-w, \nabla f(w) \rangle
\end{align}
For example, since we have that $f(x^\star)-f(x) \le 0$, then we have
\begin{align}
0 \ge \langle x^\star-x, \nabla f(x) \rangle \Longrightarrow \langle x-x^\star, \nabla f(x) \rangle .
\end{align}
However, this is not the right inequality.
Best Answer
What you're playing with is called a Variational Inequality.
The way it works is, assume $x^*$ is a global minimizer of $f(x)$ on $C$, a convex set. Now take the derivative of $$ \phi(\varepsilon) = f( (1-\varepsilon)x^* + \varepsilon x') $$ wrt to $\varepsilon$, yielding $$ \phi'(\varepsilon) = \nabla f( (1-\varepsilon)x^* + \varepsilon x')'(x'-x^*). $$ A necessary condition for $x^*$ to be a global minimizer is that $\phi'(0) \ge 0$, or $$ \phi'(0) = \nabla f( x^*)'(x'-x^*) \ge 0, \quad \forall x' \in C, $$ so that taking a directional derivative in any feasible direction $x'$ raises the value of the objective function, since $x^*$ is assumed to be the global minimizer. See how this subsumes the standard FONC's, which only apply on the interior of a set? In fact, if $x^*$ is on the interior of $C$, $\nabla f(x^*)=0$, and otherwise, $\nabla f(x^*)$ is non-zero, but characterizes the supporting hyperplane to $C$; the inequality accounts for the missing Lagrange or Kuhn-Tucker terms, $\lambda \nabla h(x^*)$ where $h$ is the constraint.
Convexity hasn't been used yet. What convexity of $f$ is buying is that the solution set of the variational inequality is a convex set. So if $x^*$ and $x'$ are global minimizers and $f$ is convex, $$ f(\lambda x^* + (1-\lambda)x') \le \lambda f(x^*) + (1-\lambda) f(x') = f^* $$ and the convex combination $\lambda x^* + (1-\lambda)x'$ must also be a global minimizer. If $f$ is strictly convex, that inequality would yield a contradiction, so that the minimizer is unique.
In general the VI framework generalizes standard FONC/SOSC reasoning to account for solutions on the boundary.