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

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