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

关于最优性条件及二次规划
第1页，讲稿共28张，创作于星期二
最优性条件
二次规划
重 点：最优性条件，二次规划
难 点: 最优性条件及应用
基本要求：理解可行方向、下降方向、有效约束等概念关于最优性条件及二次规划
第1页，讲稿共28张，创作于星期二
最优性条件
二次规划
重 点：最优性条件，二次规划
难 点: 最优性条件及应用
基本要求：理解可行方向、下降方向、有效约束等概念，
掌握最优性条件，并会用其求解有约束极值问题，掌握
二次规划模型及求解方法，理解序列二次规划的原理和特点。
第7讲 最优性条件和二次规划
第2页，讲稿共28张，创作于星期二
一、基本概念
1 起作用（紧）约束
是(I)的可行解，若 则称 为
处的起作用（紧）约束。记 处起作用（紧）约束的下标集
2 可行方向
记
或
时有
称 为 处的可行方向
为（I）或（II）的可行域
定义:
最优性条件（）
p
第3页，讲稿共28张，创作于星期二
若 是 的任一可行方向，则有
3 下降方向
时有
称 为 处的下降方向
若 是 的任一下降方向，则有
若
既满足（1）式又满足（2）式则称 为 的下 降可行方向
定理1 为（I）的局部极小值点， 在 处可微，
在
处可微
在
处连续
则在 处不存在可行下降方向。即不存在向量
同时成立
判别条件
判别条件
定义:
第4页，讲稿共28张，创作于星期二
二、最优性条件
1、Gordan引理
设
为 个 维向量，不存在向量P 使得
成立
的充要条件是存在不全为零的非负数，使得
成立
第5页，讲稿共28张，创作于星期二
2、Fritze John定理
(3) 成立
1
(4)
(5)
(6)
第6页，讲稿共28张，创作于星期二
3　Kuhn-Tucker条件
设x*是非线性规划（I）的局部极小点
有一阶连续偏导
而且X*处的所有起作用约束梯度线性无关，
则存在数
使得
（7）
成立
第7页，讲稿共28张，创作于星期二
成立
（3）
（7）
并令
即得
第8页，讲稿共28张，创作于星期二
若x*是非线性规划(II)的局部极小点，
且x*点的所有起作用约束的梯度
和
线性无关。则存在向量
使得
（7）
其中
称为广义拉格朗日(Lagrange)乘子。
第9页，讲稿共28张，创作于星期二
库恩—塔克条件是确定某点为最优点的必要条件，只要是最优点．且此处起作用约束的梯度线性无关。就必须满足这个条件。但一般说来它并不是充分条件，因而，满足这个条件的点不一定就是最优点。
对于凸规划，库恩—塔克条件不但是最优点存在的必要条件，它同时也是充分条件。
第10页，讲稿共28张，创作于星期二
某非线性规划的可行解X(k)，假定此处有两个起作用约束，
若X（k）是极小点，则
必处于
的夹角之间，
否则，X（k）点处必存在可行
下降方向，它就不会是极小点。
如右图所示。
库恩—塔克条件的几何解释：
且其梯度线性无关。
第11页，讲稿共28张，创作于星期二
三 举例
例１求
的极大值点。并验证其是否为K-T点。说明理由。
解：
1
如上图所示，阴影部分为可行域R，红色直线为目标函数的等值线。显然最大值点为（1，0）。
R
将原问题标准化
x1
x2
0
第12页，讲稿共28张，创作于星期二
K-T条件
第13页，讲稿共28张，创作于星期二
（1）
（2）
（3）
（5）
（4）
（1）式为
代入上式，得：
故
不是K-T点。
第14页，讲稿共28张，创作于星期二
的起作用约束为
线性相关
不是K-T点。
自己验证
是F-J点。
第15页，讲稿共28张，创作于星期二
例2 用K-T条件，求解非线性规划
解：1 验证该问题为凸规划
原问题标准化为
半正定，
负定
是凸函数
是凹函数
故该问题为凸规划。
所以
第16页，讲稿共28张，创作于星期二
2 求K-T点
该问题的K-T条件为
（1）
（2）
（