本例中，去掉最差点 $ P_1(0.5, 0.5) $，计算 $ P_2, P_3, P_4 $ 的重心：

检验 $ X_c $ 的可行性： $ g_1 = 1.0 + 2*0.6667 - 4 = 1.0 + 1.3334 - 4 = -1.6666 \le 0 $，满足。且 $ x_1, x_2 \ge 0 $。故重心可行。

其中 $ X_h = P_1 = (0.5, 0.5) $。

如果 $ \sigma < \epsilon $（例如 $ \epsilon = 10^{-4} $），则停止迭代，输出当前最好点作为近似最优解。
当前四点函数值：3.0693, 4.5, 6.25, 7.25。平均值 $ \bar{f} \approx 5.267 $，标准差 $ \sigma \approx 1.73 $，较大，不收敛，继续迭代。

非线性规划中的复合形法基础题 题目描述 考虑以下非线性规划问题： \[\min f(x_ 1, x_ 2) = (x_ 1 - 3)^2 + (x_ 2 - 2)^2\] \[ \begin{aligned} \text{s.t. } & g_ 1(x_ 1, x_ 2) = x_ 1 + 2x_ 2 - 4 \le 0, \\ & g_ 2(x_ 1, x_ 2) = -x_ 1 \le 0, \\ & g_ 3(x_ 1, x_ 2) = -x_ 2 \le 0. \end{aligned} \] 这是一个简单的带线性不等式约束的凸二次规划问题。我们要求使用 复合形法 （也称为复合形搜索法，Complex Method，是Nelder-Mead单纯形法在约束优化中的一种推广）来求解此问题。复合形法是一种直接搜索法，它通过在可行域内构造并迭代更新一个由多个顶点（称为复合形）构成的几何结构来寻找最优解，无需计算目标函数的梯度。 解题过程讲解 第一步：理解复合形法的基本思想 复合形法的核心思想是模拟一个“复合形”在可行域内的移动。这个复合形由 \( k \) 个顶点（或称点）构成，其中 \( k \geq n+1 \)，\( n \) 是变量的维数（本例中 \( n=2 \)）。通常取 \( k = 2n \)。算法在每一步都会计算复合形所有顶点处的目标函数值，找到最差点（目标函数值最大的点），然后尝试用一个新的、更好的点替换这个最差点。新点的产生通常通过“反射”最差点通过复合形重心的操作得到，并确保新点仍在可行域内。通过反复迭代，复合形会收缩并移向最优解附近。 第二步：算法初始化 确定参数 ：变量维数 \( n=2 \)。我们选择复合形顶点数 \( k = 2n = 4 \)。 生成初始复合形 ：我们需要在可行域内随机生成 4 个可行点。可行域由约束 \( g_ 1 \le 0, g_ 2 \le 0, g_ 3 \le 0 \) 定义，即 \( x_ 1 \ge 0, x_ 2 \ge 0, x_ 1 + 2x_ 2 \le 4 \)。 我们可以手动构造或通过随机投点并检验可行性的方式生成。一个简单的手动构造例子（满足所有约束）： 点 \( P_ 1 = (0.5, 0.5) \)， \( f = (0.5-3)^2 + (0.5-2)^2 = 6.25 + 2.25 = 8.5 \) 点 \( P_ 2 = (1.0, 0.5) \)， \( f = 4 + 2.25 = 6.25 \) 点 \( P_ 3 = (0.5, 1.0) \)， \( f = 6.25 + 1 = 7.25 \) 点 \( P_ 4 = (1.5, 0.5) \)， \( f = 2.25 + 2.25 = 4.5 \) 计算这4个点的目标函数值 \( f \)，如上所示。 初始排序 ：根据目标函数值从小到大排序（因为我们求最小化）： 最好点（最佳）： \( P_ 4, f=4.5 \) 次好点： \( P_ 2, f=6.25 \) 次差点： \( P_ 3, f=7.25 \) 最差点（最差）： \( P_ 1, f=8.5 \) 记最差点为 \( X_ h \)，最好点为 \( X_ l \)。 第三步：进行一次迭代（示例） 假设我们设置反射系数 \( \alpha = 1.3 \)（通常取 \( 1.0 \) 到 \( 2.0 \) 之间），收缩系数 \( \beta = 0.5 \)，扩展系数 \( \gamma = 2.0 \)（可选，基础复合形法常只使用反射和收缩）。我们进行第一次迭代。 计算除最差点外其他点的重心 \( X_ c \) ： \[ X_ c = \frac{1}{k-1} \sum_ {i=1, i \neq h}^{k} X_ i \] 本例中，去掉最差点 \( P_ 1(0.5, 0.5) \)，计算 \( P_ 2, P_ 3, P_ 4 \) 的重心： \[ X_ c = \frac{1}{3} \left[ (1.0, 0.5) + (0.5, 1.0) + (1.5, 0.5) \right ] = \frac{1}{3} (3.0, 2.0) = (1.0, 2/3) \approx (1.0, 0.6667) \] 检验 \( X_ c \) 的可行性： \( g_ 1 = 1.0 + 2* 0.6667 - 4 = 1.0 + 1.3334 - 4 = -1.6666 \le 0 \)，满足。且 \( x_ 1, x_ 2 \ge 0 \)。故重心可行。 反射操作 ：计算反射点 \( X_ r \)。 \[ X_ r = X_ c + \alpha (X_ c - X_ h) \] 其中 \( X_ h = P_ 1 = (0.5, 0.5) \)。 \[ X_ c - X_ h = (1.0 - 0.5, 0.6667 - 0.5) = (0.5, 0.1667) \] \[ X_ r = (1.0, 0.6667) + 1.3 * (0.5, 0.1667) = (1.0, 0.6667) + (0.65, 0.2167) = (1.65, 0.8834) \] 可行性处理 ：检查 \( X_ r \) 是否在可行域内。 \( g_ 1 = 1.65 + 2* 0.8834 - 4 = 1.65 + 1.7668 - 4 = -0.5832 \le 0 \)，满足。 \( g_ 2 = -1.65 \le 0 \)，满足。 \( g_ 3 = -0.8834 \le 0 \)，满足。 所以 \( X_ r \) 是可行点。 评估反射点 ：计算 \( f(X_ r) = (1.65-3)^2 + (0.8834-2)^2 = (-1.35)^2 + (-1.1166)^2 = 1.8225 + 1.2468 = 3.0693 \)。 比较与替换 ： 将 \( f(X_ r) = 3.0693 \) 与当前复合形中最差点的函数值 \( f(X_ h) = 8.5 \) 和最好点的函数值 \( f(X_ l) = 4.5 \) 比较。 因为 \( f(X_ r) < f(X_ l) \)，即反射点比当前最好点还好。 这是一个非常好的情况 。基础复合形法通常直接接受反射点 \( X_ r \) 替换最差点 \( X_ h \)。 但也有更复杂的策略：如果 \( f(X_ r) < f(X_ l) \)，可以尝试“扩展”操作，即沿反射方向走得更远：\( X_ e = X_ c + \gamma (X_ r - X_ c) \)，若扩展点可行且更好，则用 \( X_ e \) 替换 \( X_ h \)；否则用 \( X_ r \) 替换。这里为简单，我们直接接受 \( X_ r \)。 更新复合形 ：用 \( X_ r(1.65, 0.8834) \) 替换最差点 \( X_ h(P_ 1) \)。 新的复合形四点变为：\( P_ 4(1.5,0.5), P_ 2(1.0,0.5), P_ 3(0.5,1.0), X_ r(1.65,0.8834) \)。 重新计算函数值并排序： \( f(P_ 4)=4.5 \)， \( f(P_ 2)=6.25 \)， \( f(P_ 3)=7.25 \)， \( f(X_ r)=3.0693 \)。 新排序：最好点 \( X_ r(f=3.0693) \)， 最差点 \( P_ 3(f=7.25) \)。 第四步：收敛性检查与后续迭代 收敛准则 ：常见的准则是检查复合形中所有顶点函数值的标准差，或者最好点与最差点的函数值之差是否小于给定容差 \( \epsilon \)。例如，计算所有顶点函数值的平均值 \( \bar{f} \)，然后计算标准差： \[ \sigma = \sqrt{ \frac{1}{k} \sum_ {i=1}^{k} (f_ i - \bar{f})^2 } \] 如果 \( \sigma < \epsilon \)（例如 \( \epsilon = 10^{-4} \)），则停止迭代，输出当前最好点作为近似最优解。 当前四点函数值：3.0693, 4.5, 6.25, 7.25。平均值 \( \bar{f} \approx 5.267 \)，标准差 \( \sigma \approx 1.73 \)，较大，不收敛，继续迭代。 后续迭代 ： 在新的复合形中，最差点是 \( P_ 3(0.5,1.0) \)，最好点是 \( X_ r(1.65,0.8834) \)。 重复第三步的过程：计算除 \( P_ 3 \) 外其他三点（\( P_ 4, P_ 2, X_ r \)）的重心 \( X_ c' \)。 对最差点 \( P_ 3 \) 关于新重心 \( X_ c' \) 做反射，得到新反射点 \( X_ r' \)。 检查 \( X_ r' \) 的可行性，计算其函数值。 根据函数值比较结果（比最差点好，但不如最好点；或者比最好点还好等），决定是接受反射点，还是进行收缩（如果反射点不比最差点好，则尝试在重心和最差点之间取一个收缩点），或者扩展。 更新复合形，重新排序，检查收敛。 第五步：算法总结与最终解 算法框架 ： 初始化 ：在可行域内生成 \( k \) 个点构成初始复合形， \( k \ge n+1 \)。 迭代 ：直到满足收敛准则： a. 确定最差点 \( X_ h \) 和最好点 \( X_ l \)。 b. 计算除 \( X_ h \) 外其他点的重心 \( X_ c \)。 c. 计算反射点 \( X_ r = X_ c + \alpha (X_ c - X_ h) \)。 d. 若 \( X_ r \) 不可行，则将其向可行域内移动（例如逐步向重心收缩直到可行）。 e. 比较 \( f(X_ r) \)： * 若 \( f(X_ r) < f(X_ l) \)：可尝试扩展点 \( X_ e = X_ c + \gamma (X_ r - X_ c) \)，若 \( X_ e \) 可行且 \( f(X_ e) < f(X_ r) \)，则用 \( X_ e \) 替换 \( X_ h \)；否则用 \( X_ r \) 替换 \( X_ h \)。 * 若 \( f(X_ l) \le f(X_ r) < f(\text{次差点}) \)：用 \( X_ r \) 替换 \( X_ h \)。 * 若 \( f(X_ r) \ge f(\text{次差点}) \)：进行收缩操作。如果 \( f(X_ r) < f(X_ h) \)，则计算收缩点 \( X_ s = X_ c + \beta (X_ r - X_ c) \)；否则计算收缩点 \( X_ s = X_ c + \beta (X_ h - X_ c) \)。若 \( X_ s \) 可行且 \( f(X_ s) < f(X_ h) \)，则用 \( X_ s \) 替换 \( X_ h \)；否则进行复合形收缩（向最好点靠拢）。 输出 ：迭代结束时，复合形中最好点 \( X_ l \) 作为近似最优解。 应用到本题 ：通过多次迭代，复合形会逐渐向真正的最优点移动。对于本题，最优解可以通过解析法验证：目标函数是凸函数，约束是线性的。在可行域 \( x_ 1 \ge 0, x_ 2 \ge 0, x_ 1+2x_ 2 \le 4 \) 内，无约束最优点 \( (3,2) \) 不满足约束 \( x_ 1+2x_ 2 \le 4 \)（因为 \( 3+4=7>4 \)）。约束最优点在直线 \( x_ 1+2x_ 2=4 \) 上，且是目标函数等值线与该直线的切点。利用拉格朗日乘子法或观察（目标函数圆心在(3,2)，向约束边界投影）可得最优解约为 \( (2, 1) \)， \( f_ {min} = (2-3)^2 + (1-2)^2 = 1+1=2 \)。复合形法经过足够多次迭代后，其最好点会非常接近 \( (2, 1) \)，函数值接近2。 关键点 ：复合形法是一种基于直接搜索的约束优化方法，它通过比较复合形顶点的函数值来决定搜索方向，通过反射、扩展、收缩等几何操作更新顶点，无需导数信息，能处理不等式约束，但收敛速度通常比基于梯度的方法慢，且对初始复合形和参数（\( \alpha, \beta, \gamma \)）有一定敏感性。