《无约束非线性规划PPT课件.ppt》由会员分享，可在线阅读，更多相关《无约束非线性规划PPT课件.ppt（139页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 月解题步骤
26、：给定初始点t1和精度是是停止，输出t1是否停止，解题失败否停止，输出t2否退 出 前一页后一页第七十四张，PPT 共一百三十九页，创作于2022 年6 月例：解：取t1=1,计算：迭代过程如下表：1.137 0.1163 0.1169 3-0.001061 41.3258-0.5178-0.5708 22 0.7854 1 1退 出 前一页 后一页第七十五张，PPT 共一百三十九页，创作于2022 年6 月第七十六张，PPT 共一百三十九页，创作于2022 年6 月3、非精确一维搜索法数值方法的关键是从一个点迭代到下一个点。确定下一个点的关键是确定搜索方向和步长如果已经确定了搜索方向pk,则
27、只要确定一个最佳的步长即可。所谓的最佳步长即是在pk方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。这样的搜索方法称之为非精确一维搜索方法退 出前一页 后一页第七十七张，PPT 共一百三十九页，创作于2022 年6 月 Goldstein法原理：yt 0b c d aY=(0)+(0)tY=(0)+m2(0)tY=(0)+m1(0)t退 出前一页后一页第七十八张，PPT 共一百三十九页，创作于2022 年6 月是Goldstein算法确定m1,m2,t0,a=0,b=+(t0)(0)+m1(0)t0(t0)(
28、0)+m2(0)t0是停止,输出t0否a=a,b=t0,t1=(a+b)/2否a=t0,b=b,t1=(a+b)/2(若b=+,则t1=a)退 出 前一页后一页第七十九张，PPT 共一百三十九页，创作于2022 年6 月Goldstein法步骤第八十张，PPT 共一百三十九页，创作于2022 年6 月Armijo法第八十一张，PPT 共一百三十九页，创作于2022 年6 月82无约束条件下多变量函数寻优一、爬山法原理：通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。由以下二部分组成：选定搜索方向；在选定的方向上爬山搜索。二、变量轮换法(或降维法):选择与坐标轴平行的方向为搜索方向
29、设 S=f(X)=f(x1,x2,xn)，极值点存在的区间为 x1*a1,b1，x2*a2,b2，xn*an,bn1、原理：从起点 X(0)出发，沿平行于 x1 轴的方向P(1)进行一维搜索，求得 f(X)在该方向P(1)上近似极值点 X(1)；从点 X(1)出发，沿平行于 x2 轴的方向P(2)进行一维搜索，求得 f(X)在该方向P(2)上近似极值点 X(2)；从点 X(2)出发，照此交替进行下去，直至满足给定的精度 为止|f(X(k)-f(X(k-1)|或|S(k)-S(k-1)|第八十二张，PPT 共一百三十九页，创作于2022 年6 月83 2、算法步骤：设 S=f(X)=f(x1,x
30、2)，极值点存在的区间为x1*a1,b1，x2*a2,b2 第一步：从 X(0)=(x1(0),x2(0)T出发 先固定x1=x1(0):求以x2为单变量的目标函数的极值点，得 X(1)=(x1(0),x2(1)T，S(1)=f(X(1)再固定x2=x2(1):求以x1为单变量的目标函数的极值点，得 X(2)=(x1(2),x2(1)T，S(2)=f(X(2)此时S(2)优于S(1)，且搜索区间缩短为x1*x1(2),b1，x2*x2(1),b2 第二步：如此交替搜索，直至满足给定精度 为止|f(X(k)-f(X(k-1)|或|S(k)-S(k-1)|ox1X(0)X(1)X(2)X(3)X(
31、4)x2第八十三张，PPT 共一百三十九页，创作于2022 年6 月84例 求 S=f(x)=x12+x22-x1x2-10 x1-4x2+60 的极小值点，=0.01解：设起始点 X(0)=(0,0)T，用变量轮换法计算：先固定x1=x1(0)=0:则 f(0,x2)=x22-4x2+60，寻优得 x2(1)=2 于是 X(1)=(x1(0),x2(1)T=(0,2)T，S(1)=f(X(1)=56 再固定x2=x2(1)=2:则 f(x1,2)=x12-12x1+56，寻优得 x1(2)=6 于是 X(2)=(x1(2),x2(1)T=(6,2)T，S(2)=f(X(2)=20 如此交替搜
32、索，直至满足给定精度=0.01 为止|f(X(k)-f(X(k-1)|0.01 或|S(k)-S(k-1)|0.01 最后得极小点 X*=(8,6)T，f(X*)=8ox1X(0)X(1)X(2)X(3)X(4)x2计算结果见下表：第八十四张，PPT 共一百三十九页，创作于2022 年6 月85k固定的xi单变量的目标函数f(xj)求得极点xj目标值S(k)|S(k)-S(k-1)|12345678x1=x1(0)=0 x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.88x2=x2(7)=5.94f(0,x2)
33、=x22-4x2+60f(x1,2)=x12-12x1+56f(6,x2)=x22-10 x2+36f(x1,5)=x12-15x1+65f(7.5,x2)=x22 11.5x2+41.25f(x1,5.75)=x12 15.75x1+70.06f(7.88,x2)=x22 11.88x2+43.27f(x1,5.94)=x12 15.94x1+71.50 x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.875x2=x2(7)=5.94x1=x1(8)=7.975620118.758.18758.04698.0
34、1178.00293692.250.56250.14060.03520.0088ox1X(0)X(1)X(2)X(3)X(4)x2缺点：很大程度上取决于目标函数性质。目标函数等高线的性质很重要。道路迂回曲折，多次变换方向，在极点附近，目标值改进更小，收敛速度慢。故不是一个有利方向。第八十五张，PPT 共一百三十九页，创作于2022 年6 月最速下降法第八十六张，PPT 共一百三十九页，创作于2022 年6 月是X(k)处函数值下降最快的方向。当 时，p(k)是 f(X)在 X(k)处的下降方向。函数f(X)在X(k)处的负梯度方向梯度的性质：1、迭代原理证明：结论：一元函数泰勒公式：第八十七张
35、，PPT 共一百三十九页，创作于2022 年6 月2.迭代原理最优步长第八十八张，PPT 共一百三十九页，创作于2022 年6 月最速下降法迭代原理：一维搜索找极小点：1)确定0,1,精度0.1 2)用0.618法得到 0 40.5 31 84第八十九张，PPT 共一百三十九页，创作于2022 年6 月最速下降法迭代原理：第九十张，PPT 共一百三十九页，创作于2022 年6 月线性规划3-42.迭代原理最优步长最优步长第九十一张，PPT 共一百三十九页，创作于2022 年6 月线性收敛2.迭代原理最优步长最优步长得到一个点列：可以证明：第九十二张，PPT 共一百三十九页，创作于2022 年6
36、 月2.迭代原理证明：第九十三张，PPT 共一百三十九页，创作于2022 年6 月3.迭代步骤第九十四张，PPT 共一百三十九页，创作于2022 年6 月3.迭代步骤注释：(一阶必要条件)10 停机准则：设 连续(即 f(X)连续可微)第九十五张，PPT 共一百三十九页，创作于2022 年6 月注释：3.迭代步骤一维搜索最优解的梯度 与搜索方向 正交20 结论：证明：第九十六张，PPT 共一百三十九页，创作于2022 年6 月注释：最速下降法的任何两个相邻搜索方向正交(垂直)3.迭代步骤30 结论：第九十七张，PPT 共一百三十九页，创作于2022 年6 月注释：3.迭代步骤40 将一维搜索用
37、于正定二次函数：则可以得到 的表达式：第九十八张，PPT 共一百三十九页，创作于2022 年6 月线性规划3-4证明：3.迭代步骤40 将一维搜索用于正定二次函数：则可以得到 的表达式：注释：该公式具有普遍性第九十九张，PPT 共一百三十九页，创作于2022 年6 月注释：3.迭代步骤40 将一维搜索用于正定二次函数：则可以得到 的表达式：第一百张，PPT 共一百三十九页，创作于2022 年6 月注释：3.迭代步骤50 最速下降法，Newton法，拟Newton法，共轭梯度法的区别就是搜索方向p(k)取得不同。第一百零二张，PPT 共一百三十九页，创作于2022 年6 月4.举例例3-10解：
38、用最速下降法求 的极小点，迭代两次。第一百零三张，PPT 共一百三十九页，创作于2022 年6 月 例:试用最速下降法求 的极小点,迭代两次,计算每个迭代点的函数值,梯度及模,并验证相邻两个搜索方向是正交的.解:给初始点,利用必要条件：第一百零四张，PPT 共一百三十九页，创作于2022 年6 月 于是：由 解得 第一百零五张，PPT 共一百三十九页，创作于2022 年6 月验证搜索方向的正交性:第一百零六张，PPT 共一百三十九页，创作于2022 年6 月107例 求 S=f(x)=x12+x22-x1x2-10 x1-4x2+60 的极小值点，=0.1解:从点 X(1)出发，照此进行下去，
39、直至满足给定的精度=0.1 为止|f(X(k+1)-f(X(k)|0.1 或|G(k)|0.1 第一百零七张，PPT 共一百三十九页，创作于2022 年6 月108计算结果见下表：缺点：搜索效果比变量轮换法快，但愈接近极值 点，步长愈小，目标值改进愈小。当遇到强交互作用时，不是有效的方法;当遇到山脊时，会慢慢爬行。在远离极点时，收敛速度较快;在极点附近，收敛速度不快。k01234507.636.817.957.827.9903.055.115.565.875.93-102.21-1.490.33-0.220.05-4-5.53-0.60-0.82-0.09-0.1210.775.591.600
40、.890.240.13-0.930.37-0.930.37-0.930.37-0.37-0.93-0.37-0.93-0.37-0.9288.222.211.220.330.180.056015.749.158.178.038.003744.266.590.980.140.026ox1x(0)x(1)x(2)X(3)x2第一百零八张，PPT 共一百三十九页，创作于2022 年6 月第一百零九张，PPT 共一百三十九页，创作于2022 年6 月110四、共轭梯度法:选择共轭方向为搜索方向 问题的提出：在极值点附近，如何加快收敛速度，须对函数在极值点附近的性质进行研究。设有n维目标函数 S=f(X
41、)=f(x1,x2,xn),在极值点X*附近展开成泰勒级数：特别：对二元二次函数，可证明：在极值点附近，其等高线可近似视为同心 椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。ox1X(0)P(0)X(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)与P(0)共轭故：在极值点附近，沿搜索方向P(0)上巳得到一个 切点X(1)，则只要得出通过极值点的连线方向 P(1),在此方向上寻优,可一步直达极值点。而这个连线方向P(1)是上一次搜索方向P(0)的 共轭方向。第一百一十张，PPT 共一百三十九页，创作于2022 年6 月111 共轭方向的定义：1、定义：设
42、X,Y 是n维向量空间En中两个向量，A 为nn对称正定矩阵，若 XTAY=0，则称向量X与Y对于矩阵A共轭。特例：若 A=I，得 XTY=0，则称向量X与Y正交。2、几何意义：共轭方向是通过极值点的方向。寻优原理：设n元函数 S=f(X)=f(x1,x2,xn),在极值点X*附近可用一个二次函数逼近其中 H 为nn对称正定矩阵第一百一十一张，PPT 共一百三十九页，创作于2022 年6 月112特别：对二元二次函数 S=f(X)=f(x1，x2)从某点X(0)出发,以P(0)方向搜索,使f(X)达到极小值点X(1),则:X(1)必为该点处等高线的切点,P(0)为切线方向，且点X(1)的梯度方
43、向 f(X(1)为该等高线的法线方向，这两个方向正交。从另一点X(0)出发,仍以P(0)方向搜索,使f(X)达到另一个极小值点X(2),则:X(2)也必为该点处等高线的切点,P(0)为切线方向，且点X(2)的梯度方向f(X(2)为该等高线的法线方向，这两个方向正交。ox1X(0)P(0)X(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)与P(0)共轭故:对二元二次函数,只须搜索两个方向P(0)和P(1)就 可达到极值点 X*。一般:对n元二次函数,可用不超过n次搜索就可达到 极值点 X*。而n元非二次函数在极值点附近可用二次函数逼近。第一百一十二张，PPT 共一百三十九页
44、，创作于2022 年6 月113 适用于一般目标函数的共轭梯度法：1、共轭方向的计算问题：须用到目标函数的海赛矩阵H(二阶偏导数矩阵)，若目标函数为二次函数时，H 容易求出；若目标函数为高次或高维函数时，H 难以求出，此时共轭方向难以求出。2、共轭方向的计算方法：F-R 法，由Fletcher和Reeves提出，可避免海赛矩阵 H 的计算，方便地确定共轭方向，简单有效。第一百一十三张，PPT 共一百三十九页，创作于2022 年6 月114 3、搜索过程：从X(0)出发：从X(1)出发：第一百一十四张，PPT 共一百三十九页，创作于2022 年6 月115 从X(2)出发：4、搜索方法:若目标函
45、数为n元二次函数，则理论上最多经 n 次迭代可达极小点，实际由于舍入误差，须n次以上的迭代。若目标函数为n元非二次函数，但共轭方向只有n个，迭代n次以后应 重新开始迭代，减少误差积累。一般，在开始阶段(二次型较弱)用一阶梯度法，接近极点(二次型较强)用共轭梯度法。一般有：第一百一十五张，PPT 共一百三十九页，创作于2022 年6 月第一百一十六张，PPT 共一百三十九页，创作于2022 年6 月117例 求 S=f(x)=x12+x22-x1x2-10 x1-4x2+60 的极小值点。解:第一百一十七张，PPT 共一百三十九页，创作于2022 年6 月 例2 用共轭梯度法求解,取 解:用共轭
46、梯度法的第一步和最速下降法是相同的,故由前例知:第一百一十八张，PPT 共一百三十九页，创作于2022 年6 月 因 为 较 大,还 需 要 迭 代,下 一 探 索 方 向 由 共 轭 梯度并利用 和 组合而成.其中 所以由 第一百一十九张，PPT 共一百三十九页，创作于2022 年6 月 由：把 分别代入 的表达式中求得,因 为,所以迭代终止,就是 所求的极小点.第一百二十张，PPT 共一百三十九页，创作于2022 年6 月共轭梯度法的特点:对于二次函数的情形,从理论上说,进行n次迭代即可达到极小点,但是,在实际计算中,由于数据的舍入以及计算误差积累,往往做不到这一点.由于n维问题的共轭方向
47、最多只有个,在步之后继续如上进行就没有意义.因此,实际计算中如迭代n步还不收敛,就将X(n)作为新的始点,重新开始迭代,这样一般都可得到较好的效果.第一百二十一张，PPT 共一百三十九页，创作于2022 年6 月浙江理工大学经济管理学院1222.4 牛顿法与拟牛顿法 牛顿方向四、牛顿法第一百二十二张，PPT 共一百三十九页，创作于2022 年6 月浙江理工大学经济管理学院123四、牛顿法（1）牛顿方向第一百二十三张，PPT 共一百三十九页，创作于2022 年6 月浙江理工大学经济管理学院1242.3 无约束极值问题四、牛顿法（2）广义牛顿法步骤当一维搜索是精确的，牛顿法为二阶收敛。第一百二十四
48、张，PPT 共一百三十九页，创作于2022 年6 月浙江理工大学经济管理学院1252.3 无约束极值问题四、牛顿法（3）牛顿法优缺点优点：收敛速度快。缺点：有时进行不下去而需采取改进措施；当维数较高时，计算塞黑矩阵的逆工作量太大。可采用其他方法，如共轭梯度法，变尺度法等。第一百二十五张，PPT 共一百三十九页，创作于2022 年6 月 定理5.3：设,且 正定,记 是由修改的牛顿法 所得到的迭代点列,若水平集 有界,则 必有 聚点,且任一聚点 必满足.牛顿法的特征:1.牛顿法应用于具有正定阵 的二次函数时,只要一次迭代就 可以达到无约束优化问题的最优解,即算法具有二次收敛性.2.当初始点接近极
49、小点时,牛顿法产生的序列 以二阶收敛 速度趋于问题的平稳点,但当初始点与极小点较远时,阵 可能是奇异的，牛顿方向不存在,或者 阵不正定,不再是下降方向,此时需要使用改进的牛顿法,其收 敛速度 极大降低,因此,应该 尽可能选取离极小点较远的初始点.3.牛顿法对目标函数要求高(二阶连续可微)且需要较多存储单元,每次迭代要进行矩阵求逆运算.第一百二十六张，PPT 共一百三十九页，创作于2022 年6 月 二.拟牛顿法(变尺度法)修改的牛顿法具有全局收敛性和收敛快的特点,但还存在一个 缺点,即在每步确定搜索方向 时,要计算 阵及其逆矩阵,这个计算工作最大.于是又有一 种设想,将确定搜索方向 公式中的
50、用n 阶矩阵 代 替,从而在第k 次迭代时 由线性搜索得到，其中 和初始矩阵 是预先给定的,在迭代中,利用一阶导数按某中规则得到.第一百二十七张，PPT 共一百三十九页，创作于2022 年6 月 确定 的一种自然想法是将 作为 的近似来 构造,注意到 是对称的,且有关系 即 若记=,必须满足:1.对称正定 2.满足拟牛顿方程(2.30)另外,再设想 是 由经过简单修正而得到的,即 校正矩阵 自然应是对称矩阵,由(2.30)式应满足 第一百二十八张，PPT 共一百三十九页，创作于2022 年6 月(2.31)满足(2.31)的对称矩阵有无穷多个,因此,拟牛顿算法是一族算法,其最常见的算法所谓DF