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

《最优性条件及二次规划讲稿.ppt》由会员分享，可在线阅读，更多相关《最优性条件及二次规划讲稿.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于最优性条件及二次规划第一页，讲稿共二十八页哦最优性条件最优性条件二次规划二次规划重重 点：最优性条件，二次规划点：最优性条件，二次规划难难 点点:最优性条件及应用最优性条件及应用基本要求：理解可行方向、下降方向、有效约束等概念，基本要求：理解可行方向、下降方向、有效约束等概念，掌握最优性条件，并会用其求解有约束极值问题，掌握掌握最优性条件，并会用其求解有约束极值问题，掌握二次规划模型及求解方法，理解序列二次规划的原理和特点。二次规划模型及求解方法，理解序列二次规划的原理和特点。第第7讲讲 最优性条件和二次规划最优性条件和二次规划 第二页，讲稿共二十八页哦一、基本概念一、基本概念1 起作用（

2、紧）约束起作用（紧）约束 是(I)的可行解，若 则称 为 处的起作用（紧）约束。记 处起作用（紧）约束的下标集2 可行方向可行方向记或时有称 为 处的可行方向为（I）或（II）的可行域定义定义:最优性条件（最优性条件（5.1）p第三页，讲稿共二十八页哦若 是 的任一可行方向，则有3 下降方向下降方向时有称 为 处的下降方向若 是 的任一下降方向，则有若既满足（1）式又满足（2）式则称 为 的下 降可行方向 定理1 为（I）的局部极小值点，在 处可微，在处可微在处连续则在 处不存在可行下降方向。即不存在向量同时成立判别条件判别条件判别条件判别条件定义定义:第四页，讲稿共二十八页哦二、最优性条件二

3、、最优性条件1、Gordan引理引理设为 个 维向量，不存在向量P 使得成立的充要条件是存在不全为零的非负数，使得成立第五页，讲稿共二十八页哦2、Fritze John定理定理(3)成立1(4)(5)(6)第六页，讲稿共二十八页哦3Kuhn-Tucker条件条件 设x*是非线性规划（I）的局部极小点有一阶连续偏导而且X*处的所有起作用约束梯度约束梯度线性无关，则存在数使得（7）成立第七页，讲稿共二十八页哦成立（3）（7）并令并令即得即得第八页，讲稿共二十八页哦 若x*是非线性规划(II)的局部极小点，且x*点的所有起作用约束的梯度和线性无关。则存在向量使得（7）其中称为广义拉格朗日(Lagra

4、nge)乘子。第九页，讲稿共二十八页哦库恩塔克条件是确定某点为最优点的必要条件，只要是最优点且此处起作用约束的梯度线性无关。就必须满足这个条件。但一般说来它并不是充分条件，因而，满足这个条件的点不一定就是最优点。对于凸规划，库恩塔克条件不但是最优点存在的必要条件，它同时也是充分条件。第十页，讲稿共二十八页哦某非线性规划的可行解X(k)，假定此处有两个起作用约束，若X（k）是极小点，则必处于的夹角之间，否则，X（k）点处必存在可行下降方向，它就不会是极小点。如右图所示。库恩库恩塔克条件的几何解释：塔克条件的几何解释：且其梯度线性无关。第十一页，讲稿共二十八页哦三三 举例举例例求例求的极大值点。并

5、的极大值点。并验证其是否为验证其是否为K-T点。说明理由。点。说明理由。解：解：1如上图所示，阴影部分为可行域如上图所示，阴影部分为可行域R，红，红色直线为目标函数的等值线。显然最色直线为目标函数的等值线。显然最大值点为（大值点为（1，0）。）。R将原问题标准化将原问题标准化x1x20第十二页，讲稿共二十八页哦K-T条件第十三页，讲稿共二十八页哦（1）（2）（3）（5）（4）（1）式为代入上式，得：故不是K-T点。第十四页，讲稿共二十八页哦的起作用约束为线性相关不是K-T点。自己验证是F-J点。第十五页，讲稿共二十八页哦例例2 用用K-T条件，求解非线性规划条件，求解非线性规划解：解：1 验证

6、该问题为凸规划验证该问题为凸规划原问题标准化为原问题标准化为半正定，负定是凸函数是凹函数故该问题为凸规划。所以第十六页，讲稿共二十八页哦2 求求K-T点点该问题的该问题的K-T条件为条件为（1）（2）（3）（4）是K-T点(i)(ii)（5）讨论讨论第十七页，讲稿共二十八页哦(iii)将求出的 带入（6）式都不满足故该问题有唯一的K-T点 即为极小值点，(iv)第十八页，讲稿共二十八页哦二次规划的数学模型可表示为：二次规划的数学模型变形为：（I）（II）二次规划二次规划(5.2)第十九页，讲稿共二十八页哦其中：其中：书中书中 为行向量为行向量第二十页，讲稿共二十八页哦（III）第二十一页，讲稿

7、共二十八页哦例例1 求解二次规划问题（例5-3）解：解：写出问题对应的矩阵形式如下：这就形成了式（III）所需要的全部信息：（III）第二十二页，讲稿共二十八页哦为解此方程组，在第为解此方程组，在第1个方程和第个方程和第2个方程中引入人工变量个方程中引入人工变量R1 和和R2，目标函数为目标函数为max z=-R1-R2，对应的初始单纯形表见表对应的初始单纯形表见表5-1。第二十三页，讲稿共二十八页哦第二十四页，讲稿共二十八页哦第二十五页，讲稿共二十八页哦例例2 求解二次规划求解二次规划（自己练习）第二十六页，讲稿共二十八页哦序列二次规划序列二次规划(5.3)序列二次规划的思路序列二次规划（SQP）算法是将复杂的有约束极值问题转化为比较简单的二次规划（QP）问题求解的算法。利用泰勒展开把有约束极值问题的目标函数 在迭代点 展开成二次函数，将约束条件在迭代点 展开成线性函数得到如下二次规划问题：此问题是原有约束极值问题的近似问题，但其解不一定是可行解。为此，将上述二次规划问题变成变量 的问题，即（IV)第二十七页，讲稿共二十八页哦感感谢谢大大家家观观看看第二十八页，讲稿共二十八页哦