非线性规划课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《非线性规划课件.ppt》由会员分享,可在线阅读,更多相关《非线性规划课件.ppt(84页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、非线性规划第1页,此课件共84页哦1 1 非线性规划基本概念非线性规划基本概念 解:设该学生买入馒头,肉丸子,青菜的数量分别为x1,x2,x3;个人的满意度函数即为效用函数为u(x1,x2,x3)=Ax1a1x2a2x3a3.于是数学模型为 例例7.7.1 1 某高校学生食堂用餐,拟购三种食品,馒头0.3元/个,肉丸子1元/个,青菜0.6/碗.该学生的一顿饭支出不能够超过5元.问如何花费达到最满意?显然,此模型即为非线性.第2页,此课件共84页哦例例7.2 一容器由圆锥面和圆柱面围成一容器由圆锥面和圆柱面围成.表面积为表面积为 ,圆锥部分高为,圆锥部分高为 ,和和圆柱部分高圆柱部分高 之比为之
2、比为 ,为圆柱底圆半径为圆柱底圆半径.求求 使面积最大使面积最大.解:解:由条件由条件 所以,数学模型为:所以,数学模型为:s.t.第3页,此课件共84页哦二、数学模型二、数学模型 称如下形式的数学模型为数学规划(Mathematical Programming 简称MP)n是维欧几里得空间Rn中的向量(点),f(x)称满足约束条件的向量x为(MP)问题的一个可行解,全体可行点组成的集合称为可行域.如果f(x),gi(x),hi(x)均为线性函数,就是前面所学的线性规划问题(LP).如果至少有一个为非线性函数称为非线性规划问题.由于等式约束hi(x)=0等价于下列两个不等式约束 所以(MP)问
3、题又可表示为 第4页,此课件共84页哦1、线性代数知识考虑二次型ZTAZ,Z为n维向量正定的二次型:若对于任意Z0,有ZTAZ0;半正定的二次型:若对于任意Z0,有ZTAZ0;负定的二次型:若对于任意Z0,有ZTAZ0,又存在Z0,有ZTAZf(xf(x)f(x*),),称点称点x x*是是f(x)f(x)的可行解集的可行解集K K上的上的严格整体极小点严格整体极小点.定义定义7.2(7.2(MP)MP)问题的一个可行点问题的一个可行点x x*被称为被称为局部极小点局部极小点,如果存在一个正数,如果存在一个正数使得对于使得对于所有满足关系式所有满足关系式x-xx-x*的可行点的可行点x x都有
4、都有 f(x)f(xf(x)f(x*)成立成立.如果对任意的可行如果对任意的可行点点xK,xxxK,xx*,存在一个正数存在一个正数使得对于所有满足关系式使得对于所有满足关系式x-xx-x*f(xf(x)f(x*)成立成立.则称则称x x*是是f(x)f(x)在在K K上的一个局部严格极小点上的一个局部严格极小点.显然整体极小点一定是局显然整体极小点一定是局部极小点,反之不然部极小点,反之不然.第7页,此课件共84页哦五、凸规划五、凸规划 定义定义7.3 集合集合 被称为被称为 中的一个中的一个凸集凸集,如果对于,如果对于 中任意两点中任意两点 和任一实数和任一实数 ,点点 .几何解释几何解释
5、:当一个集合是凸集时,连接此集合中任意两点的线段也一定包含在此集合内,:当一个集合是凸集时,连接此集合中任意两点的线段也一定包含在此集合内,规定空集规定空集 是凸集是凸集.定义定义7.4 凸函数凸函数:是凸集是凸集 上的实值函数,如果对于上的实值函数,如果对于 中任意两点中任意两点 和任意实数和任意实数 有不等式有不等式 成立成立.严格凸函数严格凸函数:是凸集是凸集 上的实值函数,如果对于上的实值函数,如果对于 中任意两点中任意两点 ,和任意实数,和任意实数 ,有不等式,有不等式 成立成立.第8页,此课件共84页哦定义定义7.5 是定义在凸集是定义在凸集 上的实值函数,如果上的实值函数,如果
6、是是 上凸函数,称上凸函数,称 是是凹函数凹函数.n定理定理7.1 设设 是凸集是凸集 上的凸函数,则上的凸函数,则 在在 中的任一局部极小点都是中的任一局部极小点都是它的整体极小点它的整体极小点.n证明:证明:设设 是一局部极小点而非整体极小点,则必存在可行点是一局部极小点而非整体极小点,则必存在可行点 (可行域可行域).对任一对任一 ,由于,由于 的凸性,有的凸性,有n n 当当 时,时,与与 充分接近,与充分接近,与 是局部极小矛盾是局部极小矛盾.证毕证毕.n定义定义7.6 设有设有(MP)问题问题 ,若可行域,若可行域 是凸集,是凸集,是是 上的上的凸函数,则称此规划问题为凸函数,则称
7、此规划问题为凸规划凸规划.n定理定理7.2 凸规划的任一局部极小解为整体极小解凸规划的任一局部极小解为整体极小解.第9页,此课件共84页哦六、非线性规划问题的求解方法六、非线性规划问题的求解方法迭代法迭代法考虑(MP)问题:一般来说,MP问题难以求得整体极小点,只能求得局部极小点.以后我们说求(MP)问题,指的是求局部极小点.n1、无约束极小化问题n (UMP)(7.6)n这里是 定义在 上的一个实值函数(7.5)第10页,此课件共84页哦定理定理7.3(一阶必要条件)如果(一阶必要条件)如果 是可微函数是可微函数.是上述无约束问题是上述无约束问题(UMP)的一个局部极小点或局部极大点的必要条
8、件是:)的一个局部极小点或局部极大点的必要条件是:.满足满足 的点称为平稳点或驻点的点称为平稳点或驻点.n定理定理7.4 设设 为定义在为定义在 上的二阶连续可微函数,如果上的二阶连续可微函数,如果 是是 的一个局部极小的一个局部极小点,必有点,必有n n 这里这里 表示表示 在在 处的处的Hesse矩阵矩阵.n证明:证明:,根据,根据 在点在点 处的展开式有处的展开式有n n 若若 ,当,当 充分小时,有充分小时,有n n 有有 .这和这和 是是 的极小矛盾的极小矛盾.第11页,此课件共84页哦定理定理7.5 设 是定义在 上的二阶连续可微函数,如果点 满足 ,而且存在 的一个邻域 ,则 是
9、 的一个局部极小点.n在高等数学中求解极值点方法先求出满足在高等数学中求解极值点方法先求出满足 的点及不可导点的点及不可导点.在这在这些点判断些点判断 是否取得极小值是否取得极小值.n2、等式约束的极小化问题、等式约束的极小化问题n考虑考虑 定义定义7.7 7.7 如果在点处线性无关,则称点 是此约束条件的一个正则点.Langrange乘子法:第12页,此课件共84页哦引进拉格朗日函数 其中 被称为拉格朗日乘子向量.n定理定理7.6 设设 是连续可微函数,是连续可微函数,是是 在可行集中的一在可行集中的一个局部极小点个局部极小点.在在 是正则点的假定下必存在一个拉格朗日乘子向量是正则点的假定下
10、必存在一个拉格朗日乘子向量 ,使,使 得满足方程组得满足方程组n对等式约束,用拉格朗日乘子法求解出平稳点,判断是否极值点对等式约束,用拉格朗日乘子法求解出平稳点,判断是否极值点.n用上述解析法求解无约束和等式约束极值问题的平稳点,再判断是否为极值点用上述解析法求解无约束和等式约束极值问题的平稳点,再判断是否为极值点.该方法有一该方法有一定的局限性:定的局限性:n (1)它们要求函数是连续的,可微的,实际问题中不一定满足这一条件;)它们要求函数是连续的,可微的,实际问题中不一定满足这一条件;n (2)上述求平稳点的方程组求解比较困难,有些解不出来;)上述求平稳点的方程组求解比较困难,有些解不出来
11、;n (3)实际问题中有大量的不等式约束)实际问题中有大量的不等式约束.n因此求解非线性规划应有更好的新方法因此求解非线性规划应有更好的新方法.实际应用中一般用迭代法来求解非线性规划问题,实际应用中一般用迭代法来求解非线性规划问题,即求近似最优解的方法即求近似最优解的方法.n 第13页,此课件共84页哦3 3、非线性规划问题的求解方法、非线性规划问题的求解方法迭代法迭代法迭代法一般过程为:在迭代法一般过程为:在(MP)(MP)问题的可行域问题的可行域 内选择初始点内选择初始点 ,确确定定某某一一方方向向 ,使使目目标标函函数数 从从 出出发发,沿沿 方方向向使使目目标标函函数数值值下下降降,即
12、即 ,有有 ,进进一一步步确确定定 ,使使 ,令令 .如如果果 已已满满足足某某终终止止条条件件,为为近近似似最最优优解解.否否则则,从从 出出发发找找一一个个方方向向 ,确确定定步步长长 ,使使 ,有有 .如如此此继继续续,将将得得到到点点列列 .显显然然有有 ,即即 点点列列 相相对对应应的的目目标标函函数数是是一一个个单单调调下下降降的的数数列列.当当 是是有有穷穷点点列列时时,希希望望最最后后一一个个点点是是(MP)(MP)问问题题的的某某种种意意义义下下的的最最优优解解.当当 为为无无穷穷点点列列时时,它它有有极极限限点点,其其极极限限点点是是(MP)(MP)的的某某种种意义下的最优
13、解(此时称该方法是收敛的)意义下的最优解(此时称该方法是收敛的).第14页,此课件共84页哦迭代法一般步骤:迭代法一般步骤:1.1.选取初始点选取初始点x x0 0,k:=0,k:=0 2.2.构造搜索方向构造搜索方向p pk k 3.3.根据根据p pk k方向确定方向确定k k 4.4.令令x xk+1k+1 x xk kk kp pk k 5.5.若若x xk+1k+1已满足某终止条件,停止迭代,输出近似最优解已满足某终止条件,停止迭代,输出近似最优解x xk+1k+1.否则令否则令k:=k+1,k:=k+1,转向第二步转向第二步.迭代法求解迭代法求解(MP)MP)的注意点:构造的点列的
14、注意点:构造的点列 x xk k,其极限点应是近似最优解,其极限点应是近似最优解,即该算法必须是收敛的即该算法必须是收敛的.第15页,此课件共84页哦迭代法的关键:迭代法的关键:(1)如何构造每一轮的搜索方向pk;(2)确定步长k 关于k,前面是以minf(xk+pk)产生的,也有些算法k取为一个固定值,这要根据具体问题来确定.关于Pk的选择,在无约束极值问题中只要是使目标函数值下降的方向就可以了,对于约束极值问题则必需为可行下降方向.(3)在无约束最优化中,当函数梯度的模充分小时,(2)当函数值的下降量充分小时,(1)自变量的改变量充分小时,计算终止条件计算终止条件 在上述迭代中有:若在上述
15、迭代中有:若x xk+1k+1满足某终止条件则停止计算,输出近似最优解满足某终止条件则停止计算,输出近似最优解x xk+1k+1.这这里满足某终止条件即到达某精确度要求里满足某终止条件即到达某精确度要求.常用的计算终止条件有以下几个:常用的计算终止条件有以下几个:第16页,此课件共84页哦定义7.8 设,若存在使,则称向量是函数在点处的下降方向.n定义定义7.9 设,若存在使得,称向量设,若存在使得,称向量是点处关于的可行方向是点处关于的可行方向.若一个向量既是目标函数在点处的若一个向量既是目标函数在点处的下降方向,又是该点处关于可行域的可行方向,则称为函数在点处下降方向,又是该点处关于可行域
16、的可行方向,则称为函数在点处关于区域的可行下降方向关于区域的可行下降方向.n根据不同原理产生了不同的和的选择方法,就产生了各种算法根据不同原理产生了不同的和的选择方法,就产生了各种算法.n在以后的讨论中,一维极值的优化问题是讨论求解步长在以后的讨论中,一维极值的优化问题是讨论求解步长.n无约束极值中讨论的最速下降法,共轭方向法,坐标轮换法,牛顿法,变尺度法及有约无约束极值中讨论的最速下降法,共轭方向法,坐标轮换法,牛顿法,变尺度法及有约束极值中讨论的可行方向法都是根据不同的原理选择得到的迭代算法束极值中讨论的可行方向法都是根据不同的原理选择得到的迭代算法.第17页,此课件共84页哦七、迭代算法
17、的收敛性七、迭代算法的收敛性n定义定义7.10 设有一算法设有一算法A,若对任一初始点(可行点),通过,若对任一初始点(可行点),通过A进行迭代时,或在有限步后进行迭代时,或在有限步后停止得到满足要求的点;或得到一个无穷点列,它的任何一个聚点均是满足要求的停止得到满足要求的点;或得到一个无穷点列,它的任何一个聚点均是满足要求的点,则称此算法点,则称此算法A具有全局收敛性具有全局收敛性.n定义定义7.11 设(设(UMP)问题的目标函数)问题的目标函数 ,为对称半正定矩为对称半正定矩阵,若由算法阵,若由算法A进行迭代时,不论初始点进行迭代时,不论初始点 如何选择,必能在有限步后停止迭代,得到所要
18、求的如何选择,必能在有限步后停止迭代,得到所要求的点,则称此算法点,则称此算法A有二次有限终止性有二次有限终止性.n定义定义7.12 设序列设序列 收敛于收敛于 ,定义满足,定义满足 的非的非负数负数 的上确界为的上确界为 的收敛级的收敛级.n 若序列的收敛级为若序列的收敛级为 ,就称序列是,就称序列是 级收敛的级收敛的.第18页,此课件共84页哦若 且 就称序列是以收敛比 线性收敛的.若 或 且 就称序列是超线性收敛的.n如何判别算法的收敛性和收敛速度问题本书不讨论如何判别算法的收敛性和收敛速度问题本书不讨论.n本书给出的算法中,最速下降法具有全局收敛性、是线性收敛的;本书给出的算法中,最速
19、下降法具有全局收敛性、是线性收敛的;改进牛顿法具有全局收敛性、二次有限终止性、是二阶线性收敛改进牛顿法具有全局收敛性、二次有限终止性、是二阶线性收敛的;变尺度法和共轭方向法具有全局收敛性和二次有限终止性、的;变尺度法和共轭方向法具有全局收敛性和二次有限终止性、是超线性收敛的;是超线性收敛的;Zoutenddijk法不具有全局收敛性、改进的法不具有全局收敛性、改进的T-V 法具有全局收敛性;制约函数法具有全局收敛性法具有全局收敛性;制约函数法具有全局收敛性.关于这些算法的关于这些算法的收敛性的讨论和证明有兴趣的读者可参考其他文献收敛性的讨论和证明有兴趣的读者可参考其他文献.第19页,此课件共84
20、页哦2 一维极值问题的优化方法一维极值问题的优化方法n 前面讨论迭代算法时前面讨论迭代算法时,从从 出发确定沿方向出发确定沿方向 的步长的步长 是这样求解的是这样求解的 这里这里 ,已知已知.所以所以,若记若记 ,则为求解则为求解 的过程的过程.n于是我们考虑如下形式的极值问题于是我们考虑如下形式的极值问题.(7.8)为任意实数为任意实数n很显然可应用高等数学中学过的解析法很显然可应用高等数学中学过的解析法,即令即令 求出平稳点求出平稳点,但如前面所述如果但如前面所述如果该方程解不出来该方程解不出来,怎么办怎么办?可用下述迭代算法可用下述迭代算法0.618法法.第20页,此课件共84页哦定义7
21、.13 定义在 上,若存在点 当 ,有 ,当 时,称 在 中为单峰函数(单谷函数).n显然满足定义要求的点显然满足定义要求的点 是是 在在 中的极小点中的极小点.n在在 中任选两点中任选两点 ,且且 ,根据根据 的单峰性的单峰性,若若 ,则则 必然位于必然位于 内内,如果如果 ,则则 必然位于必然位于 内内.如如果果 ,则则 必然位于必然位于 ,记此区间为记此区间为 .如此继续如此继续,得得闭区间套闭区间套 .显然显然 ,又,又 .由闭区间套性质由闭区间套性质,为极小值点为极小值点.闭区间套的选择方法不同闭区间套的选择方法不同,求得的求得的 的快慢及求解过程的计算量是不的快慢及求解过程的计算量
22、是不一样的,有一个常用的方法是一样的,有一个常用的方法是0.618法法.第21页,此课件共84页哦0.618 0.618 法:法:第22页,此课件共84页哦解:解:,=-3,5 =-3+0.3828=0.056 =0.115 =-3+0.6188=1.944 =7.667由于由于 所以新的不定区间为所以新的不定区间为 ,=-3,1.944由于由于 -=4.944 0.2 :=0.056 :=0.115 =-3+0.3824.944=-1.112 =-0.987如此反复得下表如此反复得下表例例7.3 用0.618法求解:第23页,此课件共84页哦迭代换换1-350.0561.9440.1157.
23、6672-31.944-1.1120.056-0.987-0.9874-1.8320.056-1.112-0.664-0.987-0.9876-1.384-0.664-1.1120.936-0.987-0.9967-1.112-0.664-0.936-0.840-0.996-0.9748-1.112-0.840-1.016-0.936-1.000-0.9969-1.112-0.936第24页,此课件共84页哦3 无约束极值的优化方法无约束极值的优化方法n考虑无约束最优化问题(考虑无约束最优化问题()n (7.9)n前面已经讨论过前面已经讨论过,求解此无约束优化问题求解此无约束优化问题,可以求出
24、平稳点及不可导点的方法可以求出平稳点及不可导点的方法.令令 ,求出平稳点求出平稳点.如果如果 是正定的是正定的,则则 是是 的严格局部最优解的严格局部最优解.若若 在在 上是凸函数上是凸函数,则是整体最优解则是整体最优解.n在求解在求解 这这 维方程组比较困难时,就用最优化算法维方程组比较困难时,就用最优化算法迭代法迭代法.本节将介绍本节将介绍最速下降法最速下降法,牛顿法牛顿法,共轭方向法共轭方向法,坐标轮换法坐标轮换法,变尺度法变尺度法.这些算法就是用不同的方法来选择这些算法就是用不同的方法来选择搜索方向搜索方向 而得到的而得到的.当然当然 必须是下降方向必须是下降方向.第25页,此课件共8
25、4页哦定理定理7.7 设设 ,在点,在点 处可微处可微,若存在若存在 ,使使 ,则向量则向量 是是 在在 处的处的下降方向下降方向.n证明证明:可微可微(在在 处处),由泰勒展开式,由泰勒展开式,有有 时时,有有 是是 在点在点 的下降方向的下降方向.证毕证毕.第26页,此课件共84页哦一、最速下降法一、最速下降法 最速下降法又称梯度法最速下降法又称梯度法,选择负梯度方向作为目标函数值下降的方向选择负梯度方向作为目标函数值下降的方向,是比是比较古老的一种算法,其它的方法是它的变形或受它的启发而得到的,因此它是较古老的一种算法,其它的方法是它的变形或受它的启发而得到的,因此它是最优化方法的基础最
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 非线性 规划 课件
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内