无约束非线性规划精选PPT.ppt

关于无约束非线性规划第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 构件容积问题构件容积问题第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时，称为时，称为无约束非线性规划无约束非线性规划或者或者无约束最优无约束最优化问题化问题。否则，称为否则，称为约束非线性规划约束非线性规划或者或者约束最优化问题约束最优化问题。第9页，讲稿共139张，创作于星期二最优解和极小点最优解和极小点第10页，讲稿共139张，创作于星期二最优解和极小点最优解和极小点第11页，讲稿共139张，创作于星期二极值存在的条件极值存在的条件必必要要条条件件：设设是是n n维维欧欧氏氏空空间间的的某某一一区区域域，f(X)f(X)为为定定义义在在上上的的实实值值函函数数，是是区区域域的的内内点点，若若f(f(）在在处处可可微微，且且在该点取得局部极小值，则必有在该点取得局部极小值，则必有或或第12页，讲稿共139张，创作于星期二极值存在的条件极值存在的条件其中，其中，为为函函数数f(x)f(x)在在处处的的梯梯度度，梯梯度度的的方方向向为为f(X)f(X)的的等等值值面面（等等值值线线）的的法法线线方方向向，沿沿这这个方向函数值增加最快个方向函数值增加最快满满足足上上式式的的点点称称为为驻驻点点，在在区区域域内内部部，极极值点必为驻点；但驻点不一定是值点必为驻点；但驻点不一定是极值点极值点第13页，讲稿共139张，创作于星期二14二次型二次型二次型是X=(x1,x2,xn)T的二次齐次函数：aij=aji,A为n*n对称矩阵。若A的所有元素均为实数，则为实二次型。一个二次型唯一对应一个对称矩阵，反之，一个对称矩阵也唯一确定一个二次型。二次型（对称矩阵）正定，负定，不定。半正定，半负定。第14页，讲稿共139张，创作于星期二15二次型二次型二次型正定的充要条件，是它的矩阵的左上角各阶主子式都大于零。二次型负定的充要条件，是它的矩阵的左上角各阶主子式都负、正相间。例：判定正负性。第15页，讲稿共139张，创作于星期二极值存在的条件极值存在的条件充充分分条条件件：设设是是n n维维欧欧氏氏空空间间的的某某一一区区域域，f(X)f(X)为为定定义义在在上上的的实实值值函函数数，是是区区域域的的内内点点，f(f(）在在上上二二次次连连续续可可微微，若若f(）在在且且处处满满足足（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张，创作于星期二极值存在的条件极值存在的条件又因为又因为所以所以即为即为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的极小点，即：的极小点，即：故驻点（，）不是极值点，而是一个鞍点故驻点（，）不是极值点，而是一个鞍点第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张，创作于星期二凸函数和凸规划凸函数和凸规划凸函数及其性质凸函数及其性质凸规划及其性质凸规划及其性质第23页，讲稿共139张，创作于星期二凸函数及其性质凸函数及其性质第24页，讲稿共139张，创作于星期二凸函数的性质凸函数的性质第25页，讲稿共139张，创作于星期二凸函数的判定凸函数的判定第26页，讲稿共139张，创作于星期二第27页，讲稿共139张，创作于星期二凸函数的判定凸函数的判定例例4 4 判定下述函数是凸函数还是凹函数判定下述函数是凸函数还是凹函数解解:因为因为其海赛阵的行列式为：其海赛阵的行列式为：故其海赛阵处处正定，由定理故其海赛阵处处正定，由定理2.2.42.2.4得得f(X)f(X)为严格凸函数为严格凸函数第28页，讲稿共139张，创作于星期二凸函数的判定凸函数的判定例例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(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张，创作于星期二凸规划及其性质凸规划及其性质约束集如果如果(MP)的约束集的约束集X是凸集，目标函数是凸集，目标函数f是是X上的凸函数，则上的凸函数，则(MP)叫做叫做非线性凸非线性凸规划规划，或简称为，或简称为凸规划凸规划。第33页，讲稿共139张，创作于星期二定理定理 2.2.6 凸规划的任一局部最优解都是凸规划的任一局部最优解都是它的整体最优解。它的整体最优解。第34页，讲稿共139张，创作于星期二凸规划及其性质凸规划及其性质由于线性函数也既是凸函数，又是凹函数，由于线性函数也既是凸函数，又是凹函数，故线性规划也属于凸规划故线性规划也属于凸规划第35页，讲稿共139张，创作于星期二凸规划及其性质凸规划及其性质例例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.)=3.8.g1(X)g2(X)=0C目标函数等值线目标函数等值线第37页，讲稿共139张，创作于星期二算法及有关概念算法及有关概念最优化问题的数值解法及理论根据：最优化问题的数值解法及理论根据：1 在集合上的迭代算法是指：在集合上的迭代算法是指：开始：选定一个初始点开始：选定一个初始点 ,置置k=0,然后再按某种规则把然后再按某种规则把k次迭代的次迭代的x(k)映射为新映射为新的一点的一点x(k+1),记为这称为第记为这称为第k+1次迭次迭代这个过程无限进行下去，就产生一个点列代这个过程无限进行下去，就产生一个点列，其中规则称为算法若收敛于问题的，其中规则称为算法若收敛于问题的最优解，就称算法在上是收敛的，否则是最优解，就称算法在上是收敛的，否则是发散的发散的第38页，讲稿共139张，创作于星期二算法及有关概念算法及有关概念一种算法除了满足计算终止准则的迭代点外一种算法除了满足计算终止准则的迭代点外,还还应满足应满足:下降算法下降算法:若对于每个若对于每个k,都有都有 ,则称则称A为为下降迭代算法下降迭代算法,简称下降算法简称下降算法.许多最优化方法都采用将多维问题转化为一维许多最优化方法都采用将多维问题转化为一维问题的方法来求解问题的方法来求解.第39页，讲稿共139张，创作于星期二算法及有关概念算法及有关概念 如如:设第设第k次迭代点次迭代点xk已求得已求得,若它不满足终止准若它不满足终止准则则,在该点必存在下降方向在该点必存在下降方向.对于可微目标函数对于可微目标函数,即即是满足是满足 的的d.按某种规则从中选取一个按某种规则从中选取一个,例如例如dk,再沿这个方向再沿这个方向适当迈进一步适当迈进一步,即在直线即在直线 上适当确定一个上适当确定一个新点新点 ,使使 那我们就说完成了第那我们就说完成了第k+1次迭代次迭代,其中其中 称为步长因子称为步长因子.第40页，讲稿共139张，创作于星期二算法及有关概念算法及有关概念迭代过程中应满足两个准则迭代过程中应满足两个准则:1 是下降方向是下降方向dk的选取的选取;2是步长因子是步长因子 的选取的选取 各种迭代法的区别就在于得出方向各种迭代法的区别就在于得出方向 dk 与步与步 长长 的方式不同的方式不同.对于非线性规划对于非线性规划,总结出总结出:第41页，讲稿共139张，创作于星期二非线性规划方法概述非线性规划方法概述第42页，讲稿共139张，创作于星期二非线性规划基本迭代格式非线性规划基本迭代格式第43页，讲稿共139张，创作于星期二无约束优化无约束优化:最优解的分类和条件最优解的分类和条件给定一个函数给定一个函数 f(x),),寻找寻找 x*使得使得 f(x*)最小，即最小，即其中其中局部最优解局部最优解全局最优解全局最优解必要条件必要条件x*f(x)xlxgo充分条件充分条件Hessian阵阵最优解在可行域边界上取得时不能用无约束优化方法求解最优解在可行域边界上取得时不能用无约束优化方法求解第44页，讲稿共139张，创作于星期二2 2 迭代法中直线搜索及其性质：迭代法中直线搜索及其性质：在搜索方向已经确定的前提下在搜索方向已经确定的前提下,步长因子的选步长因子的选取有多种方法取有多种方法,如如 i)取步长因子为某个常数取步长因子为某个常数,但不能保证使目标函但不能保证使目标函数值下降数值下降;ii)可接受点算法，只要能使目标函数下降，可可接受点算法，只要能使目标函数下降，可任意选取步长任意选取步长;iii)基于沿搜索方向使目标函数值下降最多，基于沿搜索方向使目标函数值下降最多，沿射线沿射线 求目标函数的极小值：求目标函数的极小值：第45页，讲稿共139张，创作于星期二2 2 迭代法中直线搜索及其性质：迭代法中直线搜索及其性质：由于这项工作是求以为变量的一元函数由于这项工作是求以为变量的一元函数的极小点，故称这一过程为的极小点，故称这一过程为一维搜索一维搜索（线搜索线搜索），这），这样确定的步长为样确定的步长为最佳步长最佳步长,实际计算中常用此方法实际计算中常用此方法.一维搜索有个性质：在搜索方向上所得最优点处一维搜索有个性质：在搜索方向上所得最优点处的梯度和搜索方向正交的梯度和搜索方向正交定理：设目标函数定理：设目标函数f(X)具有一阶连续偏导数，具有一阶连续偏导数，x(k+1)按下列规划产生：按下列规划产生：则有则有第46页，讲稿共139张，创作于星期二3 3 收敛速度收敛速度 一一个个算算法法不不光光能能收收敛敛于于解解,还还必必须须以以较较快的速度收敛于解快的速度收敛于解,这才是这才是好的算法好的算法;我我们们用用以以下下收收敛敛的的阶阶来来度度量量一一个个算算法法的的收敛速度收敛速度.第47页，讲稿共139张，创作于星期二3 3 收敛速度收敛速度 定义定义:设序列设序列 收敛于收敛于 ,而且而且 若若 ,则称则称 为为线性收敛线性收敛的的,为为收敛比收敛比;若若 ,则称则称 为为超线性收敛超线性收敛.定义定义:设序列设序列 收敛于收敛于 ,若对于某个实若对于某个实数数 ,有有 则称序列则称序列 为为 阶收敛的阶收敛的第48页，讲稿共139张，创作于星期二3 3 收敛速度收敛速度 一一般般来来说说,线线性性收收敛敛是是比比较较慢慢的的,而而二二阶阶收收敛敛则则是是很很快快的的,超超线线性性收收敛敛居居中中,如如果果一一个个算算法法具具有有超超线线性性以以上上的的收收敛敛速速度度,我我们们就认为它是一个很好的算法了就认为它是一个很好的算法了.第49页，讲稿共139张，创作于星期二50因真正的极值点事先并不知道，故在实用上只能根据相继两次迭代得到的计算结果来判断是否已达到要求，从而建立终止迭代计算的准则。常用的终止迭代准则有：（1）根据相继两次迭代结果的绝对误差。4.终止迭代准则终止迭代准则（2）根据相继两次迭代结果的相对误差。（3）根据函数梯度的模足够小。迭代终止准则 点距准则 函数值下降准则 梯度准则第50页，讲稿共139张，创作于星期二2.2 一维搜索方法一维搜索方法精确一维搜索方法精确一维搜索方法 0.618法法 Newton法法非精确一维搜索方法非精确一维搜索方法 Goldstein法法 Armijo法法第51页，讲稿共139张，创作于星期二一维搜索一维搜索 上节提到上节提到,在大多数无约束极值的算法中在大多数无约束极值的算法中,为了确定最为了确定最优解优解,一般用解析的方法是很难得到的一般用解析的方法是很难得到的,即精确解通常是即精确解通常是计算不出来的计算不出来的,故我们常采用的是数值的方法来得到其故我们常采用的是数值的方法来得到其近似解近似解,上节我们提到上节我们提到,数值解法最常用的一种方法是迭数值解法最常用的一种方法是迭代法代法.为了确定极小化点列为了确定极小化点列,要沿逐次确定的系列射线求要沿逐次确定的系列射线求极小点极小点,即所谓的一维搜索即所谓的一维搜索.一一维维搜搜索索可可归归结结为为单单变变量量函函数数求求极极小小的的问问题题,设设目目标标函函数数为为 ,过过点点 沿沿方方向向 的的直直线线可可用用点点集集表表示示为为:第52页，讲稿共139张，创作于星期二 求 在直线L上的极小点转化为求一元函数 的极小点.如果 的极小点为 ,通常称 为沿方向 的步长因子 或简称步长.函数 在直线上的极小点就是 一维搜索的方法一般有以下几类：1.数学分析中所讲的方法，即解方程，此方法称为精确线性搜解方程，此方法称为精确线性搜索索.2.试探法试探法:按照某种方式试探点,通过一系列试探点的比较确定极小点.第53页，讲稿共139张，创作于星期二 3.函数逼近法函数逼近法:用比较简单的曲线近似代替原来的曲线,用近似曲线的极小点 来估计原来的极小点.下面我们将分别具体介绍几种方法:一.平分法 根据以前我们所学习的知识,我们知道，在 的极小点 处 有 ,并且当 时,函数是递减的,即 ;而 当 时,函数递增,即 .注:因为 为极小点,若:此时 为极大点.第54页，讲稿共139张，创作于星期二 我们找到了一个区间 ,具有性质 则在 间必然有 的极小点 ,且 .为了找到 ,我们取 .1.若 ,则在 中有极小点,2.若 ,则在 中有极小点.y=f(x)00 xy第55页，讲稿共139张，创作于星期二 若情形1满足时,此时以 作为新的区间;若情形2满足时,此时以 作为新的区间.继续上述过程,逐步将区间换小,当区间 充分小时,或者当 充分小时,即可将区间 中点取做极小点的近似,此时有:0 xy0 xy第56页，讲稿共139张，创作于星期二 注:也可以用以下的收敛准则:1.成立,2.成立.但是我们如何来确定初始区间 呢?下面我们将解决这个问题。第57页，讲稿共139张，创作于星期二搜索区间 的选取可采用如下的进退算法：给定初始点 ，初始步长 ，求搜索区间 ：1）计算 2）若 ,(此时称搜索成功，下一步搜索就大步前进)，则步长加倍，计算 若 ，则 ；否则步长再加倍，并重复上面的运算；第58页，讲稿共139张，创作于星期二3）若 ,(此时称搜索失败，下一步就小步后退),则步长缩为原来的1/4，并改变符号，即新步长为 ，若 则 ；否则步长再加倍，继续后退。第59页，讲稿共139张，创作于星期二二、二、0.618法（近似黄金分割法）法（近似黄金分割法）单谷函数单谷函数退 出前一页后一页第60页，讲稿共139张，创作于星期二搜索法求解：搜索法求解：或或基本过程：基本过程：给出给出a,b,使得使得t*在在a,b中。中。a,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,b的长度。的长度。当当a,b的长度小于某个预设的值，或者导数的绝对值的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。小于某个预设的正数，则迭代终止。退 出前一页后一页第61页，讲稿共139张，创作于星期二假定：已经确定了单谷区间假定：已经确定了单谷区间a,bt1t2ababt1t2新搜索区间为新搜索区间为a,t2新搜索区间为新搜索区间为t1,b退 出前一页后一页第62页，讲稿共139张，创作于星期二区间缩小比例的确定：区间缩小比例的确定：区间缩短比例为区间缩短比例为(t2-a)/(b-a)缩短比例为缩短比例为(b-t1)/(b-a)缩短比例缩短比例 满足：满足：每次插入搜索点使得两个区间每次插入搜索点使得两个区间a,t2和和t1,b相等；相等；每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。0.618法法t1t2ababt1t2退 出前一页后一页第63页，讲稿共139张，创作于星期二确定确定a,b,计算探索点计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤：法解题步骤：是是否否是是停止，输出停止，输出t1否否以以a,t2为新的搜索区间为新的搜索区间是是停止，输出停止，输出t2否否以以t1,b为新的搜索区间为新的搜索区间退 出前一页后一页第64页，讲稿共139张，创作于星期二例：例：解：解：t1t230t1、第一轮：、第一轮：t1=1.146,t2=1.854t200.5退 出前一页后一页第65页，讲稿共139张，创作于星期二2、第二轮：、第二轮：t2=1.146,t1=0.708t20=1.1460.53、第三轮：、第三轮：t1=0.438,t2=0.708b-t1=1.146-0.4380.51.8540tt2t11.4160tt2t1退 出前一页后一页第66页，讲稿共139张，创作于星期二4、第四轮：、第四轮：t2=0.876,t1=0.708b-t1=1.146-0.7080.5输出：输出：t*=t2=0.876为最优解，最优值为为最优解，最优值为-0.079801.416tt1t2退 出前一页后一页第67页，讲稿共139张，创作于星期二68例例 求解求解 f(x)=-18xf(x)=-18x2 2+72x+28+72x+28 的极大值点，的极大值点，0.10.1，起始搜索区间为，起始搜索区间为0,30,3解：解：用间接法：令用间接法：令 f f(x)=-36x+72=0(x)=-36x+72=0，得驻点，得驻点 x=2x=2 又因为又因为f f(x)=-36(x)=-360 0，故，故 x=2 x=2 为为f(x)f(x)的极大值点，的极大值点，f fmaxmax=100=100 用直接法中的黄金分割法：令用直接法中的黄金分割法：令 n-1n-1=，得，得n=1+(lgn=1+(lg)/)/(lg(lg)5.78442)5.78442 约约6 6步即可，计算结果见下表：步即可，计算结果见下表：ka ak kb bk kf(ak)f(bk)pk=bk-akpk/p0 x x1 1k k=ak+pkx x2 2k k=bk-pkf(x x2 2k k)f(x x1 1k k)0032882311.8541.14686.999.62f(x)f(x)x xo o3 3x x1 1x x2 21 1.146386.9821.8540.6182.2921.85499.62 98.462 1.1462.29286.998.461.1460.3821.8541.58496.8999.623 1.5842.29296.8998.460.7080.2362.0221.85499.62 99.994 1.8542.29299.6298.460.4380.1462.1252.02299.99 98.725 1.8542.12599.6299.720.2710.0903第68页，讲稿共139张，创作于星期二第69页，讲稿共139张，创作于星期二第70页，讲稿共139张，创作于星期二第71页，讲稿共139张，创作于星期二第72页，讲稿共139张，创作于星期二三、三、Newton法法Newton法基本思想：法基本思想：用探索点用探索点tk处的二阶处的二阶Taylor展开式近似代替目标函数，展开式近似代替目标函数，以展开式的最小点为新的探索点。以展开式的最小点为新的探索点。退 出前一页后一页第73页，讲稿共139张，创作于星期二解题步骤：解题步骤：给定初始点给定初始点t1和精度和精度是是是是停止，输出停止，输出t1是是否否停止，解题失败停止，解题失败否否停止，输出停止，输出t2否否退 出前一页后一页第74页，讲稿共139张，创作于星期二例：例：解：解：取取t1=1,计算：计算：迭代过程如下表：迭代过程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退 出前一页后一页第75页，讲稿共139张，创作于星期二第76页，讲稿共139张，创作于星期二3、非精确一维搜索法、非精确一维搜索法数值方法的关键是从一个点迭代到下一个点。数值方法的关键是从一个点迭代到下一个点。确定下一个点的关键是确定搜索方向和步长确定下一个点的关键是确定搜索方向和步长如果已经确定了搜索方向如果已经确定了搜索方向pk,则只要确定一个最佳的步则只要确定一个最佳的步长即可。长即可。所谓的最佳步长即是在所谓的最佳步长即是在pk方向上走一个最好的长度使得方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：目标函数下降的最多，即下述的最优化问题：这样的最优化问题不需要太高的精度，只要满足某这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。些更宽松的精度要求即可。这样的搜索方法称之为这样的搜索方法称之为非精确一维搜索方法非精确一维搜索方法退 出前一页后一页第77页，讲稿共139张，创作于星期二Goldstein法原理：法原理：yt0bcdaY=(0)+(0)tY=(0)+m2(0)tY=(0)+m1(0)t退 出前一页后一页第78页，讲稿共139张，创作于星期二是是Goldstein算法算法确定确定m1,m2,t0,a=0,b=+(t0)(0)+m1 (0)t0(t0)(0)+m2(0)t0是是停止停止,输出输出t0否否a=a,b=t0,t1=(a+b)/2否否a=t0,b=b,t1=(a+b)/2(若若b=+,则则t1=a)退 出前一页后一页第79页，讲稿共139张，创作于星期二Goldstein法步骤法步骤第80页，讲稿共139张，创作于星期二Armijo法法第81页，讲稿共139张，创作于星期二82无约束条件下多变量函数寻优无约束条件下多变量函数寻优一、爬山法原理：一、爬山法原理：通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。由以下二部分组成：由以下二部分组成：选定搜索方向；选定搜索方向；在选定的方向上爬山搜索。在选定的方向上爬山搜索。二、变量轮换法二、变量轮换法(或降维法或降维法):):选择与坐标轴平行的方向为搜索方向选择与坐标轴平行的方向为搜索方向 设设 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)，极值点存在的区间为，极值点存在的区间为 x x1 1*aa1 1,b,b1 1，x x2 2*aa2 2,b,b2 2，x xn n*aan n,b,bn n 1 1、原理：、原理：从起点从起点 X X(0)(0)出发，沿平行于出发，沿平行于 x x1 1 轴的方向轴的方向P P(1)(1)进行一维搜索，进行一维搜索，求得求得 f(X)f(X)在该方向在该方向P(1)P(1)上近似极值点上近似极值点 X X(1)(1)；从点从点 X X(1)(1)出发，沿平行于出发，沿平行于 x x2 2 轴的方向轴的方向P P(2)(2)进行一维搜索，进行一维搜索，求得求得 f(X)f(X)在该方向在该方向P(2)P(2)上近似极值点上近似极值点 X X(2)(2)；从点从点 X X(2)(2)出发，照此交替进行下去，直至满足给定的精度出发，照此交替进行下去，直至满足给定的精度 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|第82页，讲稿共139张，创作于星期二83 2 2、算法步骤：、算法步骤：设设 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2)，极值点存在的区间为，极值点存在的区间为x x1 1*aa1 1,b,b1 1，x x2 2*aa2 2,b,b2 2 第一步：从第一步：从 X X(0)(0)=(x=(x1 1(0)(0),x,x2 2(0)(0)T T出发出发 先固定先固定x x1 1=x=x1 1(0)(0):求以求以x x2 2为单变量的目标函数的极值点，为单变量的目标函数的极值点，得得 X X(1)(1)=(x=(x1 1(0)(0),x,x2 2(1)(1)T T ，S S(1)(1)=f(X=f(X(1)(1)再固定再固定x x2 2=x=x2 2(1)(1):求以求以x x1 1为单变量的目标函数的极值点，为单变量的目标函数的极值点，得得 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(1)T T ，S S(2)(2)=f(X=f(X(2)(2)此时此时S S(2)(2)优于优于S S(1)(1)，且搜索区间缩短为，且搜索区间缩短为x x1 1*x x1 1(2)(2),b,b1 1，x x2 2*x x2 2(1)(1),b,b2 2 第二步：如此交替搜索，直至满足给定精度第二步：如此交替搜索，直至满足给定精度 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2第83页，讲稿共139张，创作于星期二84例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x-10 x1 1-4x-4x2 2+60+60 的极小值点，的极小值点，=0.01=0.01解：设起始点解：设起始点 X X(0)(0)=(0,0)=(0,0)T T，用变量轮换法，用变量轮换法计算：计算：先固定先固定x x1 1=x=x1 1(0)(0)=0:=0:则则 f(0,x2)=x22-4x2+60，寻优得寻优得 x x2 2(1)(1)=2=2 于是于是 X X(1)(1)=(x=(x1 1(0)(0),x,x2 2(1)(1)T T=(0,2)=(0,2)T T ，S S(1)(1)=f(X=f(X(1)(1)=56)=56 再固定再固定x x2 2=x=x2 2(1)(1)=2:=2:则则 f(x1,2)=x12-12x1+56，寻优得寻优得 x x1 1(2)(2)=6=6 于是于是 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(1)T T=(6,2)=(6,2)T T ，S S(2)(2)=f(X=f(X(2)(2)=20)=20 如此交替搜索，直至满足给定精度如此交替搜索，直至满足给定精度 =0.01=0.01 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|0.01 0.01 或或|S|S(k)(k)-S-S(k-1)(k-1)|0.010.01 最后得极小点最后得极小点 X X*=(8,6)=(8,6)T T，f(Xf(X*)=8)=8o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2计算结果见下表：计算结果见下表：第84页，讲稿共139张，创作于星期二85k固定的固定的x xi i单变量的目标函数单变量的目标函数f(xj)求得极点求得极点xj目标值目标值S S(k)(k)|S|S(k)(k)-S S(k-1)(k-1)|12345678x x1 1=x=x1 1(0)(0)=0=0 x x2 2=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=x=x1 1(4)(4)=7.5=7.5x x2 2=x=x2 2(5)(5)=5.75=5.75x x1 1=x=x1 1(6)(6)=7.88=7.88x x2 2=x=x2 2(7)(7)=5.94=5.94f(0,x2)=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 x x2 2=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=x=x1 1(4)(4)=7.5=7.5x x2 2=x=x2 2(5)(5)=5.75=5.75x x1 1=x=x1 1(6)(6)=7.875=7.875x x2 2=x=x2 2(7)(7)=5.94=5.94x x1 1=x=x1 1(8)(8)=7.97=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2缺点缺点：很大程度上取决于目标函数性质。很大程度上取决于目标函数性质。目标函数等高线的性质很重要。目标函数等高线的性质很重要。道路迂回曲折，多次变换方向，道路迂回曲折，多次变换方向，在极点附近，目标值改进更小，在极点附近，目标值改进更小，收敛速度慢。故不是一个有利方向。收敛速度慢。故不是一个有利方向。第85页，讲稿共139张，创作于星期二最速下降法第86页，讲稿共139张，创作于星期二是是X(k)处函数值下降最快的方向。处函数值下降最快的方向。当当 时，时，p(k)是是 f(X)在在 X(k)处的处的下降方向下降方向。函数函数f(X)在在X(k)处的负梯度方向处的负梯度方向梯度的性质：梯度的性质：1 1、迭代原理、迭代原理证明：证明：结论：结论：一元函数泰勒公式：一元函数泰勒公式：第87页，讲稿共139张，创作于星期二2.2.迭代原理迭代原理最优步长最优步长第88页，讲稿共139张，创作于星期二最速下降法迭代原理：最速下降法迭代原理：一维搜索找极小点一维搜索找极小点 ：1)确定确定0,1,精度精度0.1 2)用用0.618法得到法得到 040.53184第89页，讲稿共139张，创作于星期二最速下降法迭代原理：最速下降法迭代原理：第90页，讲稿共139张，创作于星期二线性规划3-42.2.迭代原理迭代原理最优步长最优步长最优步长最优步长第91页，讲稿共139张，创作于星期二线性收敛线性收敛2.2.迭代原理迭代原理最优步长最优步长最优步长最优步长得到一个点列：得到一个点列：可以证明：可以证明：第92页，讲稿共139张，创作于星期二2.2.迭代原理迭代原理证明：证明：第93页，讲稿共139张，创作于星期二3.3.迭代步骤迭代步骤第94页，讲稿共139张，创作于星期二3.3.迭代步骤迭代步骤注释：注释：(一阶必要条件一阶必要条件)10 停机准则：停机准则：设设 连续连续(即即 f(X)连续可微连续可微)第95页，讲稿共139张，创作于星期二注释：注释：3.3.迭代步骤迭代步骤一维搜索最优解的梯度一维搜索最优解的梯度 与搜索方向与搜索方向 正交正交20 结论：结论：证明：证明：第96页，讲稿共139张，创作于星期二注释：注释：最速下降法的任何两个相邻搜索方向最速下降法的任何两个相邻搜索方向正交正交(垂直垂直)3.3.迭代步骤迭代步骤30 结论：结论：第97页，讲稿共139张，创作于星期二注释：注释：3.3.迭代步骤迭代步骤40 将一维搜索用于正定二次函数：将一维搜索用于正定二次函数：则可以得到则可以得到 的表达式：的表达式：第98页，讲稿共139张，创作于星期二线性规划3-4证明：证明：3.3.迭代步骤迭代步骤40 将一维搜索用于正定二次函数：将一维搜索用于正定二次函数：则可以得到则可以得到 的表达式：的表达式：注释：注释：该公式具有普遍性该公式具有普遍性第99页，讲稿共139张，创作于星期二注释：注释：3.3.迭代步骤迭代步骤40 将一维搜索用于正定二次函数：将一维搜索用于正定二次函数：则可