好的，我已经记住了你已学过的所有题目。这次，我将为你讲解一个之前未出现过的、在非线性规划领域中常用于求解大规模、带简单边界约束问题的经典算法。
非线性规划中的坐标下降法（Coordinate Descent Method）进阶题：处理高维、非光滑、可分离目标函数的优化问题
1. 题目描述
考虑如下形式的非线性规划问题：
最小化 \(f(\mathbf{x})\)
约束条件 \(\mathbf{x} \in \mathcal{X} = \mathcal{X}_1 \times \mathcal{X}_2 \times \dots \times \mathcal{X}_n \subseteq \mathbb{R}^n\)
其中：
- \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) 是目标函数。
- \(\mathcal{X}_i\) 是第 \(i\) 个变量 \(x_i\) 的可行域，通常是一个闭区间（如 \(x_i \ge 0\) 或 \(l_i \le x_i \le u_i\)），即问题主要是边界约束。
- 目标函数 \(f(\mathbf{x})\) 通常是高维（n 很大）且具有某种程度的可分离性（Separability）。一个常见的形式是 \(f(\mathbf{x}) = g(\mathbf{x}) + \sum_{i=1}^{n} h_i(x_i)\)，其中 \(g(\mathbf{x})\) 可能光滑，而 \(h_i(x_i)\) 可能是非光滑的正则项（如 L1 范数 \(|x_i|\)）。
问题特点：
- 高维性：传统基于梯度的二阶方法（如牛顿法）计算海森矩阵（Hessian）的代价巨大。
- 约束简单：只有边界约束，投影操作极其简单。
- 可分离性：当固定其他变量时，优化单个变量的问题可以高效求解，甚至可能得到解析解。
经典应用场景：Lasso回归（\(f(\mathbf{x}) = \frac{1}{2} \|A\mathbf{x} - \mathbf{b}\|^2 + \lambda \|\mathbf{x}\|_1\)）、逻辑回归、支持向量机的对偶问题求解等。
现在，请你使用坐标下降法来解决一个具体实例：
最小化 \(f(x_1, x_2) = (x_1 - 1)^2 + 100(x_1^2 - x_2)^2 + 10|x_2|\)
约束条件 \(x_1 \ge 0, x_2 \ge 0\)。
2. 解题过程详解
坐标下降法的核心思想是：每次迭代只优化一个坐标（变量）方向，而固定其他所有坐标。通过循环遍历所有坐标，逐渐逼近最优解。
步骤一：算法框架理解
给定初始点 \(\mathbf{x}^0 = (x_1^0, x_2^0, \dots, x_n^0)\)。对于第 \(k\) 轮迭代（\(k = 0, 1, 2, \dots\)）：
- 选择一个坐标索引 \(i\)（例如，按顺序循环 \(i = 1, 2, \dots, n, 1, 2, \dots\)）。
- 子问题求解：求解如下一维优化问题：
\[ \min_{z \in \mathcal{X}_i} \ f(x_1^{k+1}, \dots, x_{i-1}^{k+1}, z, x_{i+1}^k, \dots, x_n^k) \]
即将 \(f\) 视为仅关于变量 \(z\)（即 \(x_i\)）的一元函数，其他变量固定为当前最新值。
3. 更新坐标：令 \(x_i^{k+1}\) 等于上面子问题的最优解 \(z^*\)。其他坐标保持不变：\(x_j^{k+1} = x_j^k\)（对于 \(j \ne i\)）。
4. 检查收敛条件（如函数值下降量或坐标变化量小于阈值），若不满足，则选择下一个坐标继续。
为什么有效？ 对于高维、可分离或近似可分离的问题，单变量子问题通常计算简单、求解快速，且内存消耗极低。
步骤二：应用于我们的具体问题
我们的问题是：\(\min_{x_1 \ge 0, x_2 \ge 0} f(x_1, x_2) = (x_1 - 1)^2 + 100(x_1^2 - x_2)^2 + 10|x_2|\)。
- 初始化：我们随机选择一个可行初始点，例如 \(\mathbf{x}^0 = (0.5, 0.5)\)。
- 收敛准则：我们设定当两次迭代间函数值变化 \(|f^{k+1} - f^k| < 10^{-6}\) 时停止。
- 坐标更新顺序：我们采用经典的循环坐标下降，即顺序更新 \(x_1 \rightarrow x_2 \rightarrow x_1 \rightarrow x_2 \dots\)。
让我们开始迭代计算。
迭代 0 (k=0)：
当前点：\(x_1^0 = 0.5, x_2^0 = 0.5\)，计算 \(f^0 = (0.5-1)^2 + 100*(0.25-0.5)^2 + 10*0.5 = 0.25 + 100*0.0625 + 5 = 0.25 + 6.25 + 5 = 11.5\)。
步骤三：第一次坐标更新（优化 \(x_1\)，固定 \(x_2 = 0.5\)）
子问题：\(\min_{x_1 \ge 0} \phi_1(x_1) = (x_1 - 1)^2 + 100(x_1^2 - 0.5)^2 + 10*|0.5|\)。
常数项 \(10*0.5 = 5\) 对优化无影响，可以忽略。所以我们实际上最小化：
\[\phi_1(x_1) = (x_1 - 1)^2 + 100(x_1^2 - 0.5)^2。 \]
这是一个关于 \(x_1\) 的四次多项式。我们寻找其导数零点（临界点）：
\[\frac{d\phi_1}{dx_1} = 2(x_1 - 1) + 100 * 2*(x_1^2 - 0.5) * 2x_1 = 2(x_1 - 1) + 400x_1(x_1^2 - 0.5)。 \]
令导数为零：
\[2(x_1 - 1) + 400x_1^3 - 200x_1 = 0 \implies 400x_1^3 - 198x_1 - 2 = 0。 \]
这是一个一元三次方程。我们可以尝试牛顿法求解，或者观察/近似求解。注意到当 \(x_1\) 接近 1 时，\((x_1-1)^2\) 项会很小，但 \(100(x_1^2-0.5)^2\) 会很大（因为 \(1^2 - 0.5 = 0.5\)）。也许最优解会更靠近使 \(x_1^2\) 接近 \(x_2=0.5\) 的值，即 \(x_1 \approx \sqrt{0.5} \approx 0.707\)。
让我们数值求解这个三次方程。定义一个函数 \(g(x_1) = 400x_1^3 - 198x_1 - 2\)。牛顿法迭代公式：\(x_1^{new} = x_1^{old} - g(x_1^{old}) / g‘(x_1^{old})\)，其中 \(g’(x_1) = 1200x_1^2 - 198\)。
从 \(x_1=0.7\) 开始：
- \(g(0.7) = 400*0.343 - 198*0.7 - 2 = 137.2 - 138.6 - 2 = -3.4\)
- \(g'(0.7) = 1200*0.49 - 198 = 588 - 198 = 390\)
- 更新：\(x_1 = 0.7 - (-3.4)/390 \approx 0.7 + 0.00872 \approx 0.70872\)
再迭代一次：
- \(g(0.70872) \approx 400*0.356 - 198*0.70872 - 2 = 142.4 - 140.32656 - 2 = 0.07344\)
- \(g'(0.70872) \approx 1200*0.5023 - 198 = 602.76 - 198 = 404.76\)
- 更新：\(x_1 \approx 0.70872 - 0.07344/404.76 \approx 0.70872 - 0.000181 \approx 0.70854\)
我们取 \(x_1^1 \approx 0.7085\)。由于 \(x_1^1 > 0\)，满足约束。所以更新 \(x_1^1 = 0.7085\)， \(x_2^1 = x_2^0 = 0.5\)。
计算新函数值 \(f^1\)（第一次更新后）：
\(f^1 = (0.7085-1)^2 + 100*(0.7085^2 - 0.5)^2 + 10*0.5\)
\(= (-0.2915)^2 + 100*(0.5020 - 0.5)^2 + 5\)
\(= 0.08497 + 100*(0.0020)^2 + 5\)
\(= 0.08497 + 100*0.000004 + 5 \approx 0.08497 + 0.0004 + 5 \approx 5.08537\)。
相比 \(f^0 = 11.5\)，函数值大幅下降。
步骤四：第二次坐标更新（优化 \(x_2\)，固定 \(x_1 = 0.7085\)）
子问题：\(\min_{x_2 \ge 0} \phi_2(x_2) = (0.7085 - 1)^2 + 100(0.7085^2 - x_2)^2 + 10|x_2|\)。
常数项 \((0.7085 - 1)^2 = 0.08497\) 可以忽略。所以我们最小化：
\[\phi_2(x_2) = 100(0.5020 - x_2)^2 + 10|x_2|。 \]
由于约束 \(x_2 \ge 0\)，所以 \(|x_2| = x_2\)。问题简化为：
\[\min_{x_2 \ge 0} \ \psi(x_2) = 100(x_2 - 0.5020)^2 + 10x_2。 \]
这是一个带有非光滑项（但在这里由于约束变得线性）的二次函数。我们求其无约束最小值（不考虑 \(x_2 \ge 0\)）：
对 \(\psi(x_2)\) 求导：\(\psi'(x_2) = 200(x_2 - 0.5020) + 10\)。
令导数为零：\(200(x_2 - 0.5020) + 10 = 0 \implies x_2 - 0.5020 = -10/200 = -0.05 \implies x_2^* = 0.5020 - 0.05 = 0.4520\)。
由于 \(x_2^* = 0.4520 > 0\)，满足约束，所以这就是最优解。因此，更新 \(x_2^2 = 0.4520\)， \(x_1^2 = x_1^1 = 0.7085\)。
计算新函数值 \(f^2\)（完成第一轮循环后）：
\(f^2 = (0.7085-1)^2 + 100*(0.5020 - 0.4520)^2 + 10*0.4520\)
\(= 0.08497 + 100*(0.05)^2 + 4.52\)
\(= 0.08497 + 100*0.0025 + 4.52 = 0.08497 + 0.25 + 4.52 = 4.85497\)。
函数值从 \(5.08537\) 下降到 \(4.85497\)。
步骤五：后续迭代与收敛
现在我们已经完成了一轮完整的坐标循环（更新了 \(x_1\) 和 \(x_2\)）。算法会继续迭代：
- 下一次更新 \(x_1\)（第二轮）：固定 \(x_2 = 0.4520\)，求解 \(\min_{x_1 \ge 0} (x_1-1)^2 + 100(x_1^2 - 0.4520)^2\)。可以预见，最优的 \(x_1\) 会使 \(x_1^2\) 更靠近 0.4520，即 \(x_1 \approx \sqrt{0.4520} \approx 0.6723\)。通过类似牛顿法求解，会得到一个更精确的值，比如 \(x_1^3 \approx 0.6730\)。
- 下一次更新 \(x_2\)（第二轮）：固定新的 \(x_1 \approx 0.6730\)，则 \(x_1^2 \approx 0.4529\)，求解 \(\min_{x_2 \ge 0} 100(0.4529 - x_2)^2 + 10x_2\)。无约束最优解为 \(x_2^* = 0.4529 - 0.05 = 0.4029\)，满足约束。
如此反复迭代。你会发现一个模式：每次更新 \(x_1\) 时，我们试图让 \(x_1^2\) 接近当前的 \(x_2\)；每次更新 \(x_2\) 时，我们得到 \(x_2^* = x_1^2 - 0.05\)（因为导数零点公式是 \(x_2 = x_1^2 - 0.05\)）。
经过多轮迭代，序列 \(\{x_1^k, x_2^k\}\) 将收敛到一个不动点（固定点），即满足：
\[x_1^2 = x_2 + 0.05 \quad \text{(来自 } x_2 \text{ 子问题最优性条件)} \\ \text{且 } x_1 \text{ 是 } \min_{x_1 \ge 0} (x_1-1)^2 + 100(x_1^2 - x_2)^2 \text{ 的解。} \]
将第一个等式 \(x_2 = x_1^2 - 0.05\) 代入第二个条件关于 \(x_1\) 的优化问题中，最终问题会收敛到满足一阶最优性条件的点。
通过编程进行多次迭代（比如20-30次），最终我们会得到近似最优解。对于这个简单例子，我们可以推演其极限：假设收敛点为 \((x_1^*, x_2^*)\)。由 \(x_2\) 的最优性条件，有 \(x_2^* = (x_1^*)^2 - 0.05\)。将其代入 \(x_1\) 的优化问题，求解 \(\min_{x_1 \ge 0} (x_1-1)^2 + 100(0.05)^2\)。等等，这里似乎有个有趣的现象：当 \(x_2^* = (x_1^*)^2 - 0.05\) 时，\((x_1^2 - x_2)^2 = 0.05^2 = 0.0025\)，变成一个常数。所以 \(x_1\) 的子问题变成了简单的 \(\min_{x_1 \ge 0} (x_1-1)^2\)，其解显然是 \(x_1^* = 1\)。但这会导致 \(x_2^* = 1^2 - 0.05 = 0.95\)。让我们检查这是否是整体最优解的一个驻点。
计算在 \((1, 0.95)\) 处的梯度（考虑约束）：
\(\nabla f = [2(x_1-1) + 400x_1(x_1^2 - x_2), \ -200(x_1^2 - x_2) + 10 * sign(x_2)]\)。
代入得：第一部分 = \(2(0) + 400*1*(1-0.95) = 400*0.05 = 20\)。
第二部分 = \(-200*(1-0.95) + 10*1 = -200*0.05 + 10 = -10 + 10 = 0\)。
所以梯度为 \((20, 0)\)。对于 \(x_1 \ge 0\) 的约束，在 \(x_1=1>0\) 处，梯度分量20不为零，说明这不是一个无约束驻点。但它是坐标下降法可能收敛的点吗？在坐标下降法中，当我们固定 \(x_2=0.95\) 优化 \(x_1\) 时，我们需要解 \(\min_{x_1 \ge 0} (x_1-1)^2 + 100(x_1^2 - 0.95)^2\)。这个函数在 \(x_1=1\) 处的导数是 \(2(0) + 400*1*(1-0.95)=20 > 0\)，意味着 \(x_1=1\) 并不是这个子问题的局部最小值（因为导数为正，函数在 \(x_1=1\) 处是上升的）。实际上，如果 \(x_2\) 固定为 0.95，让 \(x_1^2\) 接近 0.95 可能比让 \(x_1\) 接近 1 更重要，因为前一项有系数100。所以坐标下降法可能不会收敛到 \((1, 0.95)\)。
通过数值实验（或更仔细的推导）可以发现，坐标下降法会收敛到另一个平衡点，例如 \(x_1 \approx 0.7, x_2 \approx 0.45\) 附近。这个点满足：当固定一方时，另一方是最优的，即是一个坐标最优点。对于非凸问题，坐标下降法保证收敛到一个驻点（所有坐标方向都是局部最优），但不一定是全局最优解。
步骤六：总结与算法特点
通过以上迭代，我们演示了坐标下降法的核心步骤：
- 分解：将高维问题分解为一系列一维子问题。
- 求解子问题：每个子问题是在简单约束下优化单变量函数，通常可以快速求解（解析解、闭式解或高效的一维搜索）。
- 迭代更新：循环或随机选择坐标进行更新，逐步降低目标函数值。
优点：
- 每步迭代计算成本低，内存需求小，非常适合高维问题。
- 对于可分离问题或 \(g(\mathbf{x})\) 是二次型等结构良好的问题，子问题求解极快。
- 实现简单。
缺点：
- 收敛速度可能是线性的，且速度依赖于坐标系的选取。
- 对于非凸问题，可能收敛到非驻点的坐标最优解（但通常也是驻点）。
- 当变量间强耦合时（如我们的例子中 \(x_1^2\) 和 \(x_2\)），收敛可能较慢，出现“之字形”路径。
进阶技巧：
- 随机坐标下降：每次随机选择一个坐标进行更新，有更好的理论收敛保证。
- 加速坐标下降：引入Nesterov动量等加速技术。
- 块坐标下降：将变量分组，每次优化一组变量，适用于具有块可分离结构的问题。
通过这个实例，你理解了坐标下降法如何通过解决一系列简单的一维问题，来攻克复杂的高维优化难题。