管理科学理论-.ppt

第四章 约束非线性优化的理论与方法 一，等式约束问题 1，切向量与正规性 定义1 设x0 是由方程组gi(x)=0， i=1,2, …,m，确定的曲面 S上的一点，若在S上存在曲线x(t)，x(0)= x0，x’(0)=h， 则称向量是曲面S上点x0处的切向量。 定义2：如果关于h 的线性方程组： 系数矩阵 满秩，则称x0为曲面S上的一个正规点。 注1 是x0处法空间的一组基。 注2 方程组 的一组线性无关的解构成曲面S上x0处切空间的一组基。 2，具等式约束问题的极值必要条件 考虑二维问题： min f (x,y) S.t. g (x,y)=0 结论1:若在极小点(x0,y0)处,?g (x0,y0) ?0，则?f (x0,y0)与?g (x0,y0)线性相关，即?f (x0,y0) +? ?g (x0,y0)=0。 结论2：(Lagrange乘子规则)设(x0,y0)是局部极小点，且?g (x0,y0) ?0，则存在常数? ，对函数F (x0,y0)= f (x0,y0)+ ? g (x0,y0)，满足 ?F(x0,y0)= ?f (x0,y0) +? ?g (x0,y0)=0. 结论3（充分条件）：设点x0满足必要条件： ?F(x0)= ?f (x0) +? ?g (x0)=0. 若 则x0是局部极小点。 二，具不等式约束的问题 1，下降方向和可行方向 考虑一般非线性约束优化问题： 例：求解 1) 下降方向的选择 如果方向P在点x0处是下降方向，则P应与－?f (x0)同侧， 即： 记 为点x0处的下降方向集。 2) 可行方向的选择 在x0处的可行方向应满足: 结论1：若 所有方向P都是可行的。 结论2：若 当 时 则P为可行方向。 记 为可行方 向集。 注：对等式约束而言，所有约束都是起作用约束。 2，最优性条件 定义1：若对?x?C和???0，有? x?C ，则称C为锥，如果C是 凸的，则称其为凸锥。 定义2：设是约束集，称 为x0处的可行方向锥。 下面进一步讨论最优性条件。设x*是问题 的最优解，则x*处 换言之，在x*处满足 的方向P必有 称 为Fritz－John 条件。其中 线性无关。 在最优点x*处应满足 Farkas引理：给定向量a i（i =1,2,…,k）与b，不存在向量P同时满足条件 和 的充要条件是 向量b 在ai 所张成的凸锥内，即满足 定理1:设x*为问题 的一个可行点,并且前t个约束为起作用约束,则x*为最 优解的一个必要条件是下式成立: 例:考虑问题 从上例看出，满足定理1还需增加一些约束规范，如梯度向量线性无关等，上例有 更一般的有： 定理2（Kuhn－Tucker）最优性必要条件： 在最优点x*处，设 线性无关，则存在 满足： 称上式为K－T条件，满足上式的点称K－T点。 相应的广义Lagrange函数为： 例1：验证以下问题在最优解处K-T条件成立。 解: 例2: 解: 定理3 设x*是一个可行点，若存在使K-T条