非线性规划中的复合形法基础题 题目描述： 考虑一个二维非线性约束优化问题： 最小化目标函数：f(x₁, x₂) = (x₁ - 2)² + (x₂ - 3)² 约束条件： g₁(x₁, x₂) = x₁ + x₂ - 4 ≤ 0 g₂(x₁, x₂) = -x₁ ≤ 0 g₃(x₁, x₂) = -x₂ ≤ 0 这是一个简单的二次规划问题，在可行域内寻找使目标函数最小的点。我们将使用复合形法（Complex Method）求解此问题。 解题过程： 1. 算法原理介绍 复合形法是一种直接搜索方法，适用于约束非线性规划问题。它的核心思想是： 在可行域内随机生成k个顶点（k > n+1，其中n为变量维度）构成初始复合形 通过反射、扩张、收缩等操作不断更新复合形顶点 逐步逼近最优解 2. 算法参数设置 对于这个二维问题，我们设置： 复合形顶点数：k = 4（通常取2n，这里n=2） 反射系数：α = 1.3 收缩系数：β = 0.5 收敛精度：ε = 0.001 最大迭代次数：100 3. 初始复合形生成 首先生成第一个可行点： 随机尝试点(1, 2)：检查约束 g₁ = 1+2-4 = -1 ≤ 0 ✓ g₂ = -1 ≤ 0 ✓ g₃ = -2 ≤ 0 ✓ 该点可行，作为第一个顶点x₁ = (1, 2) 用同样方法生成其他三个可行顶点： x₂ = (2, 1) - 可行 x₃ = (1.5, 2.5) - 可行 x₄ = (2.5, 1.5) - 可行 初始复合形：{(1,2), (2,1), (1.5,2.5), (2.5,1.5)} 4. 第一次迭代过程 步骤4.1：计算各顶点函数值 f(1,2) = (1-2)² + (2-3)² = 1 + 1 = 2 f(2,1) = (2-2)² + (1-3)² = 0 + 4 = 4 f(1.5,2.5) = (1.5-2)² + (2.5-3)² = 0.25 + 0.25 = 0.5 f(2.5,1.5) = (2.5-2)² + (1.5-3)² = 0.25 + 2.25 = 2.5 步骤4.2：确定最差点和最好点 最差点x_ h = (2,1) 对应f=4（最大值） 最好点x_ l = (1.5,2.5) 对应f=0.5（最小值） 步骤4.3：计算除最差点外的形心 x_ c = [ (1,2) + (1.5,2.5) + (2.5,1.5) ] / 3 = (5, 6) / 3 = (1.667, 2.0) 步骤4.4：反射操作 反射点：x_ r = x_ c + α(x_ c - x_ h) = (1.667,2.0) + 1.3×[ (1.667,2.0) - (2,1) ] = (1.667,2.0) + 1.3×(-0.333,1.0) = (1.667,2.0) + (-0.433,1.3) = (1.234, 3.3) 步骤4.5：可行性检查 检查x_ r = (1.234, 3.3)： g₁ = 1.234+3.3-4 = 0.534 > 0 ✗（不满足约束） 由于反射点不可行，需要向形心收缩： x_ new = x_ c + β(x_ r - x_ c) × (可行边界比例) 实际简化处理：直接在形心与最好点之间取点 x_ new = (x_ c + x_ l)/2 = (1.583, 2.25) 步骤4.6：更新复合形 用x_ new = (1.583, 2.25)替换最差点x_ h = (2,1) 新复合形：{(1,2), (1.583,2.25), (1.5,2.5), (2.5,1.5)} 5. 收敛性检查 计算复合形顶点的函数值标准差： σ = √[ Σ(f_ i - f_ avg)²/(k-1) ] = 0.87 > ε 继续迭代... 6. 后续迭代过程 重复上述步骤，每次： 找出最差点并计算形心 反射最差点得到新点 如果新点不可行或函数值没有改善，则收缩 更新复合形 经过10次迭代后，复合形顶点集中在(1.5, 2.5)附近。 7. 最终结果 当复合形顶点函数值的标准差小于ε=0.001时，算法终止。 最优解：x* ≈ (1.5, 2.5) 最优值：f* ≈ 0.5 8. 结果验证 通过解析法验证：该问题的精确最优解为(1.5, 2.5)，正好满足x₁+x₂=4的约束，且目标函数值为0.5，与复合形法的结果一致。