非线性规划中的复合形法进阶题 我将为您讲解非线性规划中的复合形法（Complex Method），这是解决约束优化问题的一种直接搜索方法。让我们从问题描述开始，然后逐步深入解题过程。 问题描述 考虑以下约束非线性规划问题： 最小化 f(x) = (x₁ - 3)² + (x₂ - 2)² 约束条件： g₁(x) = x₁ + x₂ - 4 ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 其中 x = (x₁, x₂) ∈ R² 这是一个简单的二维二次规划问题，目标函数是凸二次函数，约束条件是线性的。最优解在x* = (2,2)，f(x* ) = 1。 解题过程 1. 复合形法基本概念 复合形法是单纯形法的扩展，用于处理有约束的非线性规划问题。与单纯形法使用n+1个顶点不同，复合形法使用k个顶点（通常k > n+1，这里n=2，我们取k=4）。 核心思想：在可行域内构造一个由多个顶点组成的"复合形"，通过反射、扩展、收缩等操作，使复合形逐步向最优点移动。 2. 算法初始化 步骤2.1：生成初始复合形 我们需要在可行域内随机生成4个顶点。由于约束条件简单，我们可以通过以下方式生成： 顶点1：x¹ = (1, 1) - 满足所有约束 顶点2：x² = (2, 1) - 满足所有约束 顶点3：x³ = (1, 2) - 满足所有约束 顶点4：x⁴ = (2, 2) - 满足所有约束 计算各顶点函数值： f(x¹) = (1-3)² + (1-2)² = 4 + 1 = 5 f(x²) = (2-3)² + (1-2)² = 1 + 1 = 2 f(x³) = (1-3)² + (2-2)² = 4 + 0 = 4 f(x⁴) = (2-3)² + (2-2)² = 1 + 0 = 1 3. 迭代过程 - 第一轮 步骤3.1：确定最差点和最好点 最差点 xʰ：f值最大的顶点，x¹ = (1,1)，f=5 次最差点 xˢ：f值第二大的顶点，x³ = (1,2)，f=4 最好点 xˡ：f值最小的顶点，x⁴ = (2,2)，f=1 步骤3.2：计算除最差点外的重心 xᶜ = (x² + x³ + x⁴) / 3 = [ (2,1) + (1,2) + (2,2) ] / 3 = (5,5)/3 ≈ (1.667, 1.667) 步骤3.3：反射操作 反射公式：xʳ = xᶜ + α(xᶜ - xʰ)，其中α是反射系数（通常取1.3） xʳ = (1.667,1.667) + 1.3 × [ (1.667,1.667) - (1,1) ] = (1.667,1.667) + 1.3 × (0.667,0.667) = (1.667,1.667) + (0.867,0.867) = (2.534, 2.534) 步骤3.4：可行性检查 检查xʳ = (2.534, 2.534)是否满足约束： g₁(x) = 2.534 + 2.534 - 4 = 1.068 > 0 ✗ 违反第一个约束 由于xʳ不可行，我们需要将其向重心收缩： xʳ = xᶜ + β(xʳ - xᶜ)，其中β是收缩系数（取0.5） xʳ = (1.667,1.667) + 0.5 × [ (2.534,2.534) - (1.667,1.667) ] = (1.667,1.667) + 0.5 × (0.867,0.867) = (1.667,1.667) + (0.4335,0.4335) = (2.1005, 2.1005) 重新检查可行性： g₁(x) = 2.1005 + 2.1005 - 4 = 0.201 > 0 ✗ 仍然违反 继续收缩，直到满足约束。经过几次收缩后，我们得到可行点xʳ = (1.9, 1.9) 4. 迭代过程 - 第二轮 步骤4.1：更新复合形 用xʳ = (1.9, 1.9)替换最差点xʰ = (1,1) 新的复合形顶点： x¹ = (1.9, 1.9), f=1.22 x² = (2, 1), f=2 x³ = (1, 2), f=4 x⁴ = (2, 2), f=1 步骤4.2：确定最差点和最好点 最差点 xʰ：x³ = (1,2), f=4 最好点 xˡ：x⁴ = (2,2), f=1 步骤4.3：计算重心（排除最差点） xᶜ = [ (1.9,1.9) + (2,1) + (2,2) ] / 3 = (5.9,4.9)/3 ≈ (1.967, 1.633) 步骤4.4：反射操作 xʳ = xᶜ + α(xᶜ - xʰ) = (1.967,1.633) + 1.3 × [ (1.967,1.633) - (1,2) ] = (1.967,1.633) + 1.3 × (0.967,-0.367) = (1.967,1.633) + (1.257,-0.477) = (3.224, 1.156) 检查可行性： g₁(x) = 3.224 + 1.156 - 4 = 0.38 > 0 ✗ 违反约束 收缩到可行点：xʳ = (2.2, 1.5) 5. 收敛判断 我们继续迭代过程，每次： 找到最差点并计算其他点的重心 反射最差点通过重心 如果反射点不可行，收缩到可行域内 用新点替换最差点 终止条件：当复合形中所有顶点的函数值差异足够小，或者达到最大迭代次数时停止。 经过若干轮迭代后，复合形将收缩到最优点(2,2)附近。 6. 算法特点总结 复合形法不需要计算梯度，适用于不可微函数 通过保持复合形在可行域内来处理约束 反射系数α通常取1.3，提供过度反射以避免循环 当反射点不可行时，通过收缩将其拉回可行域 算法简单直观，但收敛速度较慢，适合中小规模问题 这个方法通过群体智能的思想，利用多个顶点的集体移动来探索搜索空间，最终收敛到最优解附近。