凸函数的局部最优也是全局最优的证明

本文主要是介绍凸函数的局部最优也是全局最优的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个性质早就知道了，但并不太清楚严谨的证明是什么。这也是《Introduction to linear optimization》书中第三章课后题的第一题。这篇博客给出严谨的证明。

Exercise 3.1 (Local minimum of convex functions)

Let $f:{\mathcal{R}}^n\to \mathcal{R}$ be a convex function and let $S\in {\mathcal{R}}^n$ be a convex set. Let $x^{\ast }$ be an element of $S$. Suppose that $x^{\ast }$ is a local optimum for the problem of minimizing $f(x)$ over $S$; that is, there exists some $ϵ>0$ such that $f(x^{\ast })\le f(x)$ for all $x\in S$ for which $|x-x^{\ast }|\le ϵ$. Prove that $x^{\ast }$ is globally optimal; that is, $f(x^{\ast })\le f(x)$ for all $x\in S$.

---

Solution:

We prove this problem by contradiction (反证法).

Proof.

Suppose that there exists a point $x_0\in S$ in which $f(x_0)<f(x^{\ast })$. Since $f(x)$ is a convex function, for any $\lambda \in [0,1]$,

$$f(\lambda x^{\ast }+(1-\lambda )x_0)\le \lambda f(x^{\ast })+(1-\lambda )f(x_0).$$

Since $f(x_0)<f(x^{\ast })$,

$$f(\lambda x^{\ast }+(1-\lambda )x_0)<\lambda f(x^{\ast })+(1-\lambda )f(x^{\ast })=f(x^{\ast }).$$

We can find a $\lambda$ that makes $\lambda x^{\ast }+(1-\lambda )x_0$ locates at the neighbourhood of $x^{\ast }$, i.e.,
$$x^{\ast }-ϵ\le \lambda x^{\ast }+(1-\lambda )x_0\le x^{\ast }+ϵ;$$

i.e., we can make $\lambda$ satisfies:

$$-ϵ\le (1-\lambda )(x^{\ast }-x^0)\le ϵ;$$

i.e., we can make $\lambda$ satisfies:
$$1-\lambda \le \frac{ϵ}{|x_0-x^{\ast }|}.$$

This $\lambda$ does exist, so there will exists a point in the neigourhood of $x^{\ast }$ but its function value is smaller than $f(x^{\ast })$, which contradicts that $x^{\ast }$ is a local minimum.

$\square$

这篇关于凸函数的局部最优也是全局最优的证明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---