非线性规划基础课件.ppt

《非线性规划基础课件.ppt》由会员分享，可在线阅读，更多相关《非线性规划基础课件.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非线性规划基础第1页，此课件共36页哦第一节第一节 非线性规划的基本概念非线性规划的基本概念一、非线性规划模型二、非线性规划的几何求解第2页，此课件共36页哦一、一、非线性规划模型非线性规划的一般形式：非线性规划的一般形式：称为决策变量称为不等式约束称为等式约束可行域称为目标函数第3页，此课件共36页哦1 1、局部解、局部解 局部极大值局部极大值 局部极小值局部极小值2 2、全局解、全局解 全局最大值全局最大值 全局最小值全局最小值 局部最优解局部最优解全局最优解全局最优解 线性规划问题的最优解在角点取到，对非线性规划问题，最优解在何处取到呢？第4页，此课件共36页哦二、非线性规划的几何求解二

2、、非线性规划的几何求解例例13.1 13.1 求解下列非线性规划的最优解。求解下列非线性规划的最优解。作图求解作图求解第5页，此课件共36页哦例例13.2 求解下列非线性规划的最优解。求解下列非线性规划的最优解。作图求解作图求解第6页，此课件共36页哦例例13.3 求解下列非线性规划的最优解。求解下列非线性规划的最优解。作图求解作图求解第7页，此课件共36页哦线性规划与非线性规划有很大的区别：如果线性规线性规划与非线性规划有很大的区别：如果线性规划的最优解存在，其最优解只能在可行域的边界达划的最优解存在，其最优解只能在可行域的边界达到。而非线性规划的最优解（如果最优解存在）则到。而非线性规划的

3、最优解（如果最优解存在）则可能在可行域的任何一点达到。可能在可行域的任何一点达到。第8页，此课件共36页哦第二节第二节 凸函数凸函数 一、凸函数的基本概念一、凸函数的基本概念二、凸函数的判断二、凸函数的判断三、凸规划三、凸规划第9页，此课件共36页哦凸函数定义凸函数定义凹函数定义凹函数定义一、凸函数的基本概念一、凸函数的基本概念凸函数凹函数非凸非凹函数第10页，此课件共36页哦凸函数具有如下性质凸函数具有如下性质 第11页，此课件共36页哦二、凸函数的判断二、凸函数的判断 一元函数凸性的判断一元函数凸性的判断第12页，此课件共36页哦多元函数凸性的判断多元函数凸性的判断 梯度：梯度：Hessi

4、an矩阵矩阵：第13页，此课件共36页哦f(x)=x13+3x1x2+x22，则，则 f(x)的的Hessian矩阵为矩阵为：判定正定的方法：当一个判定正定的方法：当一个nn矩阵矩阵A的任意的任意k阶顺序主子式阶顺序主子式大于大于0时，则该矩阵为正定的。时，则该矩阵为正定的。第14页，此课件共36页哦D为凸集合，为凸集合，f(x)是定义在上的二次可微函数，则是定义在上的二次可微函数，则f(x)为为凸函数的充要条件为凸函数的充要条件为f(x)在任意一点的在任意一点的Hessian矩阵矩阵为半正定。为半正定。则则f(x)为凸函数的充要条件为：为凸函数的充要条件为：第15页，此课件共36页哦例例13

5、.4 判别下列函数的凸凹性判别下列函数的凸凹性 解：解：1 1）1）2）H(x1,x2)的两个的两个顺顺序主子式分序主子式分别别H1(x1,x2)=4和和H2(x1,x2)=8-4=4均大均大于于0。所以所以 f(x)为凸函数为凸函数。2 2）H(x1,x2)的两个的两个顺顺序主子式分序主子式分别别H1(x1,x2)=20和和H2(x1,x2)=-40。所以所以 f(x)不是凸函数。不是凸函数。第16页，此课件共36页哦三、凸规划三、凸规划当当f(x),g(x)为凸函数，为凸函数，h(x)=(h1(x),hl(x)是线性函数是线性函数时，上述规划问题称为凸规划问题。时，上述规划问题称为凸规划问

6、题。凸规划的求解可借助下节的凸规划的求解可借助下节的KKT定理。定理。h(x)=(h1(x),hl(x)=0第17页，此课件共36页哦第三节第三节 最优性条件最优性条件一、无约束优化的最优性条件一、无约束优化的最优性条件二、约束极值问题的最优性条件二、约束极值问题的最优性条件第18页，此课件共36页哦引入两个概念引入两个概念 下降方向：下降方向：可行方向：可行方向：则称d为f(x)在点的下降方向。则称d为D在 点的可行方向。定理13.6 若f(x)在点 可微，如果存在方向d，使 ，则 使 有第19页，此课件共36页哦一、无约束优化的最优性条件一、无约束优化的最优性条件在无约束规划问题中，由于不

7、涉及到可行域的问题，在无约束规划问题中，由于不涉及到可行域的问题，因此，只涉及下降方向。不涉及可行方向的问题。因此，只涉及下降方向。不涉及可行方向的问题。第20页，此课件共36页哦定理定理13.713.7（一（一阶阶必要条件）必要条件）若f(x)在点 可微，且为无约束优化问题（13.4）的局部最优解，则 。定理定理13.813.8（二（二阶阶必要条件）必要条件）若f(x)在点 二阶连续可微，且点为无约束优化问题（13.4）的局部最优解。则 且 半正定。定理定理13.913.9（二（二阶阶充分条件）充分条件）设 满足 且 正定，则 点为无约束优化问题（13.4）的局部最优解。定理定理13.101

8、3.10 若目标函数f(x)是Rn上的连续可微凸函数，则 的充分必要条件 为无约束优化问题（13.4）的全局最优点和局部最优点。第21页，此课件共36页哦例例13.5 求函数求函数f(x)的最优值点，即。的最优值点，即。正定解：所以 为局部最小值点。第22页，此课件共36页哦二、约束极值问题的最优性条件二、约束极值问题的最优性条件 在在x点取到局部最优值的条件为：点取到局部最优值的条件为：无解无解约束规划问题不仅涉及到目标函数，约束规划问题不仅涉及到目标函数，还涉及到可行域。还涉及到可行域。因此既要考虑下降方向，还要因此既要考虑下降方向，还要考虑可行方向考虑可行方向第23页，此课件共36页哦定

9、理定理13.11（Gorden）：）：设设 ，则，则Ax0有解的充分必有解的充分必要条件为：不存在非零向量要条件为：不存在非零向量 ，使得，使得 。无解的充分必要条件为：存在不全为零的非负实数使 上述定理的几何意义为：上述定理的几何意义为：dA1A2A3A3A1A2Ad0Ad0有解有解 Ad0无解无解 第24页，此课件共36页哦定理（定理（Fritz-John）：问题（）：问题（13.5）在点取到局部极小值，）在点取到局部极小值，则存在不全为零的非负实数使则存在不全为零的非负实数使 例例13.6：是下列优化问题的最优解，验证是下列优化问题的最优解，验证x满足满足Fritz-John定理。定理。

10、第25页，此课件共36页哦紧紧指指标标集集 I=1,2 如如(w0,w1,w2)=(1,1,2)。因此，因此，x满满足足Fritz-John定理。定理。第26页，此课件共36页哦例例13.7 (0,2)T是下列是下列优优化化问题问题的最的最优优解，解，验证验证 x 满满足足Fritz-John定理定理(w0,w1,w2)=(0,k,2k)，w0=0 因此，因此，x满满足足Fritz-John定理。定理。第27页，此课件共36页哦 约束规格约束规格：线性无关线性无关 定理（定理（KKT）：）：设设 是问题（是问题（13.513.5）局部最优解，）局部最优解，在在 处可微，处可微，在在 处连续，且

11、处连续，且 线性线性无关，则存在不全为零的非负实数无关，则存在不全为零的非负实数 使使第28页，此课件共36页哦例例13.8 求下列问题的求下列问题的KKT点。点。KKT点：点：第29页，此课件共36页哦定理定理13.14.在在问题问题（13.5）中，）中，f,gi(i=1,m)是凸函数，是凸函数，在在 处处可微，可微，在在 处连续处连续，且在，且在 处处KKT条件成立，条件成立，则则 是是问题问题（13.5）全局最）全局最优优解。解。第30页，此课件共36页哦 第四节第四节 非线性规划问题的算法非线性规划问题的算法一、一、一维搜索法一维搜索法二、二、最速下降法最速下降法第31页，此课件共36

12、页哦 min f(x)f:RnR 是一阶连续函数是一阶连续函数无约束优化问题的极值条件无约束优化问题的极值条件基本迭代格式基本迭代格式寻找搜索方向是无约束优化的关键问题寻找搜索方向是无约束优化的关键问题第32页，此课件共36页哦一、一维搜索法一、一维搜索法一一维维搜搜索索法法是是求求解解无无约约束束优优化化的的一一种种方方法法。它它是是沿沿射射线线 xk+1=xk+tdk，求求 f(x)在在该该射射线线上上的的极极小小值值，这这一一问题问题可可转转化化为为求一元函数求一元函数的极小的极小值值，即，即因此，因此，这这一一过过程称程称为为一一维维搜索法。搜索法。第33页，此课件共36页哦通常，无通

13、常，无约约束束优优化化问题问题算法的一般形式算法的一般形式为为：初始步：初始步：给给定初始点定初始点 ，令，令k=0。第第1步：如果步：如果 ，停止，停止计计算；否算；否则则，进进入下一步。入下一步。第第2步：步：计计算下降方向算下降方向dk，使，使 。第第3步：步：计计算步算步长长tk，使得，使得 ，令，令 ；k=k+1，转转第第1步。步。第34页，此课件共36页哦一维搜索的方法很多，归纳起来，可分为试探法和一维搜索的方法很多，归纳起来，可分为试探法和函数逼近法。试探法中包括如黄金分割法、函数逼近法。试探法中包括如黄金分割法、Fibonacci法等；函数逼近法中包括如牛顿法、割线法等法等；函数逼近法中包括如牛顿法、割线法等。第35页，此课件共36页哦牛牛顿顿算法算法计计算步算步骤骤如下：如下：初始步：初始步：给给定初始点定初始点 ，令，令k=0=0。第第1 1步步：如如果果 ，则则停停止止计计算算，得得到到点点xk。否否则则，转转第第2 2步。步。第第2 2步：步：计计算点算点 xk+1：令令k=k+1，转转第第1 1步。步。该该算算法法特特点点是是：收收敛敛速速度度快快，为为二二阶阶收收敛敛。初初始始点点要要选选在在最最优优解解附附近近。但但有有时时初初始始点点的的选选取取困困难难，甚甚至至无无法法实实施。施。第36页，此课件共36页哦