非线性规划中的Frank-Wolfe算法 Frank-Wolfe算法是求解约束非线性规划问题的一类经典方法，特别适用于可行域为有界凸集且目标函数可微的情形。下面我将逐步介绍其核心思想、算法步骤、理论基础及特点。 问题形式与核心思想 考虑问题：min f(x)，满足 x ∈ D，其中 D 是紧凸集，f 连续可微。 核心思想：在每次迭代中，将目标函数 f 在当前迭代点 x_ k 处线性化，求解该线性函数在 D 上的最小值，得到方向 d_ k = s_ k - x_ k（s_ k 为线性化子问题的最优解），再沿该方向进行一维搜索确定步长。 算法步骤 步骤1：初始化。选取初始点 x_ 0 ∈ D，设定容许误差 ε > 0，令 k = 0。 步骤2：求解线性子问题。计算 s_ k ∈ argmin{ ∇f(x_ k)^T s | s ∈ D }。 步骤3：终止检验。若 ∇f(x_ k)^T (s_ k - x_ k) ≥ -ε，则停止（x_ k 近似满足一阶最优性条件）；否则继续。 步骤4：确定步长。可采用精确搜索 λ_ k ∈ argmin{ f(x_ k + λ(s_ k - x_ k)) | λ ∈ [ 0,1 ] }，或设定衰减步长（如 2/(k+2)）。 步骤5：更新迭代点。令 x_ {k+1} = x_ k + λ_ k (s_ k - x_ k)，k = k+1，返回步骤2。 收敛性理论基础 若 f 为凸函数，算法产生的迭代点列任何聚点均为全局最优解。 收敛速率：对于凸函数，采用衰减步长时，目标函数值的误差以 O(1/k) 速率下降；若 f 强凸且梯度 Lipschitz 连续，可能获得线性收敛。 算法特点与适用场景 优点：每次迭代只需求解线性规划，计算成本低；迭代点始终可行；产生的解具有稀疏性或多面体结构的组合。 缺点：收敛速度较慢（尤其接近最优解时）；方向选择可能仅沿可行域边界。 典型应用：交通分配、矩阵补全、稀疏优化等涉及单纯形或谱范数球约束的问题。 扩展与变体 条件梯度滑动法：结合Nesterov加速技巧，改善收敛速率。 随机Frank-Wolfe：适用于目标函数为期望形式或大规模数据问题。 块坐标Frank-Wolfe：处理高维或可分结构的优化。