最优性条件及二次规划课件.ppt

关于最优性条件及二次规划
第一页，本课件共有28页
最优性条件
二次规划
重 点：最优性条件，二次规划
难 点: 最优性条件及应用
基本要求：理解可行方向、下降方向、有效约束等概念，
掌握最优性条件，并会用其求解有约束极值问题，掌握
二次规划模型及求解方法，理解序列二次规划的原理和特点。
第7讲 最优性条件和二次规划
第二页，本课件共有28页
一、基本概念
1 起作用（紧）约束
是(I)的可行解，若 则称 为
处的起作用（紧）约束。记 处起作用（紧）约束的下标集
2 可行方向
记
或
时有
称 为 处的可行方向
为（I）或（II）的可行域
定义:
最优性条件（）
p
第三页，本课件共有28页
若 是 的任一可行方向，则有
3 下降方向
时有
称 为 处的下降方向
若 是 的任一下降方向，则有
若
既满足（1）式又满足（2）式则称 为 的下 降可行方向
定理1 为（I）的局部极小值点， 在 处可微，
在
处可微
在
处连续
则在 处不存在可行下降方向。即不存在向量
同时成立
判别条件
判别条件
定义:
第四页，本课件共有28页
二、最优性条件
1、Gordan引理
设
为 个 维向量，不存在向量P 使得
成立
的充要条件是存在不全为零的非负数，使得
成立
第五页，本课件共有28页
2、Fritze John定理
(3) 成立
1
(4)
(5)
(6)
第六页，本课件共有28页
3　Kuhn-Tucker条件
设x*是非线性规划（I）的局部极小点
有一阶连续偏导
而且X*处的所有起作用约束梯度线性无关，
则存在数
使得
（7）
成立
第七页，本课件共有28页
成立
（3）
（7）
并令
即得
第八页，本课件共有28页
若x*是非线性规划(II)的局部极小点，
且x*点的所有起作用约束的梯度
和
线性无关。则存在向量
使得
（7）
其中
称为广义拉格朗日(Lagrange)乘子。
第九页，本课件共有28页
库恩—塔克条件是确定某点为最优点的必要条件，只要是最优点．且此处起作用约束的梯度线性无关。就必须满足这个条件。但一般说来它并不是充分条件，因而，满足这个条件的点不一定就是最优点。
对于凸规划，库恩—塔克条件不但是最优点存在的必要条件，它同时也是充分条件。
第十页，本课件共有28页