结构化优化：三种候选，一份可行证书 ​

形式陈述 ​

这个终点要求交出一份可以复算的求解报告：原始数据、损失定标、候选生成过程、实际预算、可行下界、停止结论，以及它没有认证的统计对象。所有任务后都给出答案与关键中间量。

最短核心是近端梯度理路近端梯度法Proximal gradient method对复合目标的光滑项取显式梯度步、对非光滑凸项取隐式近端步的算法。 → Lasso证书理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。 → 坐标法理路Lasso 坐标下降Lasso coordinate descent · Lasso cyclic coordinate minimization用部分残差和列范数逐坐标精确最小化 Lasso，并保持残差缓存与可行对偶证书一致。 → FISTA理路FISTA 复合加速法FISTA · Fast iterative shrinkage-thresholding algorithm以近端主点、外推查询点和递推权重组成复合凸加速，并用势函数而非逐轮下降证明函数值速率。。若会软阈值和对偶可行性，可直接从下面任务一开始。进一步读间隙安全筛除理路Lasso 的间隙安全筛除Gap Safe screening for Lasso · Lasso safe sphere screening把可行原对偶间隙转成最优对偶点的安全球，再以严格列判据证明某坐标在所有 Lasso 最优解中为零。，把同一证书用于减少后续变量。

按需补课：软阈值不熟读近端算子理路近端算子Proximal operator · Proximity operator在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。；零点处求导不清读次微分理路次梯度与次微分Subgradient · Subdifferential以全局仿射下界刻画凸函数在不可微点的支撑斜率集合。；随机历史不清读条件期望理路条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉，再连接测度定义、最小均方预测、塔式性质和可计算反例。。进阶按目标选：约束线性oracle读Frank–Wolfe理路Frank–Wolfe 条件梯度法Frank-Wolfe method · Conditional gradient method以线性最小化代替投影，在紧凸集内做凸组合，并用线性化间隙认证目标误差。，偏导查询读随机坐标理路随机坐标下降与坐标曲率Randomized coordinate descent · Coordinate Lipschitz sampling按坐标曲率抽取一个精确偏导更新，以条件期望核算进展，并分清单坐标、整块与同时更新的步长。，昂贵prox读内层误差预算理路近似近端梯度的误差预算Inexact proximal gradient · Proximal subproblem residual budget用可核验的近端子问题次梯度残差分配内层精度，并把累计误差传到外层平均目标差。，随机样本查询读随机近端理路随机近端梯度Stochastic proximal gradient · Stochastic forward-backward method对光滑项使用历史条件无偏梯度，对结构项精确做prox，以噪声方差和平均输出建立固定预算保证。。它们不是核心路线的额外强制前置。

直觉 ​

求解器负责给出候选，证书负责说明候选有多好。换求解器可以改变速度和轨迹，却不能把原始目标悄悄改成另一个定标，也不能把原始可行下界换成未经检查的表达式。

“出现零坐标”“训练目标下降”“gap达标”“真实支持恢复”是四种承诺。前三者仍需区分各自证据，最后一种还需要数据生成、噪声与设计条件。下面用同一组数据把这些差别变成实际计算。

例子与边界 ​

任务一：先建立统一的原始账本 ​

固定

$$A=\left(\begin{array}{cc}1& 1\\ 1& 0\\ 0& 1\end{array}\right),b=(3/2,3/2,0{)}^T,P(x)=\frac{1}{2}\Vert b-Ax{\Vert }^2+\Vert x{\Vert }_1.$$

从 $x_0=0$开始。求 $Q=A^{T}A$、$c=A^{T}b$、光滑常数和最优解证书。然后对每个候选都使用

$$\begin{array}{}\text{(1)}& r=b-Ax,\rho =max\{1,\Vert A^{T}r{\Vert }_{\mathrm{\infty }}\},\theta =r/\rho ,D=b^T\theta -\Vert \theta {\Vert }^2/2.\end{array}$$

答案：$Q=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$、$c=(3,3/2)$，特征值为1和3，所以 $L=3$。候选 $x^{\ast }=(1,0)$的残差为 $(1/2,1/2,0)$，相关性为 $(1,1/2)$，恰满足正坐标等式和零坐标区间。$P^{\ast }=5/4$，该残差本身对偶可行且 $D=5/4$，因此零gap证明最优。满列秩另保证系数解唯一。

任务二：分别执行坐标法、ISTA和FISTA ​

坐标法每列范数平方为2，更新为 $x_j\leftarrow S_1(A_j^T{r}_{-j})/2$。请比较顺序 $1\to 2$与 $2\to 1$。ISTA使用 $x^{+}=S_{1/3}(x+(c-Qx)/3)$。FISTA使用相同步长，但在外推点查询，并取原算法的 $t$递推。

答案：顺序 $1\to 2$先由相关性3得到 $x_1=1$，再由相关性1/2保持 $x_2=0$，一次扫掠即到解。逆序先得到 $x_2=1/4$，再由相关性11/4得到 $x_1=7/8$；第二轮才到解。ISTA前三点为 $(2/3,1/6)$、$(5/6,0)$、$(17/18,0)$。

FISTA前两点与ISTA相同。令 $\beta =(t_2-1)/t_3\approx 0.281753525$，第三查询为 $(5/6+\beta /6,-\beta /6)$，第三主点为 $(17/18+\beta /9,0)$。请注意第二个查询坐标为负，而主点第二坐标为零。统一证书的结果是：

候选	坐标访问或全梯度次数	$P$	$D$	gap
坐标 $1\to 2$，一轮	2次列访问	$5/4$	$5/4$	0
坐标 $2\to 1$，一轮	2次列访问	$91/64$	$77/64$	$7/32$
坐标 $2\to 1$，两轮	4次列访问	$5/4$	$5/4$	0
ISTA 第1轮	1次全梯度	$17/12$	$67/54$	$19/108$
ISTA 第2轮	2次全梯度	$23/18$	$5/4$	$1/36$
ISTA 第3轮	3次全梯度	$203/162$	$5/4$	$1/324$
FISTA 第3轮	3次全梯度	1.250588044	1.25	0.000588044
FISTA 第4轮	4次全梯度	1.250156796	1.224799545	0.025357251

例如逆序第一轮的残差为 $(3/8,5/8,-1/4)$，相关性 $(1,1/8)$，已可行，无需再缩放。其残差平方和为19/32，故 $P=19/64+9/8=91/64$、$D=3/2-19/64=77/64$。FISTA第4轮主点第一坐标为 $1.012521829$，其过冲使朴素残差构造给出较低的下界；表格没有悄悄改用另一个更好的对偶点。

若容差为 ${10}^{-3}$，两种坐标法最终零gap都达标，ISTA第3轮未达标，FISTA第3轮达标而第4轮未达标。对ISTA，$k\ge 2$时 gap为 $9^{-(k-2)}/36$，所以第4轮gap为 $1/2916<{10}^{-3}$。这只比较本例，不证明某算法普遍更快。

表中“一次列访问”与“一次全梯度”不是同样费用。缓存残差时一轮两列的稠密访问约为 $O(mn)$，一轮梯度也为 $O(mn)$但操作与数据访问不同；每次新候选的完整gap检查还需残差、全列相关性和范数。报告必须另列这些证书成本。

任务三：分别检验非单调与非法证书 ​

FISTA第7、8轮的第一主坐标分别约为 $0.999444749,0.998955502$，目标分别约为 $1.250000308303747,1.250001090976767$。因此第8轮真实目标上升；它与任务二第4轮“目标下降但gap上升”是不同现象。两者都不违反函数值的最坏上界。

再故意用ISTA第一轮的未缩放残差 $r=(2/3,5/6,-1/6)$当作对偶点。其相关性最大值为 $3/2>1$，不满足可行性；表达式 $D(r)=5/3$甚至超过真正最优值 $5/4$，产生 $P-D=-1/4$。答案应指出非法对偶点，而不是把负gap解释为比最优还好。

最后考察小位移：$F(x)=x^2/2,x=1,\alpha ={10}^{-12}$时一步位移仅 ${10}^{-12}$，目标差仍约 $1/2$。缺少残差归一化和误差界的小步长停止规则会误停。

任务四：把gap变成安全筛除，再改变条件 ​

对ISTA第二轮，$G=1/36$、$\theta =(1/2,1/2,0)$。求安全球半径和两列测试值，并解释它与真支持的关系。

答案：半径 $R=\sqrt{2G}=\sqrt{1/18}$；列范数均为 $\sqrt{2}$，故第一列测试值为 $4/3$，第二列为 $5/6<1$。只可安全固定第二列为零。它证明当前Lasso所有优化解的第二坐标为零，没有引入任何随机数据模型，因而没有证明生成参数的真实第二坐标为零。

把设计改成 $A=(11)$、$b=2,\lambda =1$。所有非负且系数和为1的点最优，对偶点为1，两列相关性恰等于阈值。即使gap为零，也不能把严格小于替换为小于等于来删任一列。重复列使系数不唯一，拟合值仍可唯一。

若改变数据或 $\lambda$，必须重证安全名单。即使名单仍针对同一个问题，后续只用剩余列的相关性缩放残差，也不能自动保证原问题全部对偶约束成立；需要全列核验或覆盖被删列的严格界。

任务五：换一组参数，检验方法迁移 ​

保持原来的三行设计和 $b$，把 $\lambda$改为2。请算顺序坐标法的一轮和ISTA的一轮，并按新的可行约束 $\Vert A^T\theta {\Vert }_{\mathrm{\infty }}\le 2$认证。

答案：坐标第一列为 $S_2(3)/2=1/2$，第二列保持零；相关性为 $(2,1)$，所以 $x^{\ast }=(1/2,0)$，$P^{\ast }=2$。ISTA从零一步为 $S_{2/3}((1,1/2))=(1/3,0)$。残差为 $(7/6,7/6,0)$，相关性为 $(7/3,7/6)$，缩放因子 $\rho =7/6$，合法 $\theta =(1,1,0)$。$P=73/36,D=2$，gap为 $1/36$。

若把损失改为原来的三分之一而仍希望同一个最优解，应同时把惩罚参数也除以3；如果只改损失、不改惩罚，目标已经变了。带截距时则必须额外满足 ${\mathbf{1}}^T\theta =0$，不能只复用无截距的缩放公式。

结构迁移：加入不受惩罚的截距 ​

保持原来的 $A,b$，恢复 $\lambda =1$，现在最小化 $\Vert b-c\mathbf{1}-Ax{\Vert }^2/2+\Vert x{\Vert }_1$，截距 $c$不受惩罚。从 $x=0$开始，先更新截距，再检查完整KKT。无截距答案 $(1,0)$还能原样使用吗？

答案：固定零系数时，$c=\mathrm{mean}(b)=1$，残差为 $(1/2,1/2,-1)$。它满足 ${\mathbf{1}}^{T}r=0$，相关性为 $(1,-1/2)$，两坐标都在 $[-1,1]$内，因此 $x^{\ast }=(0,0),c^{\ast }=1$满足系数次梯度和截距驻点条件。原始目标 $P=(1/4+1/4+1)/2=3/4$；取 $\theta =r$，它既满足全列相关性约束，也满足零和约束，$D=b^T\theta -\Vert \theta {\Vert }^2/2=3/2-3/4=3/4$。零gap给完整证明。

也可先把每列和 $b$中心化，求斜率后恢复截距；此时列范数和相关性要使用中心化后的数据重新计算。加入截距改变了可用模型，最优系数的零模式随之改变，这不表示某个优化器“恢复真支持”更好。继续使用无截距的对偶可行条件，会遗漏 ${\mathbf{1}}^T\theta =0$这一条。

推论与应用 ​

任务六：选择正确的结构化工具 ​

1. 约束为概率单纯形，线性最小化只需找一个坐标，问当前误差上界。可选Frank–Wolfe：对 $f=\Vert x{\Vert }^2/2$、$x=(1/2,1/4,1/4)$，gap为 $3/8-1/4=1/8$。投影和镜像方法也可能合适，但它们的子问题与这个线性证书不同。
2. 只想查询一个偏导，目标为 $(x_1^2+9x_2^2)/2$。可按 $(1/10,9/10)$抽坐标，以各自曲率更新。从 $(1,1)$开始一步期望目标为0.9，均匀抽样为2.5。把这称作“抽一条样本”的SGD会混淆接口。
3. 想把三个单坐标安全步并行执行。对 $f=(x_1+x_2+x_3{)}^2/2$，从全1向量同时减去各自偏导3，得到全−2向量，目标由4.5升到18。整个块常数为3，不能使用单坐标常数1。
4. prox内部很贵，能给次梯度残差。若初始距离上界1、$R=2,\alpha =1/2,T=100$，取 ${\delta }_k=1/(4k^2)$，用 $\sum k^{-2}\le 2$得到外层平均目标差至多0.02。固定 $\delta =0.01$则同一账本为0.03。只给prox目标误差不能直接填入这个残差槽位。
5. 梯度来自随机样本，且有统一条件方差1、初始距离上界1、$L=1$。随机近端取 $T=100,\alpha =1/\sqrt{200}$，平均输出的期望目标差上界为 $\sqrt{0.02}$。它不能直接作为某次运行的确定gap；要得到Lasso确定证书，应在返回点完整扫描原数据。

交付检查 ​

合格报告应让另一个人复算更新和证书，而不依赖作者代码：给出数据、列范数、查询点、主点、残差定标、可行性及成本。停止写“gap不超过多少”，而不是只写“已收敛”。预算不足、回溯失败和证书失败应保留为明确状态。

优化gap可进入近似经验风险最小化的误差账本理路近似 ERM 与优化误差approximate ERM · optimization error刻画训练目标未被精确最小化时，经验次优量如何进入总体超额风险。，但泛化和支持恢复仍需要统计条件。这是本单元与学习理论的接口：先把已知的优化误差正确交付，再讨论它如何与抽样、模型和正则化误差组合。

需要把结构单位从单坐标扩成整组变量或矩阵奇异方向时，可继续组与矩阵证书终点：它补齐组收缩、核范数近端、掩码补全与严格唯一性证书，使用独立的数据任务，不改变本页三种标量求解器和安全筛除的原承诺。

随机复合分支可继续到随机几何终点。其中批量加速用完整带噪势函数分别核算 prox 与样本调用，并以8次 prox、242次样本给出0.1期望精度计划；它没有把这个期望结论替换成本页 Lasso 的实际可行对偶 gap。

参考资料 ​

• 各算法的原始来源、完整假设和证明见相应知识页。所有表格固定使用半平方损失；小数保留约9位，精确分数优先。
• Beck–Teboulle 2009的复合势函数与Fercoq–Gramfort–Salmon 2015的安全球分别保证加速率和筛除，两种结论通过同一Lasso数据连接，不能互相替代。