非线性规划中的坐标轮换法基础题
题目描述
考虑一个二维非线性规划问题：
最小化目标函数 \(f(x_1, x_2) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)
初始点为 \(x^{(0)} = (0, 3)\)，收敛容差 \(\epsilon = 0.001\)。要求使用坐标轮换法求解该问题，并分析迭代过程。
解题过程
坐标轮换法（Coordinate Descent）通过轮流沿每个坐标方向进行一维搜索来逼近极小点。具体步骤如下：
1. 算法原理
- 在每次迭代中，依次沿每个坐标轴方向（例如 \(e_1 = (1,0)\)、\(e_2 = (0,1)\)）求解一维优化问题：
\(\min_{\alpha} f(x + \alpha e_i)\) - 更新当前点后继续下一个方向，循环直至满足收敛条件。
2. 第一轮迭代（从 \( x^{(0)} = (0, 3) \）
-
沿 \(x_1\) 方向搜索：
固定 \(x_2 = 3\)，目标函数简化为：
\(g(\alpha) = f(0 + \alpha, 3) = (\alpha - 2)^4 + (\alpha - 6)^2\)
求导：\(g'(\alpha) = 4(\alpha - 2)^3 + 2(\alpha - 6)\)
通过牛顿法或试值法求解 \(g'(\alpha) = 0\)，得 \(\alpha \approx 2.5\)（具体计算需解方程 \(4(\alpha-2)^3 + 2(\alpha-6) = 0\)）。
更新点：\(x^{(1)} = (0 + 2.5, 3) = (2.5, 3)\) -
沿 \(x_2\) 方向搜索：
固定 \(x_1 = 2.5\)，目标函数简化为：
\(h(\beta) = f(2.5, 3 + \beta) = (2.5 - 2)^4 + (2.5 - 2(3+\beta))^2 = 0.0625 + (-3.5 - 2\beta)^2\)
求导：\(h'(\beta) = 2(-3.5 - 2\beta)(-2) = 8(-3.5 - 2\beta)\)
令 \(h'(\beta) = 0\)，得 \(\beta = -1.75\)
更新点：\(x^{(2)} = (2.5, 3 - 1.75) = (2.5, 1.25)\)
3. 收敛判断
计算相邻两轮迭代点的距离：
\(\| x^{(2)} - x^{(0)} \| = \sqrt{(2.5 - 0)^2 + (1.25 - 3)^2} \approx 3.20 > \epsilon\)
未收敛，继续迭代。
4. 第二轮迭代（从 \( x^{(2)} = (2.5, 1.25) \）
-
沿 \(x_1\) 方向：
固定 \(x_2 = 1.25\)，\(f(x_1, 1.25) = (x_1 - 2)^4 + (x_1 - 2.5)^2\)
求导并解方程得最优步长 \(\alpha \approx 1.8\)（需数值计算），更新为 \(x^{(3)} = (1.8, 1.25)\) -
沿 \(x_2\) 方向：
固定 \(x_1 = 1.8\)，\(f(1.8, x_2) = (-0.2)^4 + (1.8 - 2x_2)^2\)
求导得 \(\beta = 0.9\)，更新为 \(x^{(4)} = (1.8, 0.35)\)
5. 后续迭代与收敛
重复上述过程，每轮沿两个坐标方向依次优化。经过多轮迭代后，点列逼近理论最优解 \(x^* \approx (2.0, 1.0)\)。当连续两轮迭代点的距离小于 \(\epsilon = 0.001\) 时停止。
关键点说明
- 坐标轮换法简单易实现，但可能收敛较慢（尤其目标函数呈窄长谷状时）。
- 一维搜索可使用解析法（如求导）或数值方法（如黄金分割法）。
- 本题中，目标函数为多项式，求导解析解可行；若函数复杂，需数值近似。