《有约束极值问题》PPT课件.ppt

《《有约束极值问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《有约束极值问题》PPT课件.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、得：故不是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 线性规划的线性规划的Wolfe对偶问题对偶问题Wolfe对偶问题对偶问题2 二次规划1 二次规划模型（目标函数第二项为正定二次型）K-T 条件中第

5、一个条件为约束条件化为等式 故K-T 条件中第二个条件为显然。（2）-（4）的解即为二次规划的解。为了求解（2）-（4），在（2）式中引入人工变量将其转化为线性规划问题。在求解上述线性规划时，要求至少有一个为零。当（*）的最优解中 时，其中 即为二次规划（1）的最优解。例1求解二次规划解：将上述二次规划改写为可知目标函数为严格凸函数。或且3 可行方向法 可行方向法可看作无约束下降算法的自然推广，其典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点算法的主要步骤是选择搜索方向和确定沿此方向移动的步长搜索方向的选择方式不同就形成各种可行方向法下面给出Zoutend

6、ijk可行方向法.设点的起作用约束集非空，为求点的可行下降方向D，D应满足下述不等式：解线性规划问题（2）得最优解若则即为F-J点。若则即为可行下降方向。以该可行下降方向进行一维搜索迭代出新点。1 罚函数法（外点法）罚函数法（外点法）考虑约束问题其中En是上的连续函数。利用目标函数和约束函数组成辅助函数，称为罚函数P（X）。为罚因子。随着罚因子的增加，P（X）的最优解越靠近可行域，最终趋于所求非线性规划的最优解4 制约函数法在实际中，罚因子的选择为一个趋向无穷大的严格递增正数列 ，从非可行点出发，逐个求解得到一个极小点的序列 ，在一定条件下，这个序列将收敛于原约束问题的最优解。这种通过一系列无

7、约束问题来获得约束问题最优解的方法称为序列无约束极小化方法，简称SUMT方法。（Sequential Unconstrained Minimization Technique)例题：求解非线性规划解：构造法函数解析法求解取不满足约束条件的点则（*）式变为取不满足约束条件的点则（*）式变为无法求出由此可看出罚函数法的缺陷。2 障碍函数法（内点法）障碍函数法（内点法）考虑约束问题利用目标函数和约束函数组成辅助函数，称为障碍函数P（X）。对于障碍因子 ，选择为一个趋向无穷大的严格减小趋于零的数列从可行点出发，逐个求解（1）或（2）。3 乘子法乘子法（1)等式约束情形考虑问题为二阶连续可导。设乘子罚函数：为罚因子。（2)不等式约束情形考虑问题由（1）上述问题转化为整理后消去yj得：（3)不等式和等式约束情形考虑问题3 检查可行性若则转 4；否则，令直到为止。4 形成新的复形若比好，即则由代替组成新的复形；若比坏，即则令由（2）式重新 计算得直到再以 替代 组成新的复形。若则不进行，去掉后构成新的复形。返回2