无约束非线性规划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、关于无约束非线性规划第一张,PPT 共一百三十九页,创作于2022 年6 月2.1 非线性函数和非线性规划的概念线性函数:(1)f(kx)=kf(x)(2)f(x1+x2)=f(x1)+f(x2)则非线性函数就是不满足以上两个条件的函数非线性规划:如果目标函数或约束条件中,有一个或多个是变量的非线性函数,就称为非线性规划第二张,PPT 共一百三十九页,创作于2022 年6 月非线性规划问题例1 曲线的最优拟合问题第三张,PPT 共一百三十九页,创作于2022 年6 月例2 构件容积问题第四张,PPT 共一百三十九页,创作于2022 年6 月非线性规划问题例3第五张,PPT 共一百三十九页,创作
2、于2022 年6 月非线性规划问题例3第六张,PPT 共一百三十九页,创作于2022 年6 月非线性规划通常情况下,目标函数f(x)和约束条件hi(X)和gi(X)为自变量的非线性函数第七张,PPT 共一百三十九页,创作于2022 年6 月非线性规划ULP的可行解或可行点约束集或可行域第八张,PPT 共一百三十九页,创作于2022 年6 月向量化表示当p=0,q=0时,称为无约束非线性规划或者无约束最优化问题。否则,称为约束非线性规划或者约束最优化问题。第九张,PPT 共一百三十九页,创作于2022 年6 月最优解和极小点第十张,PPT 共一百三十九页,创作于2022 年6 月最优解和极小点第
3、十一张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件必要条件:设是n维欧氏空间的某一区域,f(X)为定义在上的实值函数,是区域的内点,若f()在处可微,且在该点取得局部极小值,则必有或第十二张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件其中,为函数f(x)在处的梯度,梯度的方向为f(X)的等值面(等值线)的法线方向,沿这个方向函数值增加最快满足上式的点称为驻点,在区域内部,极值点必为驻点;但驻点不一定是极值点第十三张,PPT 共一百三十九页,创作于2022 年6 月14二次型二次型是 X=(x1,x2,xn)T的二次齐次函数:aij=aji,A 为 n*n
4、 对称矩阵。若A 的所有元素均为实数,则为实二次型。一 个 二 次 型 唯 一 对 应 一 个 对 称 矩 阵,反 之,一 个 对 称 矩 阵 也 唯 一 确 定 一 个二次型。二次型(对称矩阵)正定,负定,不定。半正定,半负定。第十四张,PPT 共一百三十九页,创作于2022 年6 月15二次型二次型正定的充要条件,是它的矩阵的左上角各阶主子式都大于零。二 次 型 负 定 的 充 要 条 件,是 它 的 矩 阵 的 左 上 角 各 阶 主 子 式 都 负、正相间。例:判定正负性。第十五张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件充分条件:设是n维欧氏空间的某一区域,f(
5、X)为定义在上的实值函数,是区域的内点,f()在上二次连续可微,若f()在且处满足(5)或(5)式,且对任何非零矢量均有则f(x)在取严格局部极小值,此处(x*)为f(x)在点处的海赛(Hesse)矩阵第十六张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件此 处(x*)为 f(x)在 点 处 的 海 赛(Hesse)矩阵第十七张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件例求目标函数的梯度和Hesse矩阵解:因为,所以第十八张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件又因为所以即为Hesse矩阵第十九张,PPT 共一百三十九页,创作于
6、2022 年6 月极值存在的条件例2试研究函数f(x1,x2)=x22-x1的驻点解:令得(,)点为驻点,x1=0是一无函数f(x1,0)=-x12的极大点,而x2=0却是一元函数f(0,x2)=x22的极小点,即:故驻点(,)不是极值点,而是一个鞍点第二十张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件例3试求函数f(x1,x2)=2x12-8x1+2x2-4x2+20的极值和极值点解:令得(2,1)点为驻点第二十一张,PPT 共一百三十九页,创作于2022 年6 月极值存在的条件其海赛矩阵之行列式可知(2,1)点为极小点,其极小值为:第二十二张,PPT 共一百三十九页,创
7、作于2022 年6 月凸函数和凸规划凸函数及其性质凸规划及其性质第二十三张,PPT 共一百三十九页,创作于2022 年6 月凸函数及其性质第二十四张,PPT 共一百三十九页,创作于2022 年6 月凸函数的性质第二十五张,PPT 共一百三十九页,创作于2022 年6 月凸函数的判定第二十六张,PPT 共一百三十九页,创作于2022 年6 月第二十七张,PPT 共一百三十九页,创作于2022 年6 月凸函数的判定例4 判定下述函数是凸函数还是凹函数解:因为其海赛阵的行列式为:故其海赛阵处处正定,由定理2.2.4得f(X)为严格凸函数第二十八张,PPT 共一百三十九页,创作于2022 年6 月凸函
8、数的判定例5 试证明为凹函数证:(1)首先由定义来证明,任取两点a1,a2,看下式是否成立?或由于,故显然,不管a1,a2取什么值,总有()式成立,故f(x1)=-x12为凹函数,同理可证f(x2)=-x22也是凹函数或第二十九张,PPT 共一百三十九页,创作于2022 年6 月凸函数的判定证:()用定理2.2.4来证明,由于故海赛矩阵处处负定,故f(X)为严格凹函数第三十张,PPT 共一百三十九页,创作于2022 年6 月凸函数的判定证:()用定理5.2.3来证明,任意取第一点,第二点,这样现看下式是否成立或或证:()用定理2.2.3来证明,任意取第一点,第二点,这样第三十一张,PPT 共一
9、百三十九页,创作于2022 年6 月凸函数的判定不管a1,a2和b1,b2取什么值,上式均成立从而证明f()是凹函数或第三十二张,PPT 共一百三十九页,创作于2022 年6 月凸规划及其性质约束集如果(MP)的约束集X是凸集,目标函数f是X上的凸函数,则(MP)叫做非线性凸规划,或简称为凸规划。第三十三张,PPT 共一百三十九页,创作于2022 年6 月定理 2.2.6 凸规划的任一局部最优解都是它的整体最优解。第三十四张,PPT 共一百三十九页,创作于2022 年6 月凸规划及其性质由于线性函数也既是凸函数,又是凹函数,故线性规划也属于凸规划第三十五张,PPT 共一百三十九页,创作于202
10、2 年6 月凸规划及其性质例6试分析非线性规划解:f(X)和g2(X)的海赛矩阵的行列式是第三十六张,PPT 共一百三十九页,创作于2022 年6 月凸规划及其性质由上可知f(X)为严格凸函数,g2(x)为凹函数,由于为线性函数,故上述约束条件构成的可行域为凸集,这是一个凸规划,点为最优点:(0.58,1.34)T,目 标 函 数 的 最 优 值 为f(X*)=3.8.g1(X)g2(X)=0C目标函数等值线第三十七张,PPT 共一百三十九页,创作于2022 年6 月算法及有关概念最优化问题的数值解法及理论根据:1 在集合上的迭代算法是指:开始:选定一个初始点,置k=0,然后再按某种规则把k次
11、迭代的x(k)映射为新的一点x(k+1),记为这称为第k+1次迭代这个过程无限进行下去,就产生一个点列,其中规则称为算法若收敛于问题的最优解,就称算法在上是收敛的,否则是发散的第三十八张,PPT 共一百三十九页,创作于2022 年6 月算法及有关概念一种算法除了满足计算终止准则的迭代点外,还应满足:下降算法:若对于每个k,都有,则称A为下降迭代算法,简称下降算法.许多最优化方法都采用将多维问题转化为一维问题的方法来求解.第三十九张,PPT 共一百三十九页,创作于2022 年6 月算法及有关概念 如:设第k次迭代点xk已求得,若它不满足终止准则,在该点必存在下降方向.对于可微目标函数,即是满足
12、的d.按某种规则从中选取一个,例如dk,再沿这个方向适当迈进一步,即在直线 上适当确定一个新点,使 那我们就说完成了第k+1次迭代,其中 称为步长因子.第四十张,PPT 共一百三十九页,创作于2022 年6 月算法及有关概念迭代过程中应满足两个准则:1 是下降方向dk的选取;2是步长因子 的选取 各种迭代法的区别就在于得出方向 dk 与步 长 的方式不同.对于非线性规划,总结出:第四十一张,PPT 共一百三十九页,创作于2022 年6 月非线性规划方法概述第四十二张,PPT 共一百三十九页,创作于2022 年6 月非线性规划基本迭代格式第四十三张,PPT 共一百三十九页,创作于2022 年6
13、月无约束优化:最优解的分类和条件给定一个函数 f(x),寻找 x*使得 f(x*)最小,即其中局部最优解全局最优解必要条件x*f(x)xlxgo充分条件Hessian阵最优解在可行域边界上取得时不能用无约束优化方法求解第四十四张,PPT 共一百三十九页,创作于2022 年6 月2 迭代法中直线搜索及其性质:在搜索方向已经确定的前提下,步长因子的选取有多种方法,如 i)取步长因子为某个常数,但不能保证使目标函数值下降;ii)可接受点算法,只要能使目标函数下降,可任意选取步长;iii)基于沿搜索方向使目标函数值下降最多,沿射线 求目标函数的极小值:第四十五张,PPT 共一百三十九页,创作于2022
14、 年6 月2 迭代法中直线搜索及其性质:由于这项工作是求以为变量的一元函数的极小点,故称这一过程为一维搜索(线搜索),这样确定的步长为最佳步长,实际计算中常用此方法.一维搜索有个性质:在搜索方向上所得最优点处的梯度和搜索方向正交定理:设目标函数f(X)具有一阶连续偏导数,x(k+1)按下列规划产生:则有第四十六张,PPT 共一百三十九页,创作于2022 年6 月3 收敛速度 一个算法不光能收敛于解,还必须以较快的速度收敛于解,这才是好的算法;我们用以下收敛的阶来度量一个算法的收敛速度.第四十七张,PPT 共一百三十九页,创作于2022 年6 月3 收敛速度 定义:设序列 收敛于,而且 若,则称
15、 为线性收敛的,为收敛比;若,则称 为超线性收敛.定义:设序列 收敛于,若对于某个实数,有 则称序列 为 阶收敛的第四十八张,PPT 共一百三十九页,创作于2022 年6 月3 收敛速度 一般来说,线性收敛是比较慢的,而二阶收敛则是很快的,超线性收敛居中,如果一个算法具有超线性以上的收敛速度,我们就认为它是一个很好的算法了.第四十九张,PPT 共一百三十九页,创作于2022 年6 月50 因真正的极值点事先并不知道,故在实用上只能根据相继两次迭代得到的计算结果来判断是否已达到要求,从而建立终止迭代计算的准则。常用的终止迭代准则有:(1)根据相继两次迭代结果的绝对误差。4.终止迭代准则(2)根据
16、相继两次迭代结果的相对误差。(3)根据函数梯度的模足够小。迭代终止准则 点距准则 函数值下降准则 梯度准则第五十张,PPT 共一百三十九页,创作于2022 年6 月2.2 一维搜索方法精确一维搜索方法 0.618法 Newton法非精确一维搜索方法 Goldstein法 Armijo法第五十一张,PPT 共一百三十九页,创作于2022 年6 月一维搜索 上节提到,在大多数无约束极值的算法中,为了确定最优解,一般用解析的方法是很难得到的,即精确解通常是计算不出来的,故我们常采用的是数值的方法来得到其近似解,上节我们提到,数值解法最常用的一种方法是迭代法.为了确定极小化点列,要沿逐次确定的系列射线
17、求极小点,即所谓的一维搜索.一维搜索可归结为单变量函数求极小的问题,设目标函数为,过点 沿方向 的直线可用点集表示为:第五十二张,PPT 共一百三十九页,创作于2022 年6 月 求 在直线L 上的极小点转化为求一元函数 的极小点.如果 的极小点为,通常称 为沿方向 的步长因子 或简称步长.函数 在直线上的极小点就是 一维搜索的方法一般有以下几类:1.数学分析中所讲的方法,即解方程,此方法称为精确线性搜索.2.试探法:按照某种方式试探点,通过一系列试探点的比较确定极小点.第五十三张,PPT 共一百三十九页,创作于2022 年6 月 3.函数逼近法:用比较简单的曲线近似代替原来的曲线,用近似曲线
18、的极小点 来估计原来的极小点.下面我们将分别具体介绍几种方法:一.平分法 根据以前我们所学习的知识,我们知道,在 的极小点 处 有,并且当 时,函数是递减的,即;而 当 时,函数递增,即.注:因为 为极小点,若:此时 为极大点.第五十四张,PPT 共一百三十九页,创作于2022 年6 月 我们找到了一个区间,具有性质 则在 间必然有 的极小点,且.为了找到,我们取.1.若,则在 中有极小点,2.若,则在 中有极小点.y=f(x)00 xy第五十五张,PPT 共一百三十九页,创作于2022 年6 月 若情形1 满足时,此时以 作为新的区间;若情形2 满足时,此时以 作为新的区间.继续上述过程,逐
19、步将区间换小,当区间 充分小时,或者当 充分小时,即可将区间 中点取做极小点的近似,此时有:0 xy0 xy第五十六张,PPT 共一百三十九页,创作于2022 年6 月 注:也可以用以下的收敛准则:1.成立,2.成立.但是我们如何来确定初始区间 呢?下面我们将解决这个问题。第五十七张,PPT 共一百三十九页,创作于2022 年6 月搜索区间 的选取可采用如下的进 退算法:给定初始点,初始步长,求搜索区间:1)计算 2)若,(此时称搜索成功,下一步搜索就大步前进),则步长加倍,计算 若,则;否则步长再加倍,并重复上面的运算;第五十八张,PPT 共一百三十九页,创作于2022 年6 月3)若,(此
20、时称搜索失败,下一步就小步后退),则步长缩为原来的1/4,并改变符号,即新步长为,若 则;否则步长再加倍,继续后退。第五十九张,PPT 共一百三十九页,创作于2022 年6 月二、0.618法(近似黄金分割法)单谷函数退 出前一页后一页第六十张,PPT 共一百三十九页,创作于2022 年6 月搜索法求解:或基本过程:给出a,b,使得t*在a,b中。a,b称为搜索区间。迭代缩短a,b的长度。当a,b的长度小于某个预设的值,或者导数的绝对值小于某个预设的正数,则迭代终止。退 出 前一页后一页第六十一张,PPT 共一百三十九页,创作于2022 年6 月假定:已经确定了单谷区间a,bt1t2ab a
21、bt1t2新搜索区间为a,t2 新搜索区间为t1,b退 出前一页后一页第六十二张,PPT 共一百三十九页,创作于2022 年6 月区间缩小比例的确定:区间缩短比例为(t2-a)/(b-a)缩短比例为(b-t1)/(b-a)缩短比例 满足:每次插入搜索点使得两个区间a,t2和t1,b相等;每次迭代都以相等的比例缩小区间。0.618法t1t2ab a bt1t2退 出 前一页后一页第六十三张,PPT 共一百三十九页,创作于2022 年6 月确定a,b,计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤:是 否是停止,输出t1否以a,t2为新的搜索区间是停止,
22、输出t2否以t1,b为新的搜索区间退 出 前一页后一页第六十四张,PPT 共一百三十九页,创作于2022 年6 月例:解:t1t2 30 t1、第一轮:t1=1.146,t2=1.854t200.5退 出 前一页后一页第六十五张,PPT 共一百三十九页,创作于2022 年6 月2、第二轮:t2=1.146,t1=0.708t20=1.1460.53、第三轮:t1=0.438,t2=0.708b-t1=1.146-0.4380.51.8540 t t2t11.4160 tt2t1退 出前一页后一页第六十六张,PPT 共一百三十九页,创作于2022 年6 月4、第四轮:t2=0.876,t1=0.
23、708b-t1=1.146-0.7080.5输出:t*=t2=0.876为最优解,最优值为-0.079801.416tt1t2退 出前一页后一页第六十七张,PPT 共一百三十九页,创作于2022 年6 月68例 求解 f(x)=-18x2+72x+28 的极大值点,0.1,起始搜索区间为0,3解:用间接法:令 f(x)=-36x+72=0,得驻点 x=2 又因为f(x)=-360,故 x=2 为f(x)的极大值点,fmax=100 用直接法中的黄金分割法:令 n-1=,得n=1+(lg)/(lg)5.78442 约6步即可,计算结果见下表:kakbkf(ak)f(bk)pk=bk-akpk/p
24、0 x1k=ak+pkx2k=bk-pkf(x2k)f(x1k)0 0 3 28 82 3 1 1.854 1.146 86.999.62f(x)xo3x1x21 1.146 3 86.9 82 1.854 0.618 2.292 1.854 99.62 98.462 1.1462.292 86.9 98.461.146 0.382 1.854 1.584 96.8999.623 1.5842.292 96.89 98.460.708 0.236 2.022 1.854 99.62 99.994 1.8542.292 99.62 98.460.438 0.146 2.125 2.022 99.
25、99 98.725 1.8542.125 99.62 99.720.2710.0903第六十八张,PPT 共一百三十九页,创作于2022 年6 月第六十九张,PPT 共一百三十九页,创作于2022 年6 月第七十张,PPT 共一百三十九页,创作于2022 年6 月第七十一张,PPT 共一百三十九页,创作于2022 年6 月第七十二张,PPT 共一百三十九页,创作于2022 年6 月三、Newton法 Newton法基本思想:用探索点tk处的二阶Taylor展开式近似代替目标函数,以展开式的最小点为新的探索点。退 出前一页后一页第七十三张,PPT 共一百三十九页,创作于2022 年6 月解题步骤
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 无约束 非线性 规划 PPT 课件
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内