KT条件非线性求极值.ppt

第六章 约束最优化方法 第六章约束最优化方法 问题minf x s t g x 0分量形式略h x 0约束集S x g x 0 h x 0 6 1Kuhn Tucker条件一 等式约束性问题的最优性条件 考虑minf x s t h x 0回顾高等数学中所学的条件极值 问题求z f x y 极值minf x y 在 x y 0的条件下 S t x y 0引入Lagrange乘子 Lagrange函数L x y f x y x y 第六章6 1Kuhn Tucker条件 一 等式约束性问题的最优性条件 续 若 x y 是条件极值 则存在 使fx x y x x y 0fy x y y x y 0 x y 0推广到多元情况 可得到对于 fh 的情况 minf x s t hj x 0j 1 2 l若x 是 fh 的l opt 则存在 Rl使矩阵形式 一 等式约束性问题的最优性条件 续 几何意义是明显的 考虑一个约束的情况 最优性条件即 第六章6 1Kuhn Tucker条件 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 考虑问题minf x s t gi x 0i 1 2 m设x S x gi x 0i 1 2 m 令I i gi x 0i 1 2 m 称I为x 点处的起作用集 紧约束集 如果x 是l opt 对每一个约束函数来说 只有当它是起作用约束时 才产生影响 如 g2 x 0 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 特别有如下特征 如图在x f x u g x 0u 0要使函数值下降 必须使g x 值变大 则在 点使f x 下降的方向 f 方向 指向约束集合内部 因此 不是l opt g 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 定理 最优性必要条件 K T条件 问题 fg 设S x gi x 0 x S I为x 点处的起作用集 设f gi x i I在x 点可微 gi x iI在x 点连续 向量组 gi x i I 线性无关 如果x l opt 那么 u i 0 i I使 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 用K T条件求解 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 可能的K T点出现在下列情况 两约束曲线的交点 g1与g2 g1与g3 g1与g4 g2与g3 g2与g4 g3与g4 目标函数与一条曲线相交的情况 g1 g2 g3 g4对每一个情况求得满足 1 6 的点 x1 x2 T及乘子u1 u2 u3 u4 验证当满足可得 且ui 0时 即为一个K T点 下面举几个情况 g1与g2交点 x 2 1 T S I 1 2 则u3 u4 0解 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 第六章6 1Kuhn Tucker条件 二 不等式约束问题的Khun Tucker条件 续 第六章6 1Kuhn Tucker条件 三 一般约束问题的Kuhn Tucker条件 第六章6 1Kuhn Tucker条件 三 一般约束问题的Kuhn Tucker条件 续 第六章6 2既约梯度法 一 解线性约束问题的既约梯度法 第六章6 2既约梯度法 一 解线性约束问题的既约梯度法 续 第六章6 2既约梯度法 一 解线性约束问题的既约梯度法 续 第六章6 2既约梯度法 一 解线性约束问题的既约梯度法 续 第六章6 2既约梯度法 一 解线性约束问题的既约梯度法 续 第六章6 2解线性约束问题的既约梯度法 续 第六章6 2既约梯度法 一 解线性约束问题的既约梯度法 续 第六章6 2既约梯度法 算法 x 1 S k 1 k k 1 Jk j xj为x k 中最大m个正分量之一 B aj j Jk N aj j Jk YNT NfT x k BfT x k B 1NdB B 1NdN 解得x k 1 x k kd d 0 Y N Stop x k K T点 第六章6 2既约梯度法 一 解线性约束问题的既约梯度法 续 第六章6 2既约梯度法 二 广义既约梯度法 续 第六章6 2既约梯度法 二 广义既约梯度法 续 第六章6 3罚函数法 第六章6 3罚函数法1 罚函数概念 续 第六章6 3罚函数法1 罚函数概念 续 图示 第六章6 3罚函数法 2 罚函数法 fgh 第六章6 3罚函数法 2 罚函数法 续 第六章6 3罚函数法2 罚函数法 续 算法 第六章6 3罚函数法 3 闸函数法 内点罚函数法 第六章6 3罚函数法 3 闸函数法 续 第六章6 3罚函数法 3 闸函数法 续 第六章6 3罚函数法 3 闸函数法 续 第六章6 3罚函数法3 闸函数法 续 算法 第六章6 3罚函数法3 闸函数法 续 第六章6 3罚函数法 4 罚函数法与闸函数法的缺点 1 当罚函数法 闸函数法 的 0 时 惩罚项 0或0 形式 在计算上有困难 2 计算一系列无约束问题 故计算量大 5 乘子法 第六章6 3罚函数法 5 乘子法 续 第六章6 3罚函数法5 乘子法 续