非线性规划中的随机坐标搜索算法基础题
题目描述：
考虑一个无约束非线性优化问题：
min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
其中 \(x = (x_1, x_2)^T \in \mathbb{R}^2\)。
请使用随机坐标搜索算法求解此问题。算法从初始点 \(x^{(0)} = (0.0, 3.0)^T\) 开始，搜索步长固定为 \(\alpha = 0.1\)，迭代次数上限为 100 次，并假设每次迭代随机选择一个坐标方向进行搜索。要求详细解释算法步骤，并展示前 3 次迭代的手动计算过程，最后讨论算法的特性。
解题过程：
1. 算法原理介绍
随机坐标搜索是一种简单的直接搜索方法，适用于无约束优化。其核心思想是：在每次迭代中，随机选择一个坐标轴方向，然后在该方向上进行试探性移动（向前或向后），如果移动能降低目标函数值，则接受该移动；否则，保持当前位置不变。之后进入下一次迭代。由于每次只沿一个坐标方向搜索，计算量小，但收敛速度通常较慢，尤其对于高度非线性的病态问题。
2. 算法步骤
设当前点为 \(x^{(k)} = (x_1^{(k)}, x_2^{(k)})^T\)，固定步长 \(\alpha > 0\)，最大迭代次数为 \(N_{\text{max}}\)。
- 初始化：给定初始点 \(x^{(0)}\)，设置 \(k = 0\)。
- 迭代过程（当 \(k < N_{\text{max}}\) 时）：
a. 随机选择坐标方向：以等概率（各 1/2）随机选择坐标索引 \(i \in \{1, 2\}\)。
b. 生成试探点：沿选定坐标方向进行正负两个方向的试探：- 正向试探点：\(x_+ = x^{(k)} + \alpha e_i\)，其中 \(e_i\) 是第 \(i\) 个单位向量。
- 负向试探点：\(x_- = x^{(k)} - \alpha e_i\)。
c. 评估目标函数：计算 \(f(x^{(k)})\)、\(f(x_+)\)、\(f(x_-)\)。
d. 选择移动方向：比较三个函数值： - 如果 \(f(x_+)\) 最小，则令 \(x^{(k+1)} = x_+\)。
- 如果 \(f(x_-)\) 最小，则令 \(x^{(k+1)} = x_-\)。
- 如果 \(f(x^{(k)})\) 最小，则令 \(x^{(k+1)} = x^{(k)}\)（不移动）。
e. 令 \(k = k + 1\)。
- 输出：迭代结束后，返回 \(x^{(k)}\) 作为近似最优解。
3. 手动计算前 3 次迭代
已知：\(f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)，\(x^{(0)} = (0.0, 3.0)^T\)，\(\alpha = 0.1\)。
计算初始点的函数值：
\[f(x^{(0)}) = (0 - 2)^4 + (0 - 2 \times 3)^2 = 16 + (-6)^2 = 16 + 36 = 52.0 \]
第 1 次迭代（k=0）：
- 假设随机选择坐标 \(i = 1\)（即沿 \(x_1\) 方向搜索）。
- 生成试探点：
\(x_+ = (0.0 + 0.1, 3.0)^T = (0.1, 3.0)^T\)
\(x_- = (0.0 - 0.1, 3.0)^T = (-0.1, 3.0)^T\) - 计算函数值：
\(f(x_+) = (0.1 - 2)^4 + (0.1 - 2 \times 3)^2 = (-1.9)^4 + (0.1 - 6)^2 = 13.0321 + (-5.9)^2 = 13.0321 + 34.81 = 47.8421\)
\(f(x_-) = (-0.1 - 2)^4 + (-0.1 - 6)^2 = (-2.1)^4 + (-6.1)^2 = 19.4481 + 37.21 = 56.6581\) - 比较：\(f(x_+) = 47.8421\)，\(f(x_-) = 56.6581\)，\(f(x^{(0)}) = 52.0\)。
\(f(x_+)\) 最小，因此接受正向移动：\(x^{(1)} = (0.1, 3.0)^T\)，\(f(x^{(1)}) = 47.8421\)。
第 2 次迭代（k=1）：
- 假设随机选择坐标 \(i = 2\)（即沿 \(x_2\) 方向搜索）。
- 生成试探点：
\(x_+ = (0.1, 3.0 + 0.1)^T = (0.1, 3.1)^T\)
\(x_- = (0.1, 3.0 - 0.1)^T = (0.1, 2.9)^T\) - 计算函数值：
\(f(x_+) = (0.1 - 2)^4 + (0.1 - 2 \times 3.1)^2 = (-1.9)^4 + (0.1 - 6.2)^2 = 13.0321 + (-6.1)^2 = 13.0321 + 37.21 = 50.2421\)
\(f(x_-) = (0.1 - 2)^4 + (0.1 - 2 \times 2.9)^2 = (-1.9)^4 + (0.1 - 5.8)^2 = 13.0321 + (-5.7)^2 = 13.0321 + 32.49 = 45.5221\) - 比较：\(f(x_+) = 50.2421\)，\(f(x_-) = 45.5221\)，\(f(x^{(1)}) = 47.8421\)。
\(f(x_-)\) 最小，因此接受负向移动：\(x^{(2)} = (0.1, 2.9)^T\)，\(f(x^{(2)}) = 45.5221\)。
第 3 次迭代（k=2）：
- 假设随机选择坐标 \(i = 1\)（沿 \(x_1\) 方向）。
- 生成试探点：
\(x_+ = (0.1 + 0.1, 2.9)^T = (0.2, 2.9)^T\)
\(x_- = (0.1 - 0.1, 2.9)^T = (0.0, 2.9)^T\) - 计算函数值：
\(f(x_+) = (0.2 - 2)^4 + (0.2 - 2 \times 2.9)^2 = (-1.8)^4 + (0.2 - 5.8)^2 = 10.4976 + (-5.6)^2 = 10.4976 + 31.36 = 41.8576\)
\(f(x_-) = (0.0 - 2)^4 + (0.0 - 2 \times 2.9)^2 = (-2)^4 + (0.0 - 5.8)^2 = 16 + (-5.8)^2 = 16 + 33.64 = 49.64\) - 比较：\(f(x_+) = 41.8576\)，\(f(x_-) = 49.64\)，\(f(x^{(2)}) = 45.5221\)。
\(f(x_+)\) 最小，因此接受正向移动：\(x^{(3)} = (0.2, 2.9)^T\)，\(f(x^{(3)}) = 41.8576\)。
至此，经过 3 次迭代，函数值从 52.0 下降至 41.8576。
4. 算法特性讨论
- 优点：算法简单，每步只需计算 2 个新点的函数值（正向和反向），计算成本低；不需要梯度信息，适用于不可导函数；易于并行化试探步骤。
- 缺点：收敛速度慢，尤其是当变量间耦合较强时（如本例中 \((x_1 - 2x_2)^2\) 项导致变量相互影响）；固定步长可能导致效率低下（步长太大可能跳过最优点，太小则收敛慢）；随机选择坐标可能使搜索方向不系统，可能重复选择同一坐标。
- 改进方向：可采用自适应步长（如根据成功/失败次数调整）、周期性循环坐标而非随机选择、或与其他局部搜索方法结合。
总结：随机坐标搜索是一种基础的局部搜索算法，适用于低维、计算函数值廉价的问题。对于本例，从 \((0.0, 3.0)\) 开始，经 3 步迭代后向最优解 \((2.0, 1.0)\)（可验证其为全局最优）缓慢移动。实际应用中，需设置合适的终止条件（如函数值变化小于阈值）。