无约束非线性规划精选PPT.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》由会员分享,可在线阅读,更多相关《无约束非线性规划精选PPT.ppt(139页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、关于无约束非线性规划第1页,讲稿共139张,创作于星期二2.1 非线性函数和非线性规划的概念非线性函数和非线性规划的概念线性函数线性函数:(1)f(kx)=kf(x)(2)f(x1+x2)=f(x1)+f(x2)则非线性函数就是不满足以上两个条件的函数则非线性函数就是不满足以上两个条件的函数非非线线性性规规划划:如如果果目目标标函函数数或或约约束束条条件件中中,有有一一个个或或多多个个是是变变量量的的非非线线性性函函数数,就就称称为为非非线线性性规规划划第2页,讲稿共139张,创作于星期二非线性规划问题非线性规划问题例例1 1 曲线的最优拟合问题曲线的最优拟合问题第3页,讲稿共139张,创作于
2、星期二例例2 2 构件容积问题构件容积问题第4页,讲稿共139张,创作于星期二非线性规划问题非线性规划问题例例3 3第5页,讲稿共139张,创作于星期二非线性规划问题非线性规划问题例例3 3第6页,讲稿共139张,创作于星期二非线性规非线性规划划通通常常情情况况下下,目目标标函函数数f(x)和和约约束束条条件件hi(X)和和gi(X)为自变量的非线性函数为自变量的非线性函数第7页,讲稿共139张,创作于星期二非线性规非线性规划划ULP的可行解或可行点的可行解或可行点约束集或可行域约束集或可行域第8页,讲稿共139张,创作于星期二向量化表示向量化表示当当p=0,q=0时,称为时,称为无约束非线性
3、规划无约束非线性规划或者或者无约束最优无约束最优化问题化问题。否则,称为否则,称为约束非线性规划约束非线性规划或者或者约束最优化问题约束最优化问题。第9页,讲稿共139张,创作于星期二最优解和极小点最优解和极小点第10页,讲稿共139张,创作于星期二最优解和极小点最优解和极小点第11页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件必必要要条条件件:设设是是n n维维欧欧氏氏空空间间的的某某一一区区域域,f(X)f(X)为为定定义义在在上上的的实实值值函函数数,是是区区域域的的内内点点,若若f(f()在在处处可可微微,且且在该点取得局部极小值,则必有在该点取得局部极小值,则必有或或第
4、12页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件其中,其中,为为函函数数f(x)f(x)在在处处的的梯梯度度,梯梯度度的的方方向向为为f(X)f(X)的的等等值值面面(等等值值线线)的的法法线线方方向向,沿沿这这个方向函数值增加最快个方向函数值增加最快满满足足上上式式的的点点称称为为驻驻点点,在在区区域域内内部部,极极值点必为驻点;但驻点不一定是值点必为驻点;但驻点不一定是极值点极值点第13页,讲稿共139张,创作于星期二14二次型二次型二次型是X=(x1,x2,xn)T的二次齐次函数:aij=aji,A为n*n对称矩阵。若A的所有元素均为实数,则为实二次型。一个二次型唯一对应
5、一个对称矩阵,反之,一个对称矩阵也唯一确定一个二次型。二次型(对称矩阵)正定,负定,不定。半正定,半负定。第14页,讲稿共139张,创作于星期二15二次型二次型二次型正定的充要条件,是它的矩阵的左上角各阶主子式都大于零。二次型负定的充要条件,是它的矩阵的左上角各阶主子式都负、正相间。例:判定正负性。第15页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件充充分分条条件件:设设是是n n维维欧欧氏氏空空间间的的某某一一区区域域,f(X)f(X)为为定定义义在在上上的的实实值值函函数数,是是区区域域的的内内点点,f(f()在在上上二二次次连连续续可可微微,若若f()在在且且处处满满足足(
6、5 5)或或(5 5)式式,且且对任何非零矢量均有对任何非零矢量均有则则f(x)f(x)在在取取严严格格局局部部极极小小值值,此此处处(x*)x*)为为f(x)f(x)在在点点处处的的海海赛赛(Hesse)Hesse)矩阵矩阵第16页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件此此处处(x*)x*)为为f(x)f(x)在在点点处处的的海海赛赛(Hesse)Hesse)矩阵矩阵第17页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件例求目标函数例求目标函数的梯度和的梯度和HesseHesse矩阵矩阵解解:因为因为 ,所以所以第18页,讲稿共139张,创作于星期二极值存在的
7、条件极值存在的条件又因为又因为所以所以即为即为HesseHesse矩阵矩阵第19页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件例例2 2试研究函数试研究函数f(xf(x1 1,x,x2 2)=x)=x2 22 2-x-x1 1的驻点的驻点解:令解:令得得(,)点点 为为 驻驻 点点,x1=0 x1=0是是 一一 无无 函函 数数f(x1,0)=-xf(x1,0)=-x1 12 2的的极极大大点点,而而x2=0 x2=0却却是是一一元元函函数数f(0,x2)=xf(0,x2)=x2 22 2的极小点,即:的极小点,即:故驻点(,)不是极值点,而是一个鞍点故驻点(,)不是极值点,而是
8、一个鞍点第20页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件例例3 3试试求求函函数数f(xf(x1 1,x,x2 2)=2x)=2x1 12 2-8x-8x1 1+2x+2x2 2-4x-4x2 2+20+20的的极极值和极值点值和极值点解:令解:令得(得(2,12,1)点为驻点)点为驻点第21页,讲稿共139张,创作于星期二极值存在的条件极值存在的条件其海赛矩阵之行列式其海赛矩阵之行列式可知(可知(2,12,1)点为极小点)点为极小点,其极小值为其极小值为:第22页,讲稿共139张,创作于星期二凸函数和凸规划凸函数和凸规划凸函数及其性质凸函数及其性质凸规划及其性质凸规划及其性
9、质第23页,讲稿共139张,创作于星期二凸函数及其性质凸函数及其性质第24页,讲稿共139张,创作于星期二凸函数的性质凸函数的性质第25页,讲稿共139张,创作于星期二凸函数的判定凸函数的判定第26页,讲稿共139张,创作于星期二第27页,讲稿共139张,创作于星期二凸函数的判定凸函数的判定例例4 4 判定下述函数是凸函数还是凹函数判定下述函数是凸函数还是凹函数解解:因为因为其海赛阵的行列式为:其海赛阵的行列式为:故其海赛阵处处正定,由定理故其海赛阵处处正定,由定理2.2.42.2.4得得f(X)f(X)为严格凸函数为严格凸函数第28页,讲稿共139张,创作于星期二凸函数的判定凸函数的判定例例
10、5 5 试证明为凹函数试证明为凹函数证证:(1)(1)首首先先由由定定义义来来证证明明,任任取取两两点点a1,a2,a1,a2,看看下下式式是是否否成成立?立?或或由由于于,故故显显然然,不不管管a a1 1,a,a2 2取取什什么么值值,总总有有()式式成成立立,故故f(xf(x1 1)=-x)=-x1 12 2为为凹凹函函数数,同同理可证理可证f(xf(x2 2)=-x)=-x2 22 2也是凹函数也是凹函数或或第29页,讲稿共139张,创作于星期二凸函数的判定凸函数的判定证证:(:()用定理用定理2.2.42.2.4来证明,由于来证明,由于故海赛矩阵处处负定,故故海赛矩阵处处负定,故f(
11、X)f(X)为严格凹函数为严格凹函数第30页,讲稿共139张,创作于星期二凸函数的判定凸函数的判定证证:(:()用定理用定理5.2.35.2.3来证明,任意取第一点来证明,任意取第一点,第二点,这样,第二点,这样现看下式是否成立现看下式是否成立或或或或证证:(:()用定理用定理2.2.32.2.3来证明,任意取第一点来证明,任意取第一点,第二点,这样,第二点,这样第31页,讲稿共139张,创作于星期二凸函数的判定凸函数的判定不不管管a a1 1,a,a2 2和和b b1 1,b,b2 2取取什什么么值值,上上式式均均成成立立从从而而证证明明f(f()是凹函数)是凹函数或或第32页,讲稿共139
12、张,创作于星期二凸规划及其性质凸规划及其性质约束集如果如果(MP)的约束集的约束集X是凸集,目标函数是凸集,目标函数f是是X上的凸函数,则上的凸函数,则(MP)叫做叫做非线性凸非线性凸规划规划,或简称为,或简称为凸规划凸规划。第33页,讲稿共139张,创作于星期二定理定理 2.2.6 凸规划的任一局部最优解都是凸规划的任一局部最优解都是它的整体最优解。它的整体最优解。第34页,讲稿共139张,创作于星期二凸规划及其性质凸规划及其性质由于线性函数也既是凸函数,又是凹函数,由于线性函数也既是凸函数,又是凹函数,故线性规划也属于凸规划故线性规划也属于凸规划第35页,讲稿共139张,创作于星期二凸规划
13、及其性质凸规划及其性质例例6 6试分析非线性规划试分析非线性规划解:解:f(X)f(X)和和g g2 2(X)(X)的海赛矩阵的行列式是的海赛矩阵的行列式是第36页,讲稿共139张,创作于星期二凸规划及其性质凸规划及其性质由由上上可可知知f(X)f(X)为为严严格格凸凸函函数数,g,g2 2(x)(x)为为凹凹函函数数,由由于于为为线线性性函函数数,故故上上述述约约束束条条件件构构成成的的可可行行域域为为凸凸集集,这这是是一一个个凸凸规规划划,点点为为最最优优点点:(0.58,1.34)0.58,1.34)T T,目目 标标 函函 数数 的的 最最 优优 值值 为为f(Xf(X*)=3.8.)
14、=3.8.g1(X)g2(X)=0C目标函数等值线目标函数等值线第37页,讲稿共139张,创作于星期二算法及有关概念算法及有关概念最优化问题的数值解法及理论根据:最优化问题的数值解法及理论根据:1 在集合上的迭代算法是指:在集合上的迭代算法是指:开始:选定一个初始点开始:选定一个初始点 ,置置k=0,然后再按某种规则把然后再按某种规则把k次迭代的次迭代的x(k)映射为新映射为新的一点的一点x(k+1),记为这称为第记为这称为第k+1次迭次迭代这个过程无限进行下去,就产生一个点列代这个过程无限进行下去,就产生一个点列,其中规则称为算法若收敛于问题的,其中规则称为算法若收敛于问题的最优解,就称算法
15、在上是收敛的,否则是最优解,就称算法在上是收敛的,否则是发散的发散的第38页,讲稿共139张,创作于星期二算法及有关概念算法及有关概念一种算法除了满足计算终止准则的迭代点外一种算法除了满足计算终止准则的迭代点外,还还应满足应满足:下降算法下降算法:若对于每个若对于每个k,都有都有 ,则称则称A为为下降迭代算法下降迭代算法,简称下降算法简称下降算法.许多最优化方法都采用将多维问题转化为一维许多最优化方法都采用将多维问题转化为一维问题的方法来求解问题的方法来求解.第39页,讲稿共139张,创作于星期二算法及有关概念算法及有关概念 如如:设第设第k次迭代点次迭代点xk已求得已求得,若它不满足终止准若
16、它不满足终止准则则,在该点必存在下降方向在该点必存在下降方向.对于可微目标函数对于可微目标函数,即即是满足是满足 的的d.按某种规则从中选取一个按某种规则从中选取一个,例如例如dk,再沿这个方向再沿这个方向适当迈进一步适当迈进一步,即在直线即在直线 上适当确定一个上适当确定一个新点新点 ,使使 那我们就说完成了第那我们就说完成了第k+1次迭代次迭代,其中其中 称为步长因子称为步长因子.第40页,讲稿共139张,创作于星期二算法及有关概念算法及有关概念迭代过程中应满足两个准则迭代过程中应满足两个准则:1 是下降方向是下降方向dk的选取的选取;2是步长因子是步长因子 的选取的选取 各种迭代法的区别
17、就在于得出方向各种迭代法的区别就在于得出方向 dk 与步与步 长长 的方式不同的方式不同.对于非线性规划对于非线性规划,总结出总结出:第41页,讲稿共139张,创作于星期二非线性规划方法概述非线性规划方法概述第42页,讲稿共139张,创作于星期二非线性规划基本迭代格式非线性规划基本迭代格式第43页,讲稿共139张,创作于星期二无约束优化无约束优化:最优解的分类和条件最优解的分类和条件给定一个函数给定一个函数 f(x),),寻找寻找 x*使得使得 f(x*)最小,即最小,即其中其中局部最优解局部最优解全局最优解全局最优解必要条件必要条件x*f(x)xlxgo充分条件充分条件Hessian阵阵最优
18、解在可行域边界上取得时不能用无约束优化方法求解最优解在可行域边界上取得时不能用无约束优化方法求解第44页,讲稿共139张,创作于星期二2 2 迭代法中直线搜索及其性质:迭代法中直线搜索及其性质:在搜索方向已经确定的前提下在搜索方向已经确定的前提下,步长因子的选步长因子的选取有多种方法取有多种方法,如如 i)取步长因子为某个常数取步长因子为某个常数,但不能保证使目标函但不能保证使目标函数值下降数值下降;ii)可接受点算法,只要能使目标函数下降,可可接受点算法,只要能使目标函数下降,可任意选取步长任意选取步长;iii)基于沿搜索方向使目标函数值下降最多,基于沿搜索方向使目标函数值下降最多,沿射线沿
19、射线 求目标函数的极小值:求目标函数的极小值:第45页,讲稿共139张,创作于星期二2 2 迭代法中直线搜索及其性质:迭代法中直线搜索及其性质:由于这项工作是求以为变量的一元函数由于这项工作是求以为变量的一元函数的极小点,故称这一过程为的极小点,故称这一过程为一维搜索一维搜索(线搜索线搜索),这),这样确定的步长为样确定的步长为最佳步长最佳步长,实际计算中常用此方法实际计算中常用此方法.一维搜索有个性质:在搜索方向上所得最优点处一维搜索有个性质:在搜索方向上所得最优点处的梯度和搜索方向正交的梯度和搜索方向正交定理:设目标函数定理:设目标函数f(X)具有一阶连续偏导数,具有一阶连续偏导数,x(k
20、+1)按下列规划产生:按下列规划产生:则有则有第46页,讲稿共139张,创作于星期二3 3 收敛速度收敛速度 一一个个算算法法不不光光能能收收敛敛于于解解,还还必必须须以以较较快的速度收敛于解快的速度收敛于解,这才是这才是好的算法好的算法;我我们们用用以以下下收收敛敛的的阶阶来来度度量量一一个个算算法法的的收敛速度收敛速度.第47页,讲稿共139张,创作于星期二3 3 收敛速度收敛速度 定义定义:设序列设序列 收敛于收敛于 ,而且而且 若若 ,则称则称 为为线性收敛线性收敛的的,为为收敛比收敛比;若若 ,则称则称 为为超线性收敛超线性收敛.定义定义:设序列设序列 收敛于收敛于 ,若对于某个实若
21、对于某个实数数 ,有有 则称序列则称序列 为为 阶收敛的阶收敛的第48页,讲稿共139张,创作于星期二3 3 收敛速度收敛速度 一一般般来来说说,线线性性收收敛敛是是比比较较慢慢的的,而而二二阶阶收收敛敛则则是是很很快快的的,超超线线性性收收敛敛居居中中,如如果果一一个个算算法法具具有有超超线线性性以以上上的的收收敛敛速速度度,我我们们就认为它是一个很好的算法了就认为它是一个很好的算法了.第49页,讲稿共139张,创作于星期二50因真正的极值点事先并不知道,故在实用上只能根据相继两次迭代得到的计算结果来判断是否已达到要求,从而建立终止迭代计算的准则。常用的终止迭代准则有:(1)根据相继两次迭代
22、结果的绝对误差。4.终止迭代准则终止迭代准则(2)根据相继两次迭代结果的相对误差。(3)根据函数梯度的模足够小。迭代终止准则 点距准则 函数值下降准则 梯度准则第50页,讲稿共139张,创作于星期二2.2 一维搜索方法一维搜索方法精确一维搜索方法精确一维搜索方法 0.618法法 Newton法法非精确一维搜索方法非精确一维搜索方法 Goldstein法法 Armijo法法第51页,讲稿共139张,创作于星期二一维搜索一维搜索 上节提到上节提到,在大多数无约束极值的算法中在大多数无约束极值的算法中,为了确定最为了确定最优解优解,一般用解析的方法是很难得到的一般用解析的方法是很难得到的,即精确解通
23、常是即精确解通常是计算不出来的计算不出来的,故我们常采用的是数值的方法来得到其故我们常采用的是数值的方法来得到其近似解近似解,上节我们提到上节我们提到,数值解法最常用的一种方法是迭数值解法最常用的一种方法是迭代法代法.为了确定极小化点列为了确定极小化点列,要沿逐次确定的系列射线求要沿逐次确定的系列射线求极小点极小点,即所谓的一维搜索即所谓的一维搜索.一一维维搜搜索索可可归归结结为为单单变变量量函函数数求求极极小小的的问问题题,设设目目标标函函数数为为 ,过过点点 沿沿方方向向 的的直直线线可可用用点点集集表表示示为为:第52页,讲稿共139张,创作于星期二 求 在直线L上的极小点转化为求一元函
24、数 的极小点.如果 的极小点为 ,通常称 为沿方向 的步长因子 或简称步长.函数 在直线上的极小点就是 一维搜索的方法一般有以下几类:1.数学分析中所讲的方法,即解方程,此方法称为精确线性搜解方程,此方法称为精确线性搜索索.2.试探法试探法:按照某种方式试探点,通过一系列试探点的比较确定极小点.第53页,讲稿共139张,创作于星期二 3.函数逼近法函数逼近法:用比较简单的曲线近似代替原来的曲线,用近似曲线的极小点 来估计原来的极小点.下面我们将分别具体介绍几种方法:一.平分法 根据以前我们所学习的知识,我们知道,在 的极小点 处 有 ,并且当 时,函数是递减的,即 ;而 当 时,函数递增,即
25、.注:因为 为极小点,若:此时 为极大点.第54页,讲稿共139张,创作于星期二 我们找到了一个区间 ,具有性质 则在 间必然有 的极小点 ,且 .为了找到 ,我们取 .1.若 ,则在 中有极小点,2.若 ,则在 中有极小点.y=f(x)00 xy第55页,讲稿共139张,创作于星期二 若情形1满足时,此时以 作为新的区间;若情形2满足时,此时以 作为新的区间.继续上述过程,逐步将区间换小,当区间 充分小时,或者当 充分小时,即可将区间 中点取做极小点的近似,此时有:0 xy0 xy第56页,讲稿共139张,创作于星期二 注:也可以用以下的收敛准则:1.成立,2.成立.但是我们如何来确定初始区
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 无约束 非线性 规划 精选 PPT
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内