$\nabla f(x)^T(y-x) \geq 0$ if $x$ is optimal for a convex $f(x)$.

convex-analysisderivativesoptimizationreal-analysis

In the Convex Optimization book by Boyd and Vandenberghe, it states that if $x \in X$ and $X$ denotes the feasible set, and $f(x)$ is a convex objective function, then $x$ is optimal IFF

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

if $x$ is optimal for a convex $f(x)$. I understand this logic, but I don't understand why it's $\geq$ instead of $=$. If $x$ is optimal, then isn't the gradient of the objective function $f(x)$ zero there?

Best Answer

This is probably in the context of a constrained optimization problem "minimize $f$ within convex set $X$." In constrained optimization, the gradient need not be zero at the optimizer (specifically, when the optimizer is not in the interior of $X$). The optimality condition is "$\nabla f(x)^\top (y-x) \ge 0$ for all $y \in X$."

When $X$ is the entire space, then this result generalizes to the "gradient equals zero" condition for unconstrained optimization, since the vector $y-x$ can point in any direction.

Related Question