1

$f(x)\in C^1(D)$ is convex. $D\subset\mathbb{R}^n$ is a closed and convex. Show that $x^*$ is a global minimizer of the problem

$$ (P)\qquad\qquad\qquad \text{min}\{f(x):x\in D\} $$ if and only if $$ {\nabla f(x)}^T(x^*-x)\leq 0 \ \ \ \ \forall x\in D $$

My attempt: it is sufficient to show $x^*$ is local min.

Suppose, by contradiction, for arbitrarily small neighborhood of $x^*$, $\exists\ x$ such that $f(x)<f(x^*)$. $$ f(x^*)=f(x)+{\nabla f(x)}^T(x^*-x)+o(||x^*-x||)\Rightarrow {\nabla f(x)}^T(x^*-x)+o(||x^*-x||)>0 $$

For another attempt, I want to show that when if it is not local min, then when $x\rightarrow x^*$ along some direction, ${\nabla f(x)}^T(x^*-x)>0$, which leads to a contradiction.

1 Answers1

1

Suppose $\nabla f(x)^\top(x^*-x)\le 0\ \forall\,x\in C$. Replacing $x$ by $tx+(1-t)x^*$ with $t\in(0,1)$ yields $$ t\nabla f(tx+(1-t)x^*)^\top(x^*-x)\le 0. $$ Cancelling $t$ on both sides gives $$ \nabla f(tx+(1-t)x^*)^\top(x^*-x)\le 0,\quad\forall\,t\in(0,1). $$ Can you take it from here?

Kittayo
  • 699