非线性规划中的Frank-Wolfe条件梯度法进阶题
题目描述
考虑带约束的非线性规划问题：
\[\min_{x \in \mathcal{D}} f(x) \]
其中目标函数 \(f(x)\) 是连续可微的，定义域 \(\mathcal{D} \subset \mathbb{R}^n\) 是一个紧的凸集（例如多面体或球约束）。Frank-Wolfe条件梯度法通过线性化目标函数，在每一步将原问题转化为线性规划子问题，并沿可行方向更新迭代点。本题要求：
- 推导Frank-Wolfe法的核心迭代公式；
- 分析其收敛性及收敛速率；
- 讨论如何结合Nesterov加速技术改进传统Frank-Wolfe法。
解题过程
1. Frank-Wolfe法的核心思想
Frank-Wolfe法适用于约束集为凸且容易投影的情形。其核心思想是：
- 在当前迭代点 \(x_k\)，对目标函数 \(f(x)\) 进行一阶泰勒展开，构造线性近似：
\[ f(x) \approx f(x_k) + \nabla f(x_k)^\top (x - x_k). \]
- 通过求解线性规划子问题，找到使线性近似最小的可行点 \(s_k\)：
\[ s_k = \arg\min_{s \in \mathcal{D}} \nabla f(x_k)^\top s. \]
- 沿方向 \(d_k = s_k - x_k\) 更新迭代点：
\[ x_{k+1} = x_k + \gamma_k (s_k - x_k), \]
其中步长 \(\gamma_k \in [0,1]\) 可通过线搜索或预设规则（如 \(\gamma_k = \frac{2}{k+2}\)）确定。
2. 算法步骤详解
步骤1：初始化
选择初始点 \(x_0 \in \mathcal{D}\)，设定容忍误差 \(\epsilon > 0\)，令 \(k = 0\)。
步骤2：线性规划子问题
计算梯度 \(\nabla f(x_k)\)，求解子问题：
\[s_k = \arg\min_{s \in \mathcal{D}} \nabla f(x_k)^\top s. \]
由于 \(\mathcal{D}\) 是紧凸集，该问题必有解（例如多面体约束下可通过单纯形法求解）。
步骤3：收敛性检验
计算对偶间隙（duality gap）：
\[g_k = \nabla f(x_k)^\top (x_k - s_k). \]
若 \(g_k \leq \epsilon\)，则停止迭代，当前 \(x_k\) 为近似最优解。
步骤4：更新迭代点
选择步长 \(\gamma_k\)：
- 精确线搜索：\(\gamma_k = \arg\min_{\gamma \in [0,1]} f(x_k + \gamma (s_k - x_k))\)；
- 启发式步长：\(\gamma_k = \frac{2}{k+2}\)。
更新：
\[x_{k+1} = x_k + \gamma_k (s_k - x_k). \]
步骤5：迭代循环
令 \(k \leftarrow k+1\)，返回步骤2。
3. 收敛性分析
- 收敛性：若 \(f\) 是凸函数且梯度 \(\nabla f\) 在 \(\mathcal{D}\) 上Lipschitz连续（常数为 \(L\)），则Frank-Wolfe法生成的序列满足：
\[ f(x_k) - f(x^*) \leq \frac{2L \cdot \text{diam}(\mathcal{D})^2}{k+2}, \]
其中 \(\text{diam}(\mathcal{D})\) 是约束集的直径。
- 对偶间隙：\(g_k\) 是收敛性的实用指标，满足 \(g_k \leq O(1/k)\)。
4. Nesterov加速改进
传统Frank-Wolfe法收敛较慢，可通过引入动量项加速：
- 定义辅助序列 \(y_k\)：
\[ y_k = x_k + \frac{k-1}{k+2} (x_k - x_{k-1}). \]
- 在 \(y_k\) 处计算梯度，求解子问题：
\[ s_k = \arg\min_{s \in \mathcal{D}} \nabla f(y_k)^\top s. \]
- 更新迭代点：
\[ x_{k+1} = y_k + \gamma_k (s_k - y_k). \]
此改进可将收敛速率提升至 \(O(1/k^2)\)，但需注意 \(y_k\) 可能不在可行域内，需通过投影或调整保证可行性。
5. 实例演示
考虑问题：
\[\min_{x \in \Delta_n} \frac{1}{2} \|Ax - b\|^2, \]
其中 \(\Delta_n\) 是概率单纯形。
- 子问题：\(s_k = \arg\min_{s \in \Delta_n} (A^\top (A x_k - b))^\top s\) 等价于找到梯度分量最小的顶点（例如单位向量）。
- 更新：\(x_{k+1} = (1-\gamma_k) x_k + \gamma_k s_k\)。
总结
Frank-Wolfe法通过线性化将复杂约束问题转化为简单子问题，适合大规模稀疏优化。结合Nesterov加速可显著提升收敛速度，但需注意可行性的保持。