企业官网建设流程全解析

1. 从一道“墙”说起：为什么我们需要Fenchel对偶？

在优化问题的世界里，我们常常会遇到一堵无形的“墙”。比如，你想训练一个机器学习模型，损失函数是凸的，但约束条件（比如模型参数的L1范数不能太大）让问题变得棘手。直接求解原问题，就像试图翻越一堵高墙，计算复杂，步履维艰。这时，Fenchel对偶（Fenchel Duality）就像是在这堵墙上开了一扇门，让我们能从另一个更平坦、更宽敞的路径接近目标。我最初接触这个概念是在处理一个带非光滑正则项的稀疏回归问题时，原问题的目标函数不可微，梯度下降直接失效，而其对偶问题却变得光滑可导，计算瞬间轻松了许多。

简单来说，Fenchel对偶是凸分析中的一个核心工具，它为每一个凸优化问题（原问题）构造了一个与之紧密关联的对偶问题。这两个问题的最优值之间存在着深刻的关系，研究对偶问题往往能为我们理解原问题、设计求解算法提供全新的视角和更强大的工具。尤其在现代机器学习、信号处理、运筹学等领域，面对大规模、高维、带复杂约束或非光滑项的问题时，对偶方法几乎是工程师和研究者工具箱里的标配。

那么，Fenchel对偶具体能为我们做什么？它的核心价值至少体现在三个方面。第一，提供下界与最优性检验。对偶问题的最优值给出了原问题最优值的一个下界（对于最小化问题）。在迭代算法中，我们可以同时计算原问题和对偶问题的目标值，其差值（对偶间隙）是衡量当前解离最优解有多远的一个天然、可靠的指标。当对偶间隙为零时，我们就找到了原问题的最优解。第二，简化问题结构。很多情况下，原问题可能包含难以处理的项（如L1范数、指示函数），但其Fenchel共轭（Fenchel Conjugate）形式却更为友好。通过对偶转化，一个非光滑、带约束的原问题，可能转化为一个光滑、无约束或约束更简单的对偶问题，从而可以使用更高效、更稳定的梯度类算法。第三，启发性算法设计。对偶视角直接催生了一系列强大的算法，如交替方向乘子法（ADMM）、对偶上升法、原始-对偶算法等。这些算法通过巧妙地协调原变量和对偶变量的更新，往往能获得比单纯处理原问题更好的数值表现和收敛性质。

本文的目标，就是带你深入这扇“门”，不仅理解Fenchel对偶这面“镜子”是如何映照原问题的，更要聚焦于一个关键议题：如何利用对偶性来设计和分析“加速”优化算法，并严格理解其收敛速度。我们会从Fenchel对偶的基础讲起，逐步构建起分析加速算法收敛性的理论框架，并结合实例和代码片段（以MATLAB风格示意），让你不仅能看懂理论，更能上手应用。

2. Fenchel对偶：构建原问题的一面“镜子”

要理解加速，必须先夯实对偶的基础。Fenchel对偶的建立，核心依赖于两个概念：凸共轭函数和拉格朗日对偶的推广。

2.1 凸共轭函数：函数的“最大值”变换

给定一个函数f: R^n -> R ∪ {+∞}，它的Fenchel共轭函数f*: R^n -> R ∪ {+∞}定义为：f*(y) = sup_{x in dom f} { y^T x - f(x) }。 这个定义有点抽象，我们可以从几何和经济学角度理解。几何上，对于给定的斜率y，f*(y)是函数f的所有切线（超平面）y^T x - constant中，那个与f图像相切（或支撑）且截距constant最大的那个所对应的-constant。换句话说，它捕捉了用线性函数来从下方逼近f的最佳可能。如果f是凸且下半连续的，那么共轭的共轭等于自身：(f*)* = f。这个对合性质非常强大，意味着原函数和对偶函数包含了相同的信息。

几个关键例子能立刻建立直觉：

• 二次函数：若f(x) = (1/2) x^T Q x，其中Q为正定矩阵，则f*(y) = (1/2) y^T Q^{-1} y。共轭操作相当于求逆。
• 范数：若f(x) = ||x||（任意范数），则其共轭f*(y) = I_{||·||_* ≤ 1}(y)，即示性函数，当对偶范数||y||_* ≤ 1时为0，否则为+∞。这揭示了范数与单位对偶范数球的联系。
• 指数函数：f(x) = exp(x)，其共轭f*(y) = y log y - y（当 y>0），这是信息论中熵函数的形式。
• 示性函数：若f(x) = I_C(x)（当x∈C时为0，否则+∞），则f*(y) = sup_{x∈C} y^T x，即集合C的支撑函数。

计算共轭函数是掌握对偶的第一步。一个实用的技巧是：对于可微的凸函数f，使得y^T x - f(x)取最大值的x满足y = ∇f(x)。因此，可以先解出x关于y的表达式（即梯度映射的逆），再代入定义式求得f*(y)。

2.2 从拉格朗日对偶到Fenchel对偶

标准的拉格朗日对偶处理的是带等式和不等式约束的问题：min f(x) s.t. Ax = b, g(x) ≤ 0。通过引入拉格朗日乘子，构造拉格朗日函数，然后通过对乘子取极大化得到对偶问题。

Fenchel对偶可以看作是其一个更一般、更优雅的表述。考虑如下形式的原问题（P）：min_x f(x) + g(Ax)其中f和g是凸函数，A是线性算子。这个形式涵盖了极其广泛的问题：令g为示性函数，可以表示约束Ax ∈ dom g；令f或g包含正则项。

通过引入辅助变量z = Ax，原问题等价于：min_{x,z} f(x) + g(z) s.t. Ax - z = 0然后构造该约束问题的拉格朗日函数：L(x, z, y) = f(x) + g(z) + y^T (Ax - z)。 对偶函数是对x, z极小化L：q(y) = inf_{x,z} [f(x) + y^T A x] + [g(z) - y^T z]。 仔细观察，这两个中括号分别就是-f*(-A^T y)和-g*(y)的定义（差一个负号）。因此，对偶问题（D）为：max_y - f*(-A^T y) - g*(y)或等价地min_y f*(-A^T y) + g*(y)。

这就是Fenchel对偶的标准形式。强对偶定理（Slater条件等约束品性成立时）告诉我们，原问题最优值p*等于对偶问题最优值d*，并且存在对偶变量y*达到这个最优值。此时，最优解(x*, y*)满足一组称为Fenchel-Young不等式取等的条件：f(x*) + f*(-A^T y*) = <x*, -A^T y*>g(Ax*) + g*(y*) = <Ax*, y*>这组条件等价于原问题和对偶问题的极值条件，也是很多原始-对偶算法设计的出发点。

注意：在实际推导中，符号（-A^T y还是A^T y）可能因原问题定义形式（min f(x)+g(Ax)还是min f(x)+g(b-Ax)）而略有不同。关键是把握核心思想：通过共轭函数，将原问题中的线性复合项“转移”到对偶问题中，并可能改变函数的性质。

2.3 对偶间隙：算法收敛的“标尺”

对于任何一对可行的原变量x和对偶变量y，我们定义对偶间隙（Duality Gap）为：Gap(x, y) = [f(x) + g(Ax)] - [-f*(-A^T y) - g*(y)] = f(x) + g(Ax) + f*(-A^T y) + g*(y)。 由于弱对偶性，对偶间隙始终非负。当且仅当(x, y)是原-对偶最优解时，对偶间隙为零。

这个性质极其有用。在迭代算法中，我们可能无法直接知道当前解x^k离最优解x*有多远（因为f(x*)未知），但我们可以构造一个对应的对偶可行点y^k（通常基于当前迭代的梯度或邻近算子），然后计算对偶间隙Gap(x^k, y^k)。这个值给出了当前目标值f(x^k)+g(Ax^k)超出最优值p*的一个上界。因此，对偶间隙是一个不依赖于未知最优值的、可计算的收敛性度量。在设计算法时，我们常常以驱动对偶间隙下降至零为目标。

3. 加速算法的收敛性分析：穿越理论的迷雾

有了Fenchel对偶作为理论基础，我们就可以深入探讨“加速”算法了。这里的“加速”特指那些能够达到比标准一阶方法（如梯度下降的O(1/k)）更快收敛速率的方法，例如Nesterov的加速梯度法（FGM/AGM）可以达到O(1/k^2)对于光滑凸问题。然而，当问题包含非光滑项（如g(Ax)不可微）时，情况变得复杂。我们关心的是：如何为这类更一般的问题设计加速算法？又如何利用对偶理论来证明其收敛性？

3.1 收敛速率的基本刻画：函数值残差与对偶间隙

分析优化算法的收敛性，我们主要关注两个序列：

1. 函数值残差（Primal Residual）：F(x^k) - F(x*)，其中F(x) = f(x) + g(Ax)。这衡量了当前解的目标值与最优值的差距。
2. 对偶间隙（Duality Gap）：如上文定义的Gap(x^k, y^k)。这是一个更稳健的度量，因为它同时保证了原问题和对偶问题的可行性。

对于凸问题，我们通常期望算法产生一个序列{x^k}，使得函数值残差或对偶间隙以某种速率衰减到零。常见的速率有：

• O(1/k)：次线性收敛，标准梯度下降对于光滑凸函数的速率。
• O(1/k^2)：加速速率，Nesterov加速梯度法对于光滑凸函数的速率。
• O(ρ^k)（0<ρ<1）：线性（几何）收敛，通常在目标函数强凸时获得。

分析加速算法，尤其是针对复合问题min f(x)+g(Ax)的加速算法，一个强大的理论框架是估计序列（Estimate Sequence）和Lyapunov函数（或能量函数）法。

3.2 Lyapunov函数法：构建收敛的“能量”证明

这是分析加速原始-对偶算法最流行和直观的方法。其核心思想是：为算法迭代过程中产生的序列(x^k, y^k, ...)构造一个函数V^k（Lyapunov函数），这个函数满足两个性质：

1. 非负性：V^k ≥ 0。
2. 递减性：V^{k+1} ≤ V^k - c * (某种进步量)，其中c > 0。

如果我们能证明V^k的衰减速率（例如V^k ≤ C / (k+1)^2），并且V^k能控制我们所关心的收敛度量（如函数值残差或对偶间隙），那么我们就证明了算法的收敛速率。

对于加速算法，一个典型的Lyapunov函数可能形如：V^k = a_k (F(x^k) - F(x*)) + b_k ||u^k - x*||^2 + c_k (某种对偶项)其中{a_k}, {b_k}, {c_k}是精心设计、递增的序列，u^k是一个辅助变量序列。算法的迭代规则（更新x^k, y^k, u^k）和参数a_k, b_k的选择，需要协同设计，以确保V^k - V^{k+1} ≥ (某个正项)。通过 telescoping sum（叠缩求和），就能得到V^k的上界。

为什么对偶理论在这里至关重要？在构造V^k和证明其递减性时，我们经常需要将原问题目标F(x^k) - F(x*)与对偶变量、最优性条件联系起来。Fenchel-Young不等式和对偶间隙的定义提供了关键的桥梁。例如，我们常常利用不等式：F(x^k) - F(x*) ≤ Gap(x^k, y^*) = f(x^k)+g(Ax^k) + f*(-A^T y*)+g*(y*)或者，对于某个由算法产生的对偶点y^k，有：F(x^k) - F(x*) ≤ Gap(x^k, y^k)然后，算法的迭代步骤会被设计成能够显式地减少这个对偶间隙的上界，或者减少一个包含对偶间隙项的Lyapunov函数。

3.3 一个经典案例：加速邻近梯度法（FISTA）的对偶视角

考虑问题min_x f(x) + g(x)，其中f是光滑凸函数（梯度Lipschitz连续），g是凸函数（可能非光滑，但邻近算子易算）。这就是著名的复合优化问题。FISTA算法步骤如下：

1. 初始化x^0 = y^0,t_0 = 1。
2. 对于k = 0, 1, 2, ...： a. 更新y^{k+1} = prox_{η g} (x^k - η ∇f(x^k))（标准梯度步+邻近算子） b. 更新t_{k+1} = (1 + sqrt(1+4t_k^2)) / 2c. 更新x^{k+1} = y^{k+1} + ((t_k -1)/t_{k+1}) (y^{k+1} - y^k)

从原问题角度看，这是一个巧妙的动量外推。但从对偶角度看，可以将其解释为一个在原始空间执行的、但等价于在对偶空间进行某种加速的过程。具体地，g的邻近算子步骤prox_{η g}(v)等价于求解min_z g(z) + (1/(2η))||z - v||^2，这个子问题的对偶与g的共轭g*的梯度步有关（根据Moreau分解：prox_{η g}(v) = v - η prox_{g*/η}(v/η)）。

虽然FISTA通常用估计序列来证明其O(1/k^2)的收敛速率，但通过引入对偶变量，我们可以构造一个包含f(x^k)+g(x^k) + (1/(2η))||...||^2和对偶项g*(...)的Lyapunov函数，从而给出一个基于原始-对偶最优性条件的统一证明。这种证明更清晰地揭示了动量项((t_k -1)/t_{k+1})是如何通过协调原始和对偶变量的更新路径来抵消振荡、实现加速的。

实操心得：在实现FISTA时，参数t_k的更新公式必须精确。一个常见的错误是使用近似公式或错误的初始化。此外，对于强凸的f，可以调整t_k的更新规则以获得线性收敛速率。记住，加速不是免费的午餐，它通常要求目标函数的光滑部分 (f) 梯度 Lipschitz 常数已知或可估计，否则需要结合线搜，但线搜可能会轻微破坏优美的收敛率证明。

4. 超越FISTA：广义的加速原始-对偶混合梯度法

当问题形式变为min_x f(x) + g(Ax)，且f和g都可能非光滑（但邻近算子易算）时，FISTA不能直接应用。这时，我们需要更一般的加速原始-对偶混合梯度法（Accelerated Primal-Dual Hybrid Gradient, A-PDHG），也称为 Chambolle-Pock 算法的加速变种。

考虑原问题 (P)min_x f(x) + g(Ax)和对偶问题 (D)min_y f*(-A^T y) + g*(y)。标准的PDHG（未加速）迭代为：

y^{k+1} = prox_{σ g*} (y^k + σ A x̅^k) x^{k+1} = prox_{τ f} (x^k - τ A^T y^{k+1}) x̅^{k+1} = x^{k+1} + θ (x^{k+1} - x^k)

其中σ, τ > 0是步长，需满足σ τ ||A||^2 < 1以保证收敛，θ=1是常用选择，收敛速度为O(1/k)。

为了获得加速，我们需要引入外推参数θ_k，并让其随着迭代增长。一个经典的加速方案（由Chambolle和Pock提出）如下：

1. 初始化x^0, y^0, x̅^0 = x^0，设τ_0, σ_0 > 0使得τ_0 σ_0 ||A||^2 ≤ 1，设θ_0 = 1，η ∈ (0, 1]。
2. 对于k = 0, 1, 2, ...： a. 更新对偶变量：y^{k+1} = prox_{σ_k g*} (y^k + σ_k A x̅^k)b. 更新原始变量：x^{k+1} = prox_{τ_k f} (x^k - τ_k A^T y^{k+1})c. 更新外推参数和步长：θ_{k+1} = 1 / sqrt(1 + η θ_k)τ_{k+1} = τ_k / θ_{k+1}σ_{k+1} = σ_k / θ_{k+1}d. 更新外推点：x̅^{k+1} = x^{k+1} + θ_{k+1} (x^{k+1} - x^k)

这个算法中，θ_k从1开始递减（注意，这与FISTA中t_k递增不同）。可以证明，在一定的条件下（例如f或g*是强凸的），该算法能达到O(1/k^2)的收敛速率（对偶间隙）。如果没有强凸性，则可能退回到O(1/k)。

收敛性分析的关键：同样依赖于构造一个精心设计的Lyapunov函数。例如，考虑函数：L_k = (1/τ_k) ||x^k - x*||^2 + (1/σ_k) ||y^k - y*||^2 + 2θ_k (Gap(x̅^k, y*) - <A(x̅^k - x*), y^k - y*>)通过复杂的代数运算，利用算子的单调性、Fenchel-Young不等式以及步长参数τ_k, σ_k, θ_k的更新规则，可以证明L_{k+1} ≤ L_k。然后，通过对L_k的 bound 和θ_k的衰减性质，推导出对偶间隙Gap(x̅^k, y^k)的O(1/k^2)上界。

注意事项：A-PDHG的参数选择比非加速版本更敏感。η是一个阻尼参数，通常取1，但在实际数值实验中，略小于1的值（如0.95）有时能带来更好的稳定性。此外，算子范数||A||的估计至关重要。高估会导致步长过小，收敛慢；低估会破坏收敛保证。可以采用幂迭代法（Power Iteration）来估计||A||，或者在算法中结合自适应步长调整策略。

5. 实验验证：在MATLAB中观察收敛轨迹

理论是灰色的，而实践之树常青。我们用一个简单的例子来验证加速算法的效果。考虑一个全变分（TV）去噪问题，它是min f(x)+g(Ax)的典型例子：min_x (1/2)||x - b||^2 + λ * TV(x)其中f(x) = (1/2)||x - b||^2是光滑的保真项，g(z) = λ||z||_{1,2}是非光滑的全变分正则项（各向同性TV），A是离散梯度算子。这里g(Ax)不可微。

我们将对比三种算法：1) 次梯度法（慢，作为基线），2) 未加速的PDHG（Chambolle-Pock），3) 加速的PDHG（A-PDHG）。我们关心对偶间隙随迭代次数的下降情况。

% 假设已定义：离散梯度算子 D (返回两个方向的梯度)，其伴随算子 Dadj，噪声图像 b，正则化参数 lambda % 定义函数句柄 f_prox = @(x, tau) (x + tau*b) / (1+tau); % f(x)=0.5||x-b||^2 的邻近算子 g_prox = @(z, sigma) prox_l12(z, sigma*lambda); % g(z)=lambda*||z||_{1,2} 的邻近算子，需自行实现 % 算法参数 max_iter = 1000; tol = 1e-6; % 1. 未加速PDHG (θ=1) tau = 0.99 / normD; % normD是梯度算子D的谱范数估计 sigma = 0.99 / normD; theta = 1; x = zeros(size(b)); x_bar = x; y = zeros([size(b), 2]); % 对应对偶变量（两个梯度方向） gap_history_pdhg = zeros(max_iter,1); for k = 1:max_iter % 对偶更新 z = y + sigma * D(x_bar); % D是梯度算子 y_new = g_prox(z, sigma); % 对g*的邻近算子，等价于对g的邻近算子的Moreau分解 % 原始更新 x_new = f_prox(x - tau * Dadj(y_new), tau); % 外推 x_bar_new = x_new + theta * (x_new - x); % 计算对偶间隙 (简化计算，此处需要计算f(x), g(Dx), f*(-Dadj y), g*(y)) % ... 计算 gap gap_history_pdhg(k) = gap; % 更新变量 x = x_new; y = y_new; x_bar = x_bar_new; if gap < tol, break; end end % 2. 加速PDHG (A-PDHG) tau0 = 0.99 / normD; sigma0 = 0.99 / normD; theta0 = 1; eta = 0.95; % 阻尼系数 x = zeros(size(b)); x_bar = x; y = zeros([size(b), 2]); tau = tau0; sigma = sigma0; theta = theta0; gap_history_apdhg = zeros(max_iter,1); for k = 1:max_iter % 对偶更新 z = y + sigma * D(x_bar); y_new = g_prox(z, sigma); % 原始更新 x_new = f_prox(x - tau * Dadj(y_new), tau); % 更新参数 theta_new = 1 / sqrt(1 + eta*theta); tau = tau / theta_new; sigma = sigma / theta_new; % 外推 x_bar_new = x_new + theta_new * (x_new - x); % 计算对偶间隙 % ... 计算 gap gap_history_apdhg(k) = gap; % 更新变量 x = x_new; y = y_new; x_bar = x_bar_new; theta = theta_new; if gap < tol, break; end end % 绘制收敛曲线 semilogy(1:k, gap_history_pdhg(1:k), 'b-', 'LineWidth', 1.5); hold on; semilogy(1:k, gap_history_apdhg(1:k), 'r--', 'LineWidth', 2); xlabel('迭代次数 k'); ylabel('对偶间隙 (log scale)'); legend('PDHG (O(1/k))', 'A-PDHG (O(1/k^2))', 'Location', 'best'); grid on; title('全变分去噪：PDHG与加速PDHG收敛性对比');

在典型的实验结果中，我们会看到红色的A-PDHG曲线下降速度明显快于蓝色的PDHG曲线，尤其是在迭代初期。在双对数坐标下，A-PDHG的曲线斜率可能更陡，直观反映了O(1/k^2)相对于O(1/k)的速度优势。然而，这种优势并非绝对。如果问题条件数很差，或者线性算子A的范数估计不准，加速版本的振荡可能会更明显，需要仔细调参。

一个关键的实现细节：计算对偶间隙Gap(x, y) = f(x)+g(Dx) + f*(-Dadj y)+g*(y)。这里f*(-Dadj y)的计算利用了二次函数的共轭公式。对于f(x)=0.5||x-b||^2，有f*(v) = 0.5||v||^2 + v^T b。因此f*(-Dadj y) = 0.5||Dadj y||^2 - (Dadj y)^T b。g*(y)是L1,2范数共轭，是单位L2范数球的示性函数，其计算涉及对y各点处的向量进行投影归一化。在实际代码中，计算精确的对偶间隙可能开销较大，有时会用其他更易计算的残差（如原始残差、对偶残差）来代替监控。

6. 理论边界与实践中的调参陷阱

尽管加速算法在理论上有更快的收敛速率，但在实际应用中，将其理论潜力完全发挥出来并非易事。这一节我们深入探讨理论假设与工程现实之间的鸿沟。

6.1 理论速率的假设与局限

所有的O(1/k^2)加速理论都建立在一些理想化假设之上：

1. 精确的 Lipschitz 常数或算子范数：步长参数τ, σ依赖于函数梯度 Lipschitz 常数L或线性算子范数||A||。高估会导致步长过小，收敛缓慢；低估则可能导致算法发散。在复杂问题中，精确获取这些常数非常困难。
2. 强凸性假设：要获得线性收敛O(ρ^k)，通常需要目标函数的某一部分（f或g*）是强凸的。然而，许多重要的正则项（如L1范数、核范数）并非强凸。此时，加速算法可能退回到次线性收敛，其实际表现可能并不比非加速版本稳定。
3. 凸性假设：整个理论框架建立在函数是凸的基础上。对于非凸问题，加速算法缺乏一般的收敛保证，甚至可能发散。
4. 无穷精度计算：理论分析假设所有邻近算子、梯度计算都是精确的。现实中，这些计算可能存在数值误差，尤其是当邻近算子没有闭式解而需要迭代求解时（内循环），误差会累积并影响外层算法的收敛性。

6.2 步长与参数的实战调优指南

在实践中，我遵循以下步骤来调参：

1. 初始化估计：

   • 梯度 Lipschitz常数 L：对于f(x)，可以用幂迭代法估计其Hessian的最大特征值，或者采用回溯线搜索（backtracking line search）自适应确定。对于A-PDHG中的||A||，同样用幂迭代法估计A^T A的最大特征值。
   • 步长 τ, σ：保守起见，从τ = σ = 0.99 / ||A||或τ = σ = 0.99 / sqrt(L)开始。安全因子0.99是为了满足收敛条件τ σ ||A||^2 < 1或τ L < 2。

2. 自适应策略：

   • 基于对偶间隙的自适应：监控对偶间隙或原始/对偶残差。如果迭代过程中振荡剧烈（残差上下波动），可能是步长太大，可以尝试按比例（如0.8倍）减小τ和σ，并重置外推参数θ。
   • 平衡原则：在原始-对偶算法中，原始步长τ和对偶步长σ应保持平衡。一个经验法则是观察原始变量和对偶变量的更新幅度，如果一方变化远大于另一方，可以调整步长比例。

3. 加速参数 θ 的选择：

   • 在A-PDHG中，θ_k的更新公式θ_{k+1} = 1 / sqrt(1 + η θ_k)是理论推导的结果。η通常取1，但有时设置为略小于1（如0.9到0.99）可以起到阻尼作用，减少振荡，提高稳定性，尤其在线性算子A条件数较大时。
   • 对于FISTA类型的算法，如果问题具有强凸性，可以使用更激进的参数更新，例如t_{k+1} = (1 + sqrt(1+4t_k^2 + 4μ t_k^2)) / 2，其中μ是强凸系数，这可以恢复线性收敛。

4. 重启（Restarting）技术： 这是应对加速算法振荡、提升实际性能的利器。当检测到算法进展缓慢或出现“螺旋”振荡时（例如，函数值或梯度范数在一段时间内不降反升），将动量参数t_k或θ_k重置为1，并从当前点重新开始加速过程。重启策略有几种：

   • 固定周期重启：每迭代N步重启一次（例如N=50或100）。简单粗暴，但有效。
   • 函数值监控重启：当F(x^k) > F(x^{k-1})时重启。这能有效抑制振荡。
   • 梯度映射重启：基于梯度映射的范数变化来判断。 重启破坏了理论上的O(1/k^2)证明（在最坏情况下可能退化），但在绝大多数实际问题上，它能显著加快收敛，使算法表现更接近线性收敛。

6.3 何时选择加速算法？——决策流程图

面对一个新问题，是否应该使用加速算法？可以参考以下决策思路：

问题形式是否为 min f(x) + g(Ax) 或 min f(x) + g(x)？ --> 否 --> 考虑其他算法（如ADMM、坐标下降等） | 是 | f 是否光滑且梯度 Lipschitz常数已知/可估？ --> 否 --> 优先使用非加速版本（如PGD, PDHG），或结合线搜的加速版本（复杂度增加） | 是 | g (或 g*) 的邻近算子是否容易计算？ --> 否 --> 考虑使用线性化或近似求解内循环，需谨慎评估误差影响 | 是 | 问题规模是否非常大，且对收敛速度要求高？ --> 否 --> 标准算法可能已足够，加速带来的收益可能不抵调参成本 | 是 | 尝试 A-PDHG 或 FISTA。 1. 用幂迭代法估计 ||A|| 或 L。 2. 设置保守步长 (0.95/估计值)。 3. 实现并监控对偶间隙或目标函数值。 4. 若振荡剧烈：a) 减小步长；b) 引入阻尼 (η<1)；c) 启用重启策略（如每100步或函数值上升时重启）。 5. 若进展缓慢：a) 检查步长是否过于保守；b) 检查强凸性，若存在可调整参数更新公式。

最终，没有放之四海而皆准的最优算法。对于超大规模、但结构特殊（如可分）的问题，分布式非加速算法可能因为通信开销更低而更有效。加速算法的优势在于其理论上的快速收敛率，这在求解高精度解时尤为关键。我的经验是，对于中等规模、条件数适中、需要高精度解的问题，经过良好调参的加速算法通常是首选。