Characterization of minimizer of a convex function on convex set

Question

I'm proving the following theorem:

Let $\mathcal{D} \subseteq \mathbb{R}^{p}$ be non-empty closed convex and $f:\mathbb{R}^{p} \to \mathbb R_+$ be continuously differentiable and convex. Let $$x^\star=\underset{x \in \mathcal D}{\text{arg min}} \, f(x)$$ Prove that $$\forall v \in \mathcal{D}: \quad\left\langle\nabla f\left(x^{\star}\right), v-x^{\star}\right\rangle \ge 0$$

$\textbf{My attempt}$

We have $f$ is convex and differentiable implies for all $y \in \mathcal D$, $f(y) \ge f(x^\star)+\langle\nabla f(x^\star), y-x^\star\rangle$. Substitute $y=2x^\star-v$, we get $\langle\nabla f(x^\star), v-x^\star\rangle \ge f(x^\star)- f(2x^\star-v)$

Then I'm stuck because $f(x^\star)- f(2x^\star-v) \le 0$ for all $v \in \mathcal D$.

Update:

If $x^\star$ is an interior point of $\mathcal D$, then $\nabla f(x^\star) = 0$. The claim then follows. The only problem is when $x^\star$ is in the boundary of $\mathcal D$.

---

How can I proceed to finish the proof? Thank you so much!

Answer 1

I've just figured out a proof and posted it here.

---

We need the following lemma:

$\textbf{Lemma} \quad$ If $f:[0,1] \to \mathbb R$ such that $f'(0^+) <0$, then $0$ is not a minimizer of $f$.

$\textbf{Proof} \quad$ We have $$f'(0) = \lim_{x \to 0^+} \frac{f(x)-f(0)}{x-0} =\lim_{x \to 0^+} \frac{f(x)-f(0)}{x} <0$$ It follows that there exists $1>a > 0$ such that $\frac{f(a)-f(0)}{a} <0$. Hence $f(a)<f(0)$. $\blacksquare$

Come back to our main problem. Assume there exists $v\in \mathcal D$ such that $\left\langle\nabla f\left(x^{\star}\right), v-x^{\star}\right\rangle < 0$. Let $\mathcal D'=\{tv +(1-t)x^{\star} \mid t \in [0,1]\}$. It follows from the convexity of $\mathcal D$ that $\mathcal D' \subseteq \mathcal D$. We define $$g:[0,1] \to \mathbb R, \quad t \mapsto f(tv +(1-t)x^{\star})$$ By chain rule, $\partial g(t) = \partial f (z) \circ \partial z (t)$ with $z = tv +(1-t)x^{\star}$. This means $\partial g(0) = \langle \nabla f (z(0)), v-x^{\star} \rangle = \left\langle\nabla f\left(x^{\star}\right), v-x^{\star}\right\rangle < 0$. By $\textbf{Lemma}$, $0$ is not a minimizer of $g$ and thus $x^{\star}$ is not a minimizer of $f$ on $\mathcal D' \subseteq \mathcal D$. This is a contradiction.

Answer 2

I think my previous solution is not correct because we only define derivative for an interior point. So $g$ is not differentiable at $0$ and thus we can not apply the chain rule. I have fixed it as follows:

---

We need the following lemma:

$\textbf{Lemma} \quad$ If $f:[0,1] \to \mathbb R$ such that $\partial f(0^+) <0$, then $0$ is not a minimizer of $f$.

$\textbf{Proof} \quad$ We have $$\partial f(0^+) = \lim_{x \to 0^+} \frac{f(x)-f(0)}{x-0} =\lim_{x \to 0^+} \frac{f(x)-f(0)}{x} <0$$ It follows that there exists $1>a > 0$ such that $\frac{f(a)-f(0)}{a} <0$. Hence $f(a)<f(0)$. $\blacksquare$

Come back to our main problem. Assume there exists $v\in \mathcal D$ such that $\left\langle\nabla f\left(x^{\star}\right), v-x^{\star}\right\rangle < 0$. Let $\mathcal D'=\{tv +(1-t)x^{\star} \mid t \in [0,1]\}$. It follows from the convexity of $\mathcal D$ that $\mathcal D' \subseteq \mathcal D$.

Consider $$g:[0,1] \to \mathbb R, \quad t \mapsto f(tv +(1-t)x^{\star})$$ We have $$\begin{aligned} \partial g(0^+) &= \lim_{t \to 0^+} \frac{g(t)-g(0)}{t-0} &&= \lim_{t \to 0^+} \frac{f(tv +(1-t)x^{\star})-f(x^\star)}{t} \\ &= \lim_{t \to 0^+} \frac{f(t(v-x^{\star}) +x^{\star})-f(x^\star)}{t} &&= \lim_{t \to 0} \frac{f(t(v-x^{\star}) +x^{\star})-f(x^\star)}{t} \\ &= \partial_{v-x^\star}f(x^\star) &&= \partial f(x^\star)(v-x^\star) \\ &= \left\langle\nabla f\left(x^{\star}\right), v-x^{\star}\right\rangle <0\end{aligned}$$ By $\textbf{Lemma}$, $0$ is not a minimizer of $g$ and thus $x^{\star}$ is not a minimizer of $f$ on $\mathcal D' \subseteq \mathcal D$. This is a contradiction.