Convex Optimization Note 1 | Int

作者: 今天又忘记密码 | 来源:发表于2019-04-15 23:44 被阅读0次

凸优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单，譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用，如次导数等。凸优化应用于很多学科领域，诸如自动控制系统，信号处理，通讯和网络，电子电路设计，数据分析和建模，统计学（最优化设计），以及金融。在近来运算能力提高和最优化理论发展的背景下，一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化（凸最小化）问题，例如求凹函数 $f$ 最大值的问题就等同于求凸函数 $-f$ 最小值的问题。^[1]下面的这些理论证明等主要来自于NESTEROV的书^[2]。

凸优化和机器学习

假设我们有两个空间，样本空间 $\mathcal{X}$ ，标签空间 $\mathcal{Y}$ ，还有一个参数空间 $\mathcal{H}$ 包括了从样本到标签的映射，引入它们之间的Loss Function $L:\mathcal{Y}\times\mathcal{Y} \rightarrow \mathbb{R}$ ，如果已经知道这些样本和标签 $\mathcal{X}\times\mathcal{Y}$ 的分布 $P$ ，

经验风险最小

$\mathcal{L}_{P}=\mathbb{E}_{P} [L(h(x), y)].$

学习的目标就是求解一个最优化问题：

$\min_{h\in \mathcal{H}}\mathcal{L}_{P}(h).$

常规的做法就是使得经验风险最小，也就是把训练样本全部跑一遍，然后使得通过我们的误差函数累计计算出来的值最小。

$\min_{h\in \mathcal{H}}\sum^{n}_{i=1}L(h(x_i), y_{i})=\min_{\theta}\sum^{n}_{i=1}L(h_{\theta}(x_{i}),y_{i}).$

当标签是离散值的时候看作是分类任务，当标签是连续值的时候看作是回归任务。

一般情况下，求解这种任务是 NP 难的问题，所以引入另一种替代的办法，用Hinge Loss表示 $[0, 1]$ 误差，这样也就使得其有了梯度，而且这种代价函数和原来的代价函数是等价的。引入松弛变量构造一个带约束的最优化函数。

$\min_{\omega}\sum^{n}_{i=1}\zeta_{i}$
$s.t.\quad \begin{array}{l} y_{i}(x_{i}^{T}w+b) + \zeta_{i} \geq 1, \\ \zeta_{i} \geq 0, \\ ||w||^2_{2} \leq \Lambda \end{array}$

最后一项 $||w||^2_{2} \leq \Lambda$ 是用于约束回归参数的复杂度，用于防止过拟合。一般用拉格朗日乘子法可以对原来约束条件下的方程进行改写得到：

$\min_{\omega}\sum^{n}_{i=1}\zeta_{i} + ||w||^2_{2} - \lambda \Lambda$
$s.t.\quad \begin{array}{l} y_{i}(x_{i}^{T}w+b) + \zeta_{i} \geq 1, \\ \zeta_{i} \geq 0. \end{array}$

还有几种常用的损失函数：

Square loss: $\Phi_{s}(y,y')=(1-yy')^2.$
Logistic loss: $\Phi_{l}(y,y')=\frac{1}{ln2}ln(1-e^{-yy'}).$
Cross entropy loss: $\Phi_{c}(y,y')=-tln(y')-(1-t)ln(1-y').$ 其中 $t=(1+y)/2.$

极大似然视角下

极大似然估计法下，一个似然函数 $P(X,Y|\theta)$ 的估计可以通过下面的公式得到。

$\begin{array}{rl} \theta_{MLE} & = \text{argmin}_{\theta}P(X,Y|\theta) = \text{argmax}_{\theta}\log P(X, Y|\theta) \\ & = \text{argmax}_{\theta}\log \prod_{i}P(x_i, y_i|\theta) \\ & = \text{argmax}_{\theta}\sum^{n}_{i=1}\log P(x_{i}, y_{i}|\theta)\end{array}$

极大后验视角下

如果将其中的极大似然估计替换成极大后验估计，可以改写成下面这样的形式。

$\begin{array}{rl} \theta_{MAP} & = \text{argmax}_{\theta}P(X, Y|\theta) P(\theta) =\text{argmax}_{\theta} \log\{ P(\theta)P(X,Y|\theta) \}\\ &=\text{argmax}_{\theta}\log \{ P(\theta)\prod_{i}P(x_{i}, y_{i}|\theta) \}\\ &=\text{argmax}_{\theta} \{ \log P(\theta) + \sum^{n}_{i=1}P(x_{i}, y_{i}|\theta) \} \\ \end{array}$

问题泛化

令 $x$ 是一个 $n$ 维实向量：

$x=(x^{(1)},\dots, x^{(n)} )^{T} \in \mathbb{R}^{n},$

$S$ 是 $\mathbb{R}^{n}$ 一个子集，且 $f_{0}(x),\dots,f_{m}(x)$ 是 $x$ 的一些实值函数，一般的约束问题都写成下面的形式：

$\min f_{0}(x)$
$s.t. \begin{array}{l} f_{j}(x) \leq 0, j=1,\dots m,\\ x\in S. \end{array}$

以上的 $f_{0}(x)$ 是我们的目标（objective）函数，而考虑最小化问题只是一种分析习惯，其他形式的优化也可以改写成这种形式，向量函数
$f(x)=(f_{1}(x),\dots, f_{m}(x))^{T}$
称为函数约束（functional constraints）向量，集合 $S$ 称为基本可行集（basic feasible set），并且集合
$Q=\{x\in S|f_{j}(x) \leq 0, j=1\dots m\}$
称为问题的可行集（basic set）。如果 $Q\neq \emptyset$ 则说明这是一个可行的问题，如果存在 $x\in \int Q$ ，对于所有不等式约束都满足 $f_{j}(x)<0$ 则称为严格可行的（strictly feasible）。

问题的自然分类

有约束问题（constrained problems）： $Q\subset\mathbb{R}^{n}$ 。
无约束问题（unconstrained problems）： $Q\equiv \mathbb{R}^{n}$ 。
光滑问题（smooth problems）：所有的 $f_{i}(x)$ 是可微的。
非光滑问题（nonsmooth problems）：存在不可微的分量 $f_{k}(k)$ 。

对于线性约束问题（linearly constrained problems）：所有泛函数约束都是线性的。线性约束问题可以继续分为：

线性优化问题：如果 $f_{0}(x)$ 也是线性的，那么这个最小化问题就是一个线性优化问题。
二次优化问题：如果 $f_{0}(x)$ 是二次的，那么这就是一个二次优化问题
二次约束的二次问题：如果所有的 $f_{j}$ 是二次的，那么这就是一个二次约束的二次问题（quadratically constrained quadratic problem）。

解的定义

这种最优化问题中一般会存在多种解：

$x^{*}$ 是全局解（global solution），如果对于所有的 $x\in Q$ ，有
$f_{0}(x^{*}) \leq f_{0}(x).$
在这种情况下， $f_{0}(x^{*})$ 称为问题的（全局）最优值（optimal value）。
$x^{*}$ 如果只是在一个局部 $x\in NBR(x^{*}, \delta)\cap Q$ ，有
$f_{0}(x^{*}) \leq f_{0}(x).$
则称之为局部解。

非线性优化式非常重要和有前途的应用理论。它覆盖了几乎所有的运筹学和数值分析的需求（包括现在大量的机器学习内容）虽然总体上看，优化问题是无解的。

数值方法的性能

特定的问题因为它本身可能存在个各种特别的性质，某些方法可以有非常独特的求解性能。所以要对一类问题（ $\mathcal{P}\in \mathcal{F}$ ）来讨论某些方法的性能，在这类问题中都存在相似的特点，而某种数值方法会对这些方法都有一定的性能。

因此，一个方法 $\mathcal{M}$ 在整个类 $\mathcal{F}$ 上的性能（performance）是它的效率的一个自然特性。

符号约定

模型：问题 $\mathcal{P}$ 的一个已知（known）的“部分”，称为问题的模型（model）。我们用 $\Sigma$ 来表示模型。通常，模型包含了问题形式，泛函分量的类型描述，等等。
Oracle：为了识别问题 $\mathcal{P}$ （并且求解它），方法应该能够搜集关于 $\mathcal{P}$ 的特定的信息。为了方便，搜集数据的过程被描述为一个 oracle。一个 oracle $\mathcal{O}$ 就是一个单位，它回答方法连续的询问。方法 $\mathcal{M}$ 试图通过搜集和处理回答，来求解问题 $\mathcal{P}$ 。
求解一个问题所需要的努力程度（computational efforts）的总量是一个方法 $\mathcal{M}$ 的性能。
逼近解：求解一个问题要找到一个准确度为 $\varepsilon > 0$ 的逼近解。

常规求解流程

给定初始点 $x_{0}$ 和准确度 $\varepsilon>0$ 和初始化： $k=0$ ，初始的信息 $I_{-1}=\emptyset$ 。

在 $x_{k}$ 调用oracle $\mathcal{O}$ 。
更新信息集： $I_{k}=I_{k-1}\cap (x_{k},\mathcal{O}(x_{k}))$ 。
对 $I_{k}$ 运用方法 $\mathcal{M}$ 的规则，形成点 $x_{k+1}$
检查停止条件 $\mathcal{T}_{\varepsilon}$ 。如果满足条件，则形成输出 $\bar{x}$ 。否则设置 $k:=k+1$ 循环步骤。

真正对于求解问题起作用的是步骤1和环步骤3，这两个步骤也是计算代价集中的地方，我们对这些步骤进行更加具体的分析，有

解析复杂性（analytical complexity）：求解问题 $\mathcal{P}$ ，达到准确率 $\varepsilon$ 所需要调用的orcal的数量。
算术复杂性（arithmetical complexity）：求解问题 $\mathcal{P}$ ，达到准确率 $\varepsilon$ ，所需要的算术操作的总数量（包括Oracle方法的工作）。

Oracle

一般用局部黑盒概念（local black box concept）假设oracle能让我们得到优化问题解析复杂度的大部分结果，而距离测试点 $x$ （或者叫当前的采样点）很远的小问题变化不会影响在 $x$ 的回答。

继续沿用上面最小化问题的问题表述形式，针对这样一种泛化模型（functional model）假定根据函数的光滑性程度，可以使用不同类型的oracle：

零阶oracle（zero-order oracle）：
返回 $f(x)$ 的值。
一阶oracle（first-order oracle）：
返回 $f(x)$ 和梯度 $f'(x)$ 的值。
二阶oracle（second-order oracle）：
返回 $f(x)$ ，梯度 $f'(x)$ ，和Hessian $f''(x)$ 的值。

全局优化中复杂度的界

Lipschitz连续

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

$|f(x)-f(y)| \leq L||x-y||_{\infty}$

其中， $L$ 是某个Lipschitz常量（Lipschitz constant）

范数 $l_{\infty}$ 测量 $\mathbb{R}^{n}$ 中的距离：

$||x||_{\infty}=\max_{1\leq i \leq n}|x^{(i)}|.$

上界分析

根据Lipschitz连续我们可以构造一种零阶的求解方法（它的另一个名字应该是暴力枚举在一定精度下的全部可行解）。在每个维度上都把坐标平均间隔成 $p$ 个点，然后在所有点中找到 $\bar{x}$ ，使得目标函数具有最小的值。如果令 $f^{*}$ 是问题的全局最优值。其中点构造为
$x_{\alpha}=((\frac{2i_{1}-1)}{2p}), (\frac{2i_{2}-1)}{2p}), \dots, (\frac{2i_{n}-1)}{2p}))^{T}$
那么
$f(\bar{x})-f^{*} \leq \frac{L}{2p}.$

证明：给定一个多维索引 $\alpha=(i_1, \dots, i_n)\in \{1, \dots, p\}^{n}.$ ，定义这个点步长以内的领域范围
$X_{\alpha}=\{ x\in \mathbb{R}^{n}: ||x-x_{\alpha}||_{\infty} \leq \frac{1}{2p} \}.$

很明显这些坐标的全部集合就是函数的可行域： $\cap_{\alpha\in \{1,\dots, p\}^{n}}X_{\alpha}=B_{n}$ ，如果这个函数存在一个全局最优解，则在网格离散的点上一定有一个索引值 $\alpha^{*}$ 索引的网格点的连续邻域内存在最优解（就是这个最优解在它的框框内） $x^{*}\in X_{x_{a^{*}}}$ 满足 $||x^{*}-x_{\alpha^{*}}||_{\infty} \leq \frac{1}{2p}.$ ，因此有，

$f(\bar{x}) - f(x^{*}) \leq f(x_{a^{*}})-f(x^{*}) \leq \frac{L}{2p}.$

把这个问题推广到一系列的问题就有：

$\text{Find}~\bar{x}\in B_{n}:\quad f(\bar{x})-f^{*} \leq \varepsilon.$

也就有如果要得到精度在 $\varepsilon$ 以内的解，这个方法的复杂度就在
$\mathscr{A}(\mathscr{G}=(\lfloor \frac{L}{2\varepsilon}\rfloor+1)^{n},$
所以令 $p=\lfloor \frac{L}{2\varepsilon}\rfloor+1 \geq \frac{L}{2\varepsilon}$ 也就有 $f(\bar{x}-f^{*}) \leq \frac{L}{2p} \leq \varepsilon.$ 也就需要调用 $p^n$ 次oracle，这是这个方法的复杂度上界。

实际上这还不够，也许在这种问题形式下还有更好的方法，或者实际上方法 $\mathscr{G}$ 的性能更好，所以再进一步分析求解这种问题的下界，下面的分析基于一些特点：

它们基于黑盒（black box）的概念。
这些界对于所有合理的迭代方案都有效，因此，它们给我们提供的是对于这个问题类的解析复杂度的下估计（lower estimate）。
这些界都用了抵抗 oracle（resisting oracle）的思想。
- 对于每个特定方法（for example，，一个抵抗oracle试图创建一个最坏（worst）问题：
  - 它从一个“空”的函数开始，并且试图用最坏可能的方式回答这个方法的每一个调用。
  - 这个回答必须和前面的回答以及问题类的描述兼容（compatible）

下界分析

首先定义下面这样的问题，有模型 $\min_{x\in \mathbb{B}_{n}}f(x)$ 且 $f(x)$ 在 $\mathbb{B}_{n}$ 上是 $\mathscr{C}_{\infty} Lipschitz$ 连续的。用于收集信息的 Oracle是一个零阶黑盒。目标是为了寻找一个逼近解 $\bar{x}\in \mathbb{B}_{n}:f(\bar{x})-f^{*} \leq \varepsilon$ 。根据我们的分析要取得 $\varepsilon$ 的精度，问题 $\mathscr{C}$ 的解析复杂度至少为 $(\lfloor \frac{L}{2\varepsilon}\rfloor)^n(\geq 1)$ 。
我们假设有一种方法可以使得 $N < p^{n}$ 以内把问题 $\mathscr{P}$ 解决掉，然后再弄一个Oracle，它在任意测试点都返回 $f(x)=0$ ，然而因为有 $N < p^n$ 所以还会存在一个多维索引 $\hat{\alpha}$ 使得在箱子 $X_{\hat{\alpha}}$ 内不存在测试点。写成数学形式如下

$\bar{f}(x)=\min\{ 0, L||x-x_{*}||_{\infty}-\varepsilon \}.$

构造出来的这个函数是满足常数 $L$ 的 $\mathscr{C}_{\infty}$ -Lipschitz 连续。它的全局最有解为 $-\varepsilon$ 这样，如果搜索的量小于 $p^n$ 那结果肯定不可能超过 $\varepsilon$ 这是根据比较一般的形式构造出的满足条件的最好的情况了，如果连这个都不能达到，那在最普遍情况下也就达不到更好的结果了。

所以我们可以确定在使用暴力的网格法求解的下界：
$\mathscr{G}:(\lfloor \frac{L}{2\varepsilon} \rfloor + 1)^n \Leftrightarrow \text{Lower bound:}\lfloor \frac{L}{2\varepsilon} \rfloor^n.$

可以看到这种问题几乎是时间上不可解的，而且推导出的下界也未必比上界更好一些。把这结果和那种NP-难问题的上界进行比较，是组合优化中经典的困难问题，真是让人失望。而像这种网格法在数值计算中还是满常见的，比如数值积分^[3]。

松弛和逼近

非线性优化中，简单的目标是找到可微函数的局部最小值。但是很多情况下这些函数的全局结构不会比 Lipschitz 连续函数更简单。所以目前大部分的一般非线性优化的方法基于松弛（relaxation）思想：

一个序列 $\{a_{k}\}^{\infty}_{k=0}$ 如果 $a_{k+1}\leq a_{k}, \forall~k\geq 0.$ 它是一个松弛序列（relaxation sequence）

逼近意味着一个简化的目标函数替换初始的目标函数，在属性上简化函数和原函数的距离非常接近

在非线性优化中常用非线性函数的导数来使用局部（local）逼近。这些就是一阶和二阶逼近（或者也叫线性和平方逼近）。

一阶逼近

如果 $f(x)$ 在 $\bar{x}$ 是可微的，那么对于 $y\in \mathbb{R}^{n}$ ，我们有
$f(y)=f(\bar{x})+\langle \nabla f(x), y-\bar{x} \rangle + o(||y-\bar{x}||).$

线性函数 $f(\bar{x})+\langle \nabla f(\bar{x}), y-\bar{x} \rangle$ 称为 $f$ 在 $\bar{x}$ 的线性逼近（linear approximation），其中 $\langle \cdot, \cdot \rangle$ 表示内积。

$\nabla f(x)=(\frac{\partial f(x)}{\partial x^{(1)}}, \dots, \frac{\partial f(x)}{\partial x^{(n)}})^{T}$

将函数 $f(x)$ 的次层集（sublevel set）记作 $\mathscr{L}_{f}(\alpha)$ （也可以看作是等高线以下内容）：
$\mathscr{L}_{f}(\alpha)=\{x\in \mathbb{R}^{n} | f(x) \leq \alpha \}.$

考虑在 $\bar{x}$ 上和 $\mathscr{L}_{f}(f(\bar{x}))$ 相切方向集合：
$S_{f}(\bar{x})=\left \{ s\in \mathbb{R}^{n}|s= \lim_{y_k \rightarrow \bar{x}, f(y_{k})=f(\bar{x})} \frac{y_k - \bar{x}}{||y_k - \bar{x}||}, \text{for some}~\{y_k\} \rightarrow \bar{x}~\text{with}~f(y_k)=f(\bar{x}) \forall k \right \}.$

如果 $f(y_k)=f(\bar{x})$ ，我们有
$f(y_k)=f(\bar{x}) + \langle \nabla f(\bar{x}), y_k - \bar{x} \rangle + o(||y_k - \bar{x}||)=f(\bar{x}).$
因为 $\lim_{r \downarrow 0}\frac{1}{r}o(r)=0, o(0)=0$ 所以等号两边同时除以 $||y_k-\bar{x}||$ 然后让 $y_k \rightarrow \bar{x}$ 我们就得到：
$if~s\in S_{f}(\bar{x}), then~\langle \nabla f(\bar{x}), s \rangle=0.$

$s\in S_f(\bar{x})$ 其实就是表示 $\mathbb{R}^{n}$ 中的方向， $||s||=1$ 。

$\Delta (s)=\lim_{\alpha \downarrow 0}\frac{1}{\alpha}[f(\bar{x} + \alpha s)-f(\bar{x})].$
最后得到
$\Delta (s)=\langle \nabla f(\bar{x}), s\rangle .$
通过 Cauchy-Schwarz 不等式，
$-||x||\cdot ||y|| \leq \langle x, y\rangle \leq ||x||\cdot ||y||,$
推出 $\Delta (s)=\langle \nabla f(\bar{x}), s\rangle \geq -||\nabla f(\bar{x}||.$ 继续再让
$\bar{s}=-\nabla f(\bar{x})/||\nabla f(\bar{x})||.$
带入原来的方程中得到
$\Delta (\bar{s})=-\langle \nabla f(\bar{x}), \nabla f(\bar{x}) \rangle / ||\nabla f(\bar{x}) || = -||\nabla f(\bar{x})||.$
所以，反梯度方向 $-\nabla f(\bar{x})$ 是最快的下降方向。

一阶优化条件

令 $x^{*}$ 是一个可微函数 $f(x)$ 的局部最小点。那么 $\nabla f(x^{*})=0$ ，而且它周围点 $||y-x^{*}|| \leq r, ~\text{and}~r>0$ 上的函数值都应该比最优点上面的函数值大 $f(y) \geq f(x^{*})$ ，而且 $f$ 可微
$f(y) = f(x^{*}) + \langle \nabla f(x^{*}, y-x^{*}\rangle + o(||y-x^{*}||) \geq f(x^{*}).$
因此对于所有的 $s\in \mathbb{R}^{n}$ ，我们有 $\langle \nabla f(x^{*}), s \rangle \geq 0.$ 如果取 $s=-\nabla f(x^{*})$ 则有 $-||\nabla f(x^{*})|| \geq 0.$ 当且仅当 $\nabla f(x^{*})=0.$

但是这仅仅是一个最小值的必要条件，满足这个条件的可能只是个 $f$ 的静点，所以还需要二阶的信息。

二阶逼近

令函数 $f(x)$ 在 $\bar{x}$ 上是二次可微的，那么
$f(y)=f(\bar{x})+\langle \nabla f(x), y-\bar{x} \rangle + \frac{1}{2} \langle \nabla^2 f(\bar{x})(y-\bar{x}), y-\bar{x} \rangle + o(||y-\bar{x}||^2).$

定义函数 $f$ 在 $x$ 的 Hessian（对称矩阵）

$\nabla^2 f(\bar{x})^{(i, j)} = \frac{\partial^2 f(\bar{x})}{\partial x^{(i)} \partial x^{(j)}}$
对于对称矩阵 $A \succeq 0$ 表示 $A$ 是正半定的（positive semidefine）：
$\langle Ax, x \rangle \geq 0 ~\forall x\in \mathbb{R}^{n}.$
如果这个点是一个局部最小点，那么它的二阶导应该至少有大于0的分量
$\nabla f(x^{*}) = 0, \nabla^2 f(x^{*})\succeq 0.$
对于所有的 $s$ ， $||s||=1$ ，有 $\langle \nabla^2 f(x^{*})s, s\rangle \geq 0$ 。
如果满足以上的条件，则必要性得以满足，那么 $x^{*}$ 是 $f(x)$ 的一个严格的局部最小点，有时候也用隔离（isolated）这个词来代替严格（strict）。

$x^{*}$ 为最优值点的充分性证明：在点 $x^{*}$ 的一个很小邻域内，函数 $f(\cdot)$ 可以表达成
$f(y)=f(x^{*})+\frac{1}{2}\langle \nabla^2 f(x^{*})(y-x^{*}), y-x^{*}\rangle + o(||y-x^{*}||^2).$
因为 $o(r^2)/r^2 \rightarrow$ 当 $r\downarrow 0$ ，存在一个值 $\bar{r} > 0$ 使得所有的 $r\in [0, \bar{x}]$ 有
$|o(r^2)| \leq \frac{r^2}{4} \lambda_{\min}(\nabla^2 f(x^{*})).$
根据我们的假设，这个特征值是正的，所以，对于任意 $y\in \mathbb{R}^{n}$ ， $0<||y-x^{*}||\leq \bar{r}$ 我们有
$\begin{array}{rcl} f(y) & \geq & f(x^{*}) + \frac{1}{2}\lambda_{\min}(\nabla^2 f(x^{*}))||y-x^{*}+||o(||y-x^{*}||^2)\\ & \geq & f(x^{*}) + \frac{1}{2}\lambda_{\min}(\nabla^2 f(x^{*})) + ||y-x^{*}|| > f(x^{*}).\end{array}$

根据变分不等式，对于对称矩阵 $A\in \mathbb{R}^{n\times n}$ 有
$\lambda_{\min}(A)\cdot X^TX \leq X^T AX \leq \lambda_{\max}(A)\cdot X^T X.$
所以有
$\frac{1}{2}\langle \nabla^2(y-x^{*}), y-x^{*}\rangle \geq \lambda_{\min}(\nabla^2 f(x^{*}))||y-x^{*}||^2.$

可微函数的类

Lipschitz 条件

令 $Q$ 是一个 $\mathbb{R}^{n}$ 的子集，我们记 $C^{k,p}_{L}(Q)$ 为具有下面属性的函数类：

任意 $f\in C^{k,p}_{L}(Q)$ 在 $Q$ 上是 k 次连续可微的。

它的第 $p$ 次导数在 $Q$ 上是 Lipschitz 连续的，有常量 $L$ 对于所有的 $x, y\in Q$

$||\nabla^{p}f(x)-\nabla^{p}f(y)|| \leq L||x-y||.$

显然，我们总是会有

$p\leq k$ 显然成立
如果 $q\geq k$ 那么 $C^{q,p}_{L}(Q)\subset C^{k, p}_{L}(Q)$
同时，如果 $f_1 \in C^{k, p}_{L_1}(Q)$ ， $f_2\in C^{k, p}_{L_2}(Q)$ 且 $\alpha, \beta\in \mathbb{R}^{1}$ 对于
$L_3 = |\alpha|L_1+|\beta|L_2$
有 $\alpha f_1+\beta f_2 \in C^{k, p}_{L_3}(Q)$

Lipschitz Continuous Gradient

考虑具有 Lipschitz 连续梯度的函数类，根据定义这个 $f\in C^{1, 1}_L(\mathbb{R}^n)$ 有对于所有的 $x,y \in \mathbb{R}^{n}$
$||\nabla f(x)-\nabla f(y)|| \leq L||x-y||.$

一个函数 $f$ 属于 $C^{2, 1}_L(\mathbb{R}^{n}) \subset C^{1, 1}_L(\mathbb{R}^n)$ 当且仅当对于所有的 $x\in \mathbb{R}^n$ 下面条件满足
$||\nabla^2 f(x)|| \leq L.$

证明：实际上对于任何的 $x, y\in \mathbb{R}^{n}$ 有

$\begin{array}{rl}\nabla f(y)&=\nabla f(x)+\int^{1}_{0}\nabla^2 f(x + \tau(y-x))(y-x)d\tau\\ &=\nabla f(x)+(\int^1_0 \nabla^2 f(x+\tau(y-x))d\tau)\cdot(y-x).\end{array}$

如果条件 $||\nabla^2 f(x)|| \leq L$ 成立的话有
$\begin{array}{rl} ||\nabla f(y)-\nabla f(x)|| & = ||(\int^1_0 \nabla^2 f(x+\tau(y-x))d\tau)\cdot (y-x)||\\ &\leq ||int^1_0\nabla^2 f(x+\tau(y-x))d\tau||\cdot ||y-x||\\ &\leq \int^1_0 ||\nabla^2 f(x+\tau(y-x))||d\tau \cdot ||y-x||\\ &\leq L||y-x||.\end{array}$

另外，如果 $f\in C^{2,1}_L(\mathbb{R}^n)$ ，那么对于任意的 $s\in \mathbb{R}^n$ 和 $\alpha > 0$ 有
$\left \| \left (\int^{\alpha}_0 \nabla^2 f(x+\tau s)d\tau \right )\cdot s \right\|=||\nabla f(x+\alpha s)-\nabla f(x)|| \leq \alpha L||s||.$
证明：
我们令 $\Phi(\alpha) = (\int^{\alpha}_{0} \nabla^2 f(x+\tau s)d\tau)$ ，不等式两边同时除以 $\alpha$ ，取 $\alpha \downarrow 0$ 有
$\left \| \lim_{\alpha \downarrow 0} \frac{\Phi(\alpha)}{\alpha} \cdot s \right \| = \left \| \lim_{\alpha \downarrow 0} \frac{\Phi(\alpha)-\Phi(0)}{\alpha-0} \cdot s \right \| = ||\nabla \Phi(0)\cdot s|| \leq L||s||.$
因为 $\nabla \Phi(\alpha) = \nabla^2 f(x+\alpha s)$ ，有 $\nabla \Phi(0)=\nabla^2 f(x)$ ，所以得证。

几何解释

如果 $f\in C^{1, 1}_L(\mathbb{R}^n)$ 那么对于任意的 $x, y\in \mathbb{R}^n$ 有
$|f(y)-f(x)-\langle \nabla f(x), y-x \rangle | \leq \frac{L}{2}||y-x||^2.$

$f(y)$ 和其一阶逼近的距离的上界，因为确定了这个上界之后可以将优化复杂的函数 $f$ 等价成为优化它的上界^[4]，转化为二次规划问题^[5]。

证明如下
$\begin{array}{rl}f(y)&=f(x)+\int^1_0 \langle \nabla f(x+\tau(y-x)), y-x\rangle d\tau\\ &=f(x) + \langle \nabla f(x), y-x\rangle + \int^1_0 \langle \nabla f(x+\tau(y-x))-\nabla f(x), y-x\rangle d\tau. \end{array}$
所以
$\begin{array}{rl} |f(y)-f(x)-\langle \nabla f(x), y-x \rangle| &= \left | \int^1_0 \langle \nabla f(x+\tau(y-x)) - \nabla f(x), y-x \rangle d\tau \right |\\ & \leq \int^1_0 \left | \langle \nabla f(x+\tau(y-x)) - \nabla f(x), y-x \rangle \right | d\tau \\ & \leq \int^1_0 ||\nabla f(x+\tau(y-x)) - \nabla f(x)|| \cdot ||y-x|| d\tau \\ & \leq \int^1_0 \tau L||y-x||^2 d\tau = \frac{L}{2}||y-x||^2. \end{array}$

如果 $f \in C_{M}^{2,2}\left(\mathbb{R}^{n}\right)$ ，是一个二阶可微符合 Lipschitz 连续 Hessian 的函数类型，我们有
$\left\|\nabla^{2} f(x)-\nabla^{2} f(y)\right\| \leq M\|x-y\|, \quad \forall x, y \in \mathbb{R}^{n}$
则对于任意 $x, y \in \mathbb{R}^{n}$ ，做一次积分，再做一次积分
$\begin{array}{c}{\left\|\nabla f(y)-\nabla f(x)-\nabla^{2} f(x)(y-x)\right\| \leq \frac{M}{2}\|y-x\|^{2}} \\ {\left|f(y)-f(x)-\langle\nabla f(x), y-x\rangle-\frac{1}{2}\left\langle\nabla^{2} f(x)(y-x), y-x\right\rangle\right|} \\ { \leq \frac{M}{6}\|y-x\|^{3}}\end{array}$

证明
$\begin{array}{rl} \nabla f(y)&=\nabla f(x)+\int_{0}^{1} \nabla^{2} f(x+\tau(y-x))(y-x) d \tau \\ &=\nabla f(x)+\nabla^{2} f(x)(y-x)+\int_{0}^{1}\left(\nabla^{2} f(x+\tau(y-x))-\nabla^{2} f(x)\right)(y-x) d \tau \end{array}$
因此
$\begin{aligned} \left\|\nabla f(y)-\nabla f(x)-\nabla^{2} f(x)(y-x)\right\| &=\left\|\int_{0}^{1}\left(\nabla^{2} f(x+\tau(y-x))-\nabla^{2} f(x)\right)(y-x) d \tau\right\| \\ & \leq \int_{0}^{1}\left\|\left(\nabla^{2} f(x+\tau(y-x))-\nabla^{2} f(x)\right)(y-x)\right\| d \tau \\ & \leq \int_{0}^{1}\left\|\nabla^{2} f(x+\tau(y-x))-\nabla^{2} f(x)\right\| \cdot\|y-x\| d \tau \\ & \leq \int_{0}^{1} \tau M \nabla^{2} f(x+\tau(y-x))-\nabla^{2} f(x)\|\cdot\| y-x\|d \tau\\ & \leq \int_{0}^{1} \tau M\|y-x\|^{2} d \tau=\frac{M}{2}\|y-x\|^{2} \end{aligned}$

令 $f \in C_{M}^{2,2}\left(\mathbb{R}^{n}\right)$ 并且 $x, y \in \mathbb{R}^{n}$ with $\|y-x\|=r$ 可以有
$\nabla^{2} f(x)-M r I_{n} \preceq \nabla^{2} f(y) \preceq \nabla^{2} f(x)+M r I_{n}$

证明
我们令 $G=\nabla^{2} f(y)-\nabla^{2} f(x)$ 是一个矩阵，因为 $f \in C_{M}^{2,2}\left(\mathbb{R}^{n}\right)$ ，所以它肯定会被限制在这个界限内 $\|G\| \leq M r$ 这意味着矩阵中每个特征值都在这个界限内。
所以我们有
$-M r I_{n} \preceq G \equiv \nabla^{2} f(y)-\nabla^{2} f(x) \preceq M r I_{n}$

凸优化维基百科 ↩
NESTEROV J E. Lectures on convex optimization[M]. 2018. ↩
Numerical integration ↩
Lipschitz-gradient by xingyuzhou ↩
Quadratic_programming ↩