Lipschitz Condition

L-lipschitz连续性是最近优化课程经常提到的一个基础内容，老师人很nice，讲课也很有开放性，每次都需要做大量的预习和课后复习才能完全消化。所以最近的Blog基本上都离不开数学主题了。
课堂引出L-lipschitz是为了衡量一个凸函数是否容易优化，通过函数光滑的程度和凸的程度来判断，原文是：$\nabla f$ is L-lipschitz and $f$ $\mu$-strongly convex.

---

Definition of Lipschitz Continuous

If $f$ is Lipschitz continuous on $Q$ with constant $L$，if for all $x, y\in Q$ we have：

$$||f(x)-f(y)||\leq L||x-y||$$

If $f$ is Lipschitz continuous gradient on $R^n$. Then for any $x, y\in R^n$ we have：

$$|f(y)-f(x)-\langle f'(x)，y-x\rangle |\leq \frac{L}{2}||y-x||^2$$

If $f$ is Lipschitz continuous Hessian on $R^n$. Then for any $x, y\in R^n$ we have：

$$|f(y)-f(x)-\langle f'(x)，y-x\rangle-\frac{1}{2}\langle f''(x)(y-x)，y-x\rangle |\leq \frac{L}{6}||y-x||^3$$

在知乎文章中主要提到了这三种Lipschitz Continuous：

1. Lipschitz continuous：函数被一次函数上下夹逼
2. Lipschitz continuous gradient：函数被二次函数上下夹逼
3. Lipschitz continuous Hessian：函数被三次函数上下夹逼

通过对函数求导，可以构造出更高阶的Lipschitz continuous condition。其中，gradient是一阶导数，Hessian是二阶导数。

Lipschitz continuous 用在函数值上是为了不让函数值变化的太快；用在导函数上，是为了不让导函数变化的太快；用在Hessian上，是为了让Hessian不变化的太快。但他们都导致了一个很有意思的结果：这个Lipschitz continuous不管用在什么上，都使的函数被多项式上下夹逼，一方面便于我们处理，另一方面至少我们能控制一下函数的包络信息。

参考

https://zhuanlan.zhihu.com/p/27554191
https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality
https://zh.wikipedia.org/wiki/%E5%88%A9%E6%99%AE%E5%B8%8C%E8%8C%A8%E9%80%A3%E7%BA%8C
https://users.wpi.edu/~walker/MA500/HANDOUTS/LipschitzContinuity.pdf
http://www.win.tue.nl/~rvhassel/Onderwijs/Old-Onderwijs/2WA23-2011/HO-03.pdf