2
$\begingroup$

How to understand the sufficient condition for global optimum? From my understanding, the global optimum should be 0 instead of $\geq 0$, where does this come from?

Consider the constrained optimization problem

$$\underset{\beta \in R^p}{\min}f(\beta) \space \space \space s.t. \space\beta \in C$$

where $f$ is a convex objective function, and $C$ is a convex constraint set

when $f$ is differentiable then a sufficient condition for a vector $\beta^* \in C$ to be a global optimum is :

$$ \langle \triangledown f(\beta^*),\beta - \beta^* \rangle \geq 0 $$ for any $\beta \in C$

$\endgroup$

1 Answer 1

0
$\begingroup$

When you don't have constraints in the set or the optimum is strictly inside $C$, you should have $\nabla f(\beta^*)=0$ in order to satisfy for all other $\beta$. Having zero-gradient is also a sufficient condition but doesn't consider all possible situations, e.g. $f(\beta)=-3\beta, \beta\in[1,2]\rightarrow\beta^*=2$.

Assume the condition is satisfied. Since $f$ is convex, $f(\beta)\geq f(\beta^*)+\nabla f(\beta^*) (\beta-\beta^*)$. Since the second term is non-negative, it means $f(\beta)\geq f(\beta^*)$. So, if the condition is satisfied for some $\beta^*$, that $\beta^*$ is the optimum. It's a sufficient condition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.