前置知识
梯度
对于一个多元函数$f:R^n \rightarrow R$，其梯度是一个向量：
$$
\nabla f(x) = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \dots,\frac{\partial f}{\partial x_n} \right)^T
$$
p-范数
对于一个n维向量$x=(x_1,x_2,\dots,x_n)$，其p-范数定义为：
$$
\Vert x \Vert_p = \left(\sum_{i=1}^n |x_i|^p \right) ^{\frac{1}{p}}
$$
$p=1$：曼哈顿范数（L1范数）
$$
\Vert x \Vert = \sum_{i=1}^n |x_i|
$$
表示向量$x$各个分量绝对值的和
$p=2$：欧几里得范数（L2范数）
$$
\Vert x \Vert_2 = \sqrt{\sum_{i=1}^n |x_i|^2}
$$
表示欧式几何空间中向量的长度
$p \rightarrow \infty$：切比雪夫范数（无穷范数）
$$
\Vert x \Vert_\infty = \max_{1 \leq i \leq n} |x_i|
$$
表示向量$x$各个分量的最大绝对值
问题描述
$$
\min_{x \in S}f(x)
$$
$f(x)$是一个可微分的凸函数，$S$是一个紧致凸集（例如多面体、单纯形、单位球）
⭐算法逻辑
通常称之为条件梯度法（Conditional Gradient Method）
选取初始点$x^{(0)} \in S$，每一步$k=0,1,2,\dots$
计算当前点的梯度：
$$
\nabla f(x^{(k)})
$$线性子问题，在集合$S$上找到梯度方向下降最快的点：
$$
\begin{aligned}
s^{(k)}
&= \arg \min_{s \in S} \langle \nabla f(x^{(k)}), s \rangle \\
&= \arg \min_{s \in S} \nabla f(x^{(k)})^T s
\end{aligned}
$$选取步长$\gamma_k \in [0, 1]$，可以使用类似于$\gamma_k = \frac{2}{k+2}$的固定形式，或者是使用线搜索：
$$
\gamma_k = \arg \min_{\gamma \in [0, 1]} f(x^{(k)} + \gamma(s^{(k)} - x^{(k)}))
$$更新当前点：
$$
\begin{aligned}
x^{(k+1)}
&= x^{(k)} + \gamma_k(s^{(k)} - x^{(k)}) \\
&= (1-\gamma_k)x^{(k)} + \gamma_k s^{(k)}
\end{aligned}
$$
性质
- 对于光滑凸函数，该算法的收敛速度为$O(\frac{1}{k})$
简单例子
我们有
$$
f(x) = x^2 \text{ on } R^2 \\
x \in S : |x| \leq 1 $$
求
$$
\min_{x \in S}f(x)
$$
先算$f(x)$的梯度（全程只用算一次）。这个例子比较简单，$x$就是一个单元向量，有
$$
\nabla f = \langle 2x \rangle
$$
我们选择$x^{(0)} = 1$，然后
$$
\begin{aligned}
s^{(0)}
&= \arg \min_{s \in S} \langle \nabla f(x^{(0)}), s \rangle \\
&= \arg \min_{|s| \leq 1} \nabla f(1)^T s \\
&= \arg \min_{|s| \leq 1} 2s \\
&= -1
\end{aligned}
$$
以及
$$
\gamma_0 = \frac{2}{0+2} = 1
$$
得到第一次迭代后的结果
$$
x^{(1)} = (1-\gamma_0)x^{(0)} + \gamma_0 s^{(0)} = -1
$$
进入第二次迭代
$$
\begin{aligned}
s^{(1)}
&= \arg \min_{s \in S} \langle \nabla f(x^{(1)}), s \rangle \\
&= \arg \min_{|s| \leq 1} \nabla f(-1)^T s \\
&= \arg \min_{|s| \leq 1} -2s \\
&= 1
\end{aligned}
$$
以及
$$
\gamma_1 = \frac{2}{1+2} = \frac{2}{3}
$$
得到第二次迭代后的结果
$$
x^{(2)} = (1-\gamma_1)x^{(1)} + \gamma_1 s^{(1)} = \frac{1}{3}
$$
之后，不断迭代，会观察到$x^{(k)}$在$\pm \frac{1}{k}$附近震荡，逐渐收敛到0