非线性规划中的积极集法基础题 题目描述 考虑以下不等式约束非线性规划问题： 最小化函数 f(x) = (x₁ - 2)² + (x₂ - 1)² 满足约束条件： g₁(x) = x₁ + x₂ - 2 ≤ 0 g₂(x) = x₁² - x₂ ≤ 0 g₃(x) = -x₁ ≤ 0 g₄(x) = -x₂ ≤ 0 这是一个二维优化问题，目标函数是凸二次函数，约束包括线性不等式和非线性不等式。我们需要找到满足所有约束的条件下使目标函数最小的点。 解题过程 第一步：理解问题结构 目标函数f(x)是圆心在(2,1)的圆形等值线，约束定义了一个可行域： g₁是直线x₁+x₂=2以下的半平面 g₂是抛物线x₂≥x₁²以上的区域 g₃和g₄要求x₁,x₂非负 可行域是第一象限中在直线x₁+x₂=2以下、抛物线x₂≥x₁²以上的区域。 第二步：积极集法基本原理 积极集法用于求解只有不等式约束的优化问题，核心思想是： 猜测哪些约束在最优解处是积极的（等号成立） 将这些约束当作等式约束求解子问题 验证解是否确实最优 关键概念： 积极约束：在某个点处等号成立的约束 工作集：当前被认为是积极的约束集合 第三步：选择初始点并确定工作集 我们选择可行点x⁰=(0.5, 0.5) 计算约束值： g₁(0.5,0.5)=0.5+0.5-2=-1 <0（不积极） g₂(0.5,0.5)=0.25-0.5=-0.25 <0（不积极） g₃(0.5,0.5)=-0.5 <0（不积极） g₄(0.5,0.5)=-0.5 <0（不积极） 初始工作集W⁰为空集，因为所有约束都不积极。 第四步：求解第一个子问题（无约束优化） 工作集为空，相当于无约束优化： min f(x) = (x₁-2)² + (x₂-1)² 梯度∇f(x)=[ 2(x₁-2), 2(x₂-1) ] 令梯度为0得最优解：x₁=2, x₂=1 检查可行性：点(2,1)满足g₁=2+1-2=1>0，违反约束g₁ 因此需要将约束g₁加入工作集。 第五步：求解等式约束子问题 工作集W¹={g₁}，将g₁当作等式约束： min f(x) = (x₁-2)² + (x₂-1)² s.t. x₁+x₂-2=0 使用拉格朗日法：L(x,λ)=f(x)+λ(x₁+x₂-2) 最优性条件： ∂L/∂x₁=2(x₁-2)+λ=0 ∂L/∂x₂=2(x₂-1)+λ=0 x₁+x₂-2=0 解得：x₁=1.5, x₂=0.5, λ=1 第六步：检查拉格朗日乘子符号 对于不等式约束，在解处积极的约束需要满足λ≥0 这里λ=1>0，满足最优性条件。 第七步：验证所有约束 检查所有约束： g₁=1.5+0.5-2=0（积极） g₂=2.25-0.5=1.75>0（违反！） 点(1.5,0.5)违反约束g₂，需要将其加入工作集。 第八步：调整工作集并重新求解 工作集W²={g₁, g₂}，求解等式约束问题： min f(x) = (x₁-2)² + (x₂-1)² s.t. x₁+x₂-2=0, x₁²-x₂=0 从约束得：x₂=2-x₁, x₂=x₁² ∴ x₁²=2-x₁ ⇒ x₁²+x₁-2=0 解得x₁=1或x₁=-2（舍去负解） 对应x₂=1 点(1,1)处约束值： g₁=1+1-2=0（积极） g₂=1-1=0（积极） g₃=-1<0, g₄=-1 <0 第九步：计算拉格朗日乘子 建立拉格朗日函数：L=f(x)+λ₁(x₁+x₂-2)+λ₂(x₁²-x₂) KKT条件： ∂L/∂x₁=2(x₁-2)+λ₁+2λ₂x₁=0 ∂L/∂x₂=2(x₂-1)+λ₁-λ₂=0 代入x=(1,1)： 2(1-2)+λ₁+2λ₂=0 ⇒ -2+λ₁+2λ₂=0 2(1-1)+λ₁-λ₂=0 ⇒ λ₁-λ₂=0 解得：λ₁=λ₂=2/3>0 所有积极约束的乘子为正，满足最优性条件。 第十步：最终验证 点(1,1)处： 目标函数值f=(1-2)²+(1-1)²=1 所有约束满足：g₁=g₂=0, g₃=g₄ <0 积极约束的拉格朗日乘子均为正 因此x* =(1,1)是全局最优解，最优值为1。 方法总结 积极集法通过迭代调整工作集，将不等式约束问题转化为等式约束子问题求解。每次迭代验证解的最优性，并通过添加违反约束或删除负乘子约束来更新工作集，直到找到满足KKT条件的最优解。