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

1最优性条件,第八章有约束极值问题,一、基本概念,1起作用约束,是(I)的可行解，若则称为处的起作用约束。记处起作用约束的下标集,2可行方向,记,或,时有,称为处的可行方向,为（I）或（II）的可行域,若是的任一可行方向，则有,3下降方向,时有,称为处的下降方向,若是的任一下降方向，则有,若,既满足（1）式又满足（2）式则称为的下降可行方向,定理1为（I）的局部极小值点，在处可微，,在,处可微,在,处连续,则在处不存在可行下降方向。即不存在向量,同时成立,二、最优性条件,1、Gordan引理,设,为个维向量，不存在向量P使得,成立,的充要条件是存在不全为零的非负数，使得,成立,2、FritzeJohn定理,(I),(3),1,(4),(5),(6),该定理给出了非线性规划,的(局部)最优点应满足的必要条件。,该条件称为,FritzJohn条件，满足这个条件的点称为FritzJohn点。,3Kuhn-Tucker条件,设x*是非线性规划（I）的局部极小点,有一阶连续偏导,而且X*处的所有起作用约束梯度线性无关，,则存在数,使得,（6）,成立,成立,（3）,（3）,中各式的两边，,（6）,若x*是非线性规划(II)的局部极小点，,且x*点的所有起作用约束的梯度,和,线性无关。则存在向量,使得,（7）,其中,称为广义拉格朗日(Lagrange)乘子。,库恩塔克条件是确定某点为最优点的必要条件，只要是最优点且此处起作用约束的梯度线性无关。就必须满足这个条件。但一般说来它并不是充分条件，因而，满足这个条件的点不一定就是最优点。可是，对于凸规划，库恩塔克条件不但是最优点存在的必要条件，它同时也是充分条件。,某非线性规划的可行解x*，假定此处有两个起作用约束，,若x（k）是极小点，则,必处于,的夹角之间,不然，x（k）点处必存在可行下降方向，它就不会是极小点。,举例：,例求,的极大值点。并验证其是否为K-T点。说明理由。,解：,1,如上图所示，阴影部分为可行域R，红色直线为目标函数的等值线。显然最大值点为（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线性规划的Wolfe对偶问题,Wolfe对偶问题,2二次规划,1二次规划模型（目标函数第二项为正定二次型）,K-T条件中第一个条件为,约束条件化为等式故,K-T条件中第二个条件为,显然。（2）-（4）的解即为二次规划的解。为了求解（2）-（4），在（2）式中引入人工变量将其转化为线性规划问题。,在求解上述线性规划时，要求,至少有一个为零。,当（*）的最优解中时，其中即为二次规划（1）的最优解。,例1求解二次规划,解：将上述二次规划改写为,可知目标函数为严格凸函数。,或,且,3可行方向法,可行方向法可看作无约束下降算法的自然推广，其典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点算法的主要步骤是选择搜索方向和确定沿此方向移动的步长搜索方向的选择方式不同就形成各种可行方向法下面给出Zoutendijk可行方向法.,设,点的起作用约束集非空，为求,点,的可行下降方向D，D应满足下述不等式：,解线性规划问题（2）得最优解,若,则,即为F-J点。,若,则,即为可行下降方向。,以该可行下降方向进行一维搜索迭代出新点。,1罚函数法（外点法）考虑约束问题,其中,En是上的连续函数。,利用目标函数和约束函数组成辅助函数，称为罚函数P（X）。,为罚因子。随着罚因子的增加，P（X）的最优,解越靠近可行域，最终趋于所求非线性规划的最优解,4制约函数法,在实际中，罚因子的选择为一个趋向无穷大的严格递增正数列，从非可行点出发，逐个求解,得到一个极小点的序列，在一定条件下，这个序列将收敛于原约束问题的最优解。,这种通过一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法，简称SUMT方法。（SequentialUnconstrainedMinimizationTechnique),例题：求解非线性规划,解：构造法函数,解析法求解,取不满足约束条件的点,则（*）式变为,取不满足约束条件的点,则（*）式变为,无法求出,由此可看出罚函数法的缺陷。,2障碍函数法（内点法）,考虑约束问题,利用目标函数和约束函数组成辅助函数，称为障碍函数P（X）。,对于障碍因子，选择为一个趋向无穷大的严格减小趋于零的数列,从可行点出发，逐个求解,（1）或（2）。,3乘子法,（1)等式约束情形考虑问题,为二阶连续可导。,设乘子罚函数：,为罚因子。,（2)不等式约束情形考虑问题,由（1）上述问题转化为,整理后消去yj得：,（3)不等式和等式约束情形考虑问题,