根据神秘言论：L-Lipschitz smooth 是凸优化与非凸优化理论中最基础、最常用的正则性假设之一。
定义：对于 \(L > 0\)，如果 \(f: {\mathbb E} \to {\mathbb R}\) 是 L-smooth，则有：
\[\|\nabla f(x) - \nabla f(y) \|_* \le L \| x - y\|
\]
其中 \(\|\cdot\|_*\) 表示 \(\mathbb E\) 的对偶空间的 L2 范数。
| 形式 |
表达式 |
适用场景 |
| 梯度 Lipschitz |
\(|\nabla f(x) - \nabla f(y)| \leq L |x-y|\) |
原始定义，最通用 |
| Hessian 有界 |
\(|\nabla^2 f(x)|_2 \leq L,\ \forall x\) |
二阶可微时等价，直观表示“最大曲率” |
| 二次上界 |
\(f(y) \leq f(x) + \langle \nabla f(x), y-x \rangle + \frac{L}{2}|y-x|^2\) |
优化证明中最常用，直接给出函数值的上界 |
内积是标量乘法在向量空间的自然延伸，所以采用内积代替：
\[f(y) = f(x) + f'(x)(y - x) + \frac {f'(x + \theta(y - x))} {2} (y - x)^2, \theta \in[0, 1]
\]
也就是：
\[f(y) = f(x) + \langle \nabla f(x) , y - x \rangle + \frac 1 2 (y - x)^T \nabla^2 f(\xi) (y - x)
\]
为什么是 \((y - x)^T \nabla^2 f(\xi) (y - x)\) 就要涉及到求导法则和 Hessian 矩阵的相关知识了：[[矩阵、多元求导]]
考虑到 Hessian 矩阵可以认为一定是实对称的，所以有：
\[|u^T H u \| = \|(Qu)^T \Lambda (Qu) | = |\sum \lambda_i v_i^2| \le \sum |\lambda_i| v_i^2 \le \left(\sum |\lambda_i| \right)^2\left(\| v_i\|\right)^2
\]
考虑到 \(Q\) 不改变范数，也就是 \(\|v_i\| = \|u_i\|\)，那么根据 \(\|H\|_2\) 谱范数的定义：\(\|H\|_2 = \sup \frac {\|Hx\|_2}{\|x\|_x} = \sqrt{\lambda_{max}(H^T H)}\)
\[(y - x)^T \nabla^2 f(\xi) (y - x) \le \|\nabla^2 f(\xi) \| \cdot \|y - x\|^2
\]
利用梯度不等式求导后的结论，那么有：
\[f(y) \leq f(x) + \langle \nabla f(x), y-x \rangle + \frac{L}{2}\|y-x\|^2
\]
当然我们可以深入一下这个展开的部分的推导。
首先我们对于 \(f({\bf x})\) 在 \(x_0\) 处的展开可以构造一个单变元函数，这样就可以用最简单的泰勒展开了：
\[h(t) = f({\bf x_0} + t({\bf x - x_0}))
\]
则考虑 \(h(t)\) 在 \(0\) 处的展开，然后带入 \(t = 1\)：
\[h(t) = h(0) + h'(0) t + \frac 1 2 h''(0) t^2 + \cdots
\]
根据求导法则：
\[\frac {dh(t)} {dt} = \frac {\partial f} {\partial u} \frac {du} {dt} = \nabla f({\bf x_0} + t({\bf x - x_0}))^T ({\bf x - x_0}) = \langle \nabla f({\bf x_0} + t({\bf x - x_0})), {\bf x - x_0} \rangle
\]
继续求二阶导：
\[\begin{aligned}
\frac {d^2 h(t)} {d^2 t} &= \frac {d \nabla f({\bf x_0} + t({\bf x - x_0}))^T ({\bf x - x_0})}{dt} \\
&= \left(\frac {\partial \nabla f(u) } {\partial u} \frac {du} {dt} \right )^T ({\bf x - x_0}) \\
&= \left( \nabla^2 f({\bf x_0} + t({\bf x - x_0})) ({\bf x - x_0}) \right)^T ({\bf x - x_0}) \\
&= ({\bf x - x_0})^T \nabla^2 f({\bf x_0} + t({\bf x - x_0})) ({\bf x - x_0})
\end{aligned}
\]
然后带入我们需要的导数中 \(t = 0\) 求 \(h(1)\)，并且利用拉格朗日余项，那么得到：
\[f({\bf x}) = f({\bf x_0}) + \langle \nabla f({\bf x_0}), {\bf h} \rangle + \frac 1 2 {\bf h}^T \nabla^2 f({\bf x_0} + \theta {\bf h}) {\bf h}
\]
我们继续深入一下放缩的方法。
对于 \(\langle \nabla f({\bf x_0}), {\bf h} \rangle\)，利用柯西不等式，则有 \(|\langle \nabla f({\bf x_0}), {\bf h} \rangle| \le \| \nabla f({\bf x_0}) \| \| {\bf h} \|\)
柯西不等式可以扩展到任意内积运算上，例如：
\(\langle f, g \rangle = \int_a^b f(x) g(x) dx\) 有 \(\left( \int_a^b f(x)g(x) dx \right)^2 \le \left( \int_a^b f(x)^2 dx \right) \left( \int_a^b g(x)^2 dx \right)\)
\(\langle A, B \rangle = \text{tr}(A^T B)\) 有 \(|\text{tr}(A^T B)| \le \|A\|_F \|B\|_F\)
对于 \(\frac 1 2 {\bf h}^T \nabla^2 f({\bf x_0} + \theta {\bf h}) {\bf h}\)，由于知道 \(\nabla^2\) 是对称矩阵：
\[\nabla^2 f({\bf x}) = \begin{bmatrix}
\frac {\partial^2 f}{ \partial x_1 \partial x_1} & \frac {\partial^2 f}{ \partial x_1 \partial x_2} & \cdots & \frac {\partial^2 f}{ \partial x_1 \partial x_n} \\
\frac {\partial^2 f}{ \partial x_2 \partial x_1} & \frac {\partial^2 f}{ \partial x_2 \partial x_2} & \cdots & \frac {\partial^2 f}{ \partial x_2 \partial x_n} \\
\vdots & \vdots & \ddots & \vdots \\
\frac {\partial^2 f}{ \partial x_n \partial x_1} & \frac {\partial^2 f}{ \partial x_n \partial x_2} & \cdots & \frac {\partial^2 f}{ \partial x_n \partial x_n}
\end{bmatrix}
\]
根据 \(f\) 的连续性（可能会有特殊情况，不考虑了），有：
\[\frac {\partial^2 f}{ \partial x_i \partial x_j} = \frac {\partial^2 f}{ \partial x_j \partial x_i}
\]
于是这就对称了。
我们知道，对于一个对称矩阵，必定能对角化，所以可以转化为 \(Q \Lambda Q^T\) 的形式。就有了上文的证明。
至于为什么，这就问线性代数去吧
