Frank-Wolfe算法 Frank-Wolfe算法（也称条件梯度法）是求解凸优化问题的一阶迭代算法，特别适用于可行域为有界凸集且线性优化容易求解的问题。下面逐步展开讲解： 1. 问题背景与形式 考虑凸优化问题： \[ \min_ {x \in \mathcal{D}} f(x) \] 其中： \( f \) 是可微凸函数； 可行域 \(\mathcal{D} \subset \mathbb{R}^n\) 为紧凸集（有界闭集）； 关键假设：对任意向量 \(c\)，线性子问题 \(\min_ {s \in \mathcal{D}} c^T s\) 易求解（如通过单纯形法或闭式解）。 2. 算法核心思想 Frank-Wolfe算法通过迭代执行以下步骤： 线性近似 ：在当前迭代点 \(x_ k\)，用一阶泰勒展开近似 \(f\)： \[ f(x) \approx f(x_ k) + \nabla f(x_ k)^T (x - x_ k) \] 最小化该线性函数 over \(\mathcal{D}\)，得到方向点： \[ s_ k = \arg\min_ {s \in \mathcal{D}} \nabla f(x_ k)^T s \] 确定步长 ：沿方向 \(d_ k = s_ k - x_ k\) 移动，通过线确定步长 \(\gamma_ k \in [ 0,1 ]\)（常用精确搜索或设定递减步长）； 更新迭代点 ： \[ x_ {k+1} = x_ k + \gamma_ k (s_ k - x_ k) \] 由于 \(\mathcal{D}\) 是凸集，\(x_ {k+1}\) 仍在可行域内。 3. 算法步骤与细节 输入 ：初始点 \(x_ 0 \in \mathcal{D}\)，迭代次数 \(T\) 或容差 \(\epsilon\)。 循环 （对于 \(k=0,1,\dots,T-1\)）： 计算梯度 \(g_ k = \nabla f(x_ k)\)； 求解线性子问题：\(s_ k = \arg\min_ {s \in \mathcal{D}} g_ k^T s\)； 计算对偶间隙 \(\delta_ k = g_ k^T (x_ k - s_ k)\)（若 \(\delta_ k \le \epsilon\)，则退出循环）； 选择步长 \(\gamma_ k\)（如 \(\gamma_ k = \frac{2}{k+2}\) 或精确搜索 \(\arg\min_ {\gamma \in [ 0,1]} f(x_ k + \gamma(s_ k - x_ k))\)）； 更新 \(x_ {k+1} = x_ k + \gamma_ k (s_ k - x_ k)\)。 4. 关键特性与收敛性 保持可行性 ：由于 \(x_ {k+1}\) 是 \(x_ k\) 和 \(s_ k\) 的凸组合，算法始终在可行域内； 收敛速度 ： 若 \(f\) 为凸且 Lipschitz 光滑，采用递减步长时收敛速度为 \(O(1/k)\)； 若 \(f\) 强凸且可行域有界，可达到 \(O(1/k^2)\) 的收敛速度（采用自适应步长时）； 对偶间隙 ：\(\delta_ k = g_ k^T (x_ k - s_ k)\) 既是停止准则，也衡量当前解与最优性的距离。 5. 优势与适用场景 稀疏性 ：尤其适用于希望解具有稀疏结构的问题（如 \(s_ k\) 是极点，迭代解为极点的凸组合）； 避免投影 ：相比投影梯度法，Frank-Wolfe 只需求解线性优化问题，避免高成本投影； 典型应用：矩阵补全、稀疏信号处理、交通均衡问题等。 6. 示例说明 考虑 \(\min \frac{1}{2} \|Ax - b\|^2\)，约束为 \(\|x\|_ 1 \leq t\)（L1-球）。 线性子问题：\(\arg\min_ {\|s\|_ 1 \leq t} g_ k^T s\) 的解是 \(s_ k = -t \cdot \mathrm{sign}(g_ k) \cdot e_ i\)，其中 \(i\) 对应 \(|g_ k|\) 最大分量的索引； 每次迭代仅更新一个分量，促进稀疏性。 7. 扩展与变体 ** Away-step Frank-Wolfe** ：通过移除非活跃方向加速收敛； ** Bloc