有约束极值问题ppt课件.ppt

《有约束极值问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1最优性条件第八章有约束极值问题一、基本概念1起作用约束是(I)的可行解，若则称为处的起作用约束。记处起作用约束的下标集2可行方向记或时有称为处的可行方向为（I）或（II）的可行域若是的任一可行方向，则有3下降方向时有称为处的下降方向若是的任一下降方向，则有若既满足（1）式又满足（2）式则称为的下降可行方向定理1为（I）的局部极小值点，在处可微，在处可微在处连续则在处不存在可行下降方向。即不存在向量同时成立二、最优性条件1、Gordan引理设为个维向量，不存在向量P使得成立的充要条件是存在不全为零的非负数，使得成立2

2、、FritzeJohn定理(I)(3)1(4)(5)(6)该定理给出了非线性规划的(局部)最优点应满足的必要条件。该条件称为FritzJohn条件，满足这个条件的点称为FritzJohn点。3Kuhn-Tucker条件设x*是非线性规划（I）的局部极小点有一阶连续偏导而且X*处的所有起作用约束梯度线性无关，则存在数使得（6）成立成立（3）（3）中各式的两边，（6）若x*是非线性规划(II)的局部极小点，且x*点的所有起作用约束的梯度和线性无关。则存在向量使得（7）其中称为广义拉格朗日(Lagrange)乘子。库恩—塔克

3、条件是确定某点为最优点的必要条件，只要是最优点．且此处起作用约束的梯度线性无关。就必须满足这个条件。但一般说来它并不是充分条件，因而，满足这个条件的点不一定就是最优点。可是，对于凸规划，库恩—塔克条件不但是最优点存在的必要条件，它同时也是充分条件。某非线性规划的可行解x*，假定此处有两个起作用约束，若x（k）是极小点，则必处于的夹角之间不然，x（k）点处必存在可行下降方向，它就不会是极小点。举例：例１求的极大值点。并验证其是否为K-T点。说明理由。解：1如上图所示，阴影部分为可行域R，红色直线为目标函数的等值线。显然最

4、大值点为（1，0）。R将原问题标准化K-T条件（1）（2）（3）（5）（4）（1）式为代入上式，得：故不是K-T点。的起作用约束为线性相关不是K-T点。自己验证是F-J点。例2用K-T条件，求解非线性规划解：1验证该问题为凸规划原问题标准化为半正定，负定是凸函数是凹函数故该问题为凸规划。所以2求K-T点该问题的K-T条件为（1）（2）（3）（4）是K-T点(i)(ii)（5）(iii)将求出的带入（6）式都不满足故该问题有唯一的K-T点即为极小值点，三、Wolfe对偶问题1定义令设或为凸规划或则Wolfe对偶问题为：2

5、线性规划的Wolfe对偶问题Wolfe对偶问题§2二次规划1二次规划模型（目标函数第二项为正定二次型）K-T条件中第一个条件为约束条件化为等式故K-T条件中第二个条件为显然。（2）-（4）的解即为二次规划的解。为了求解（2）-（4），在（2）式中引入人工变量将其转化为线性规划问题。在求解上述线性规划时，要求至少有一个为零。当（*）的最优解中时，其中即为二次规划（1）的最优解。例1求解二次规划解：将上述二次规划改写为可知目标函数为严格凸函数。或且§3可行方向法可行方向法可看作无约束下降算法的自然推广，其典型策略是从可行点

6、出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点．算法的主要步骤是选择搜索方向和确定沿此方向移动的步长．搜索方向的选择方式不同就形成各种可行方向法．下面给出Zoutendijk可行方向法.设点的起作用约束集非空，为求点的可行下降方向D，D应满足下述不等式：解线性规划问题（2）得最优解若则即为F-J点。若则即为可行下降方向。以该可行下降方向进行一维搜索迭代出新点。1罚函数法（外点法）考虑约束问题其中En是上的连续函数。利用目标函数和约束函数组成辅助函数，称为罚函数P（X）。为罚因子。随着罚因子的增加，P

7、（X）的最优解越靠近可行域，最终趋于所求非线性规划的最优解§4制约函数法在实际中，罚因子的选择为一个趋向无穷大的严格递增正数列，从非可行点出发，逐个求解得到一个极小点的序列，在一定条件下，这个序列将收敛于原约束问题的最优解。这种通过一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法，简称SUMT方法。（SequentialUnconstrainedMinimizationTechnique)例题：求解非线性规划解：构造法函数解析法求解取不满足约束条件的点则（*）式变为取不满足约束条件的点则（*）式变为无

8、法求出由此可看出罚函数法的缺陷。2障碍函数法（内点法）考虑约束问题利用目标函数和约束函数组成辅助函数，称为障碍函数P（X）。对于障碍因子，选择为一个趋向无穷大的严格减小趋于零的数列从可行点出发，逐个求解（1）或（2）。3乘子法（1)等式约束情形考虑问题为二阶连续可导。设乘子罚函数：为罚因子。（2)不等式约束情形考虑问题由（1）上述