Frank–Wolfe 条件梯度法

投影梯度理路投影梯度法Projected gradient method · Gradient projection method在每次梯度步后投影回闭凸可行集以保持可行性的约束一阶算法。寻找接近梯度候选的可行点，通常要解一个二次距离问题。Frank–Wolfe只问“在当前线性价格下，哪个可行点最便宜”，再向它移动一部分。镜像下降理路镜像下降法Mirror descent method · Bregman gradient method用强凸镜像映射生成的 Bregman 几何执行线性化损失更新的约束一阶算法。则还要支付Bregman距离。三种子问题的成本不同，应该按约束结构选方法。

在概率单纯形 ${\mathrm{\Delta }}_n$ 上，线性oracle只需找最小梯度坐标，返回相应顶点 $e_j$。在半径 $\tau$ 的 ${\ell }_1$ 球上，它返回 $-\tau \mathrm{sign}(g_j)e_j$，其中 $|g_j|=\Vert g{\Vert }_{\mathrm{\infty }}$。若从一个可行原子开始，每次至多加入一个新的oracle原子，$k$ 次更新后可表示为至多 $k+1$ 个已访问原子的凸组合；在多面体上若oracle总返回顶点，这些原子就是顶点。这个“稀疏”指原子表示；一般原子本身可以是稠密向量。

间隙来自一条可计算支撑平面。对任意 $z\in C$，凸性给 $f(z)\ge f(x)+⟨\mathrm{\nabla }f(x),z-x⟩$。在线性oracle处取最小值，得到 $f^{\ast }\ge f(x)-G(x)$，从而

这个下界与产生 $x$ 的算法无关，任意可行候选都能检查；它也不需要知道 $L$ 或最优值。

三个坐标的线搜索 ​

取 $C={\mathrm{\Delta }}_3$、$f(x)=\Vert x{\Vert }^2/2$，从 $x_0=(1,0,0)$ 开始。$\mathrm{\nabla }f=x$，选择并列最小坐标时取编号较小者，所以 $s_0=e_2$。第一段目标是 $[(1-\gamma {)}^2+{\gamma }^2]/2$，导数 $-1+2\gamma$ 为零给 $\gamma =1/2$，得到 $x_1=(1/2,1/2,0)$。

此时 $s_1=e_3$。第二段目标为 $(1-\gamma {)}^2/4+{\gamma }^2/2$，导数 $-1/2+3\gamma /2$ 为零给 $\gamma =1/3$，得到 $x_2=(1/3,1/3,1/3)$。三个点的目标分别是 $1/2,1/4,1/6$；用 $G(x)=\Vert x{\Vert }^2-\underset{i}{min}{x}_i$，间隙分别为 $1,1/2,0$。最后的零证书证明最优，无需凭图猜测均匀点。

若使用预设步长，首步 ${\gamma }_0=1$ 会从 $e_1$ 到 $e_2$，目标不变。这不违反函数值上界；预设步长与精确线搜索不能混成同一条数值轨道。

近似oracle的误差必须加入证书 ​

假设返回 $\tilde{s}\in C$，并有可信的加性误差 $\delta \ge 0$，满足

那么可报告的上界是 $\tilde{G}+\delta$，其中 $\tilde{G}=⟨\mathrm{\nabla }f(x),x-\tilde{s}⟩$，因为 $G\le \tilde{G}+\delta$。如果不附误差保证，oracle在上例 $e_1$ 返回 $\tilde{s}=e_1$ 就会报 $\tilde{G}=0$，实际目标还比最优值高 $1/3$。一个方便的方向不一定是合格的证书。

紧性也有工作：若 $C=\mathbb{R}$、$f(x)=x^2/2$，在 $x=1$ 的线性子问题是最小化 $s$，没有有限解，虽然原目标有唯一最小点。若去掉凸性，$f(x)=-x^2$、$C=[-1,1]$ 在 $x=0$ 有 $G=0$，目标却高于全局最优值 $1$；式(2)的支撑平面步骤已经失败。

函数值的完整递推 ​

记 ${\mathrm{\Delta }}_k=f(x_k)-f^{\ast }$、$B=L{R}^2$。由下降引理理路下降引理Descent lemma · Quadratic upper-bound lemma以 Lipschitz 梯度常数给出函数相对一阶模型的全局二次上界。和式(2)，对任意 $0\le \gamma \le 1$，

首步 ${\gamma }_0=1$ 给 ${\mathrm{\Delta }}_1\le B/2\le 2B/3$。若 ${\mathrm{\Delta }}_k\le 2B/(k+2)$，取 ${\gamma }_k=2/(k+2)$ 得

最后一步因 $(k+1)(k+3)\le (k+2{)}^2$。归纳得到 ${\mathrm{\Delta }}_k\le 2L{R}^2/(k+2)$，$k\ge 1$。精确线搜索的值不大于这条试探步，因此沿用递推。

这个证明控制函数值，不等于已经证明每个末点的gap也是同一个 $O(1/k)$ 上界。实际停止仍直接算式(1)。例如上述递推只使用 $G_k\ge {\mathrm{\Delta }}_k$，这是把gap向下替换成目标差，不能反过来从小目标差推出小gap。

预算与问题选择 ​

每轮费用是梯度、线性oracle、$O(n)$凸组合及可选线搜索。在单纯形上选坐标为 $O(n)$；若梯度已稠密，维护稀疏原子表示并不会让全部费用自动变成常数。复杂约束上的线性oracle本身也可能昂贵。

惩罚型 Lasso 与约束 $\Vert x{\Vert }_1\le \tau$ 的平方损失可在合适参数下关联，但一般并非每个 $\lambda$ 与每个 $\tau$ 一一对应。对前者应使用Lasso 可行对偶间隙理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。；对后者可用这里的线性oracle证书。比较两个数值gap前先核对它们认证的是同一个目标和可行域。

两道短自测 ​

1. 对 ${\mathrm{\Delta }}_3$上的 $f=\Vert x{\Vert }^2/2$，候选 $(1/2,1/4,1/4)$的gap是多少？答案：$\Vert x{\Vert }^2=3/8$，最小梯度为1/4，故gap为1/8；实际目标差为 $3/16-1/6=1/48$，证书可以保守。
2. 近似线性oracle给 $\tilde{G}=0.01$、经证明的误差 $\delta =0.03$，能否认证误差不超过0.02？答案：只能认证0.04，不能达标；要么改善oracle，要么保留预算不足状态。