第三章无约束最优化方法ppt课件.ppt

1,建筑结构优化设计原理,第三章 无约束最优化方法,同济大学土木工程学院建筑工程系杨 彬Course_,2,第三章 无约束最优化方法,最优化的数学模型为 求 min subject to (or s.t.),数学规划方法是在规定的约束条件下，用数学手段直接求目标函数的极大、极小值。特殊情况：,3,1、无约束最优化问题不存在约束条件2、线性规划当目标函数、约束函数均是变量X的线性函数时3、非线性规划当函数中至少有一个是非线性函数时,第三章 无约束最优化方法,4,3-1 无约束最优化方法概述,无约束最优化问题是数学规划的基础。,第三章 无约束最优化方法,求函数 极小值。,无约束最优化问题的定义：求函数 的极小（或极大）值， （ n维欧氏空间）。,5,第三章 无约束最优化方法,根据函数极值条件确定了极小点,则函数f(x)在 附近的一切x均满足不等式,所以函数f(x)在 处取得局部极小值，称 为局部极小点。,而优化问题一般是要求目标函数在某一区域内的全局极小点。,函数的局部极小点是不是一定是全局极小点呢？,一、最优性条件,6,下凸的一元函数,第三章 无约束最优化方法,可以证明凸规划问题的局部最小点就是其全局最小点。,7,凸集,一个点集（或区域），如果连接其中任意两点的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。,第三章 无约束最优化方法,8,凸函数,函数f(x）为凸集定义域内的函数，若对任何的,称,是定义在凸集上的一个凸函数。,第三章 无约束最优化方法,9,第三章 无约束最优化方法,10,凸规划,对于约束优化问题,第三章 无约束最优化方法,11,第三章 无约束最优化方法,设 Q是nn 阶对称矩阵。,若 且 都有 ，则称矩阵Q 是正定的,若 都有 ，则称矩阵Q 是半正定的,若 且 都有 ，则称矩阵Q 是负定的,若 都有 ，则称矩阵Q 是半负定的,一个对称矩阵 是不是正定的，可以用Sylvester定理来判定。,定理(Sylvester ) 一个 nn阶对称矩阵Q 是正定矩阵的充分必要条件是，矩阵Q 的各阶主子式都是正的。,正定矩阵,12,第三章 无约束最优化方法,多元函数的梯度和性质,定义 以 的n偏导数为分量的向量称为 在 x处的梯度，记为 梯度也可以称为函数 关于向量 x的一阶导数。,13,第三章 无约束最优化方法,梯度的性质、函数在某点的梯度若不为零，则必与过该点的等值面“垂直”；、梯度方向是函数具有最大变化率的方向。如图所示，证明上面性质。为了证明性质引入方向导数的概念。,梯度方向与等值面的关系,14,第三章 无约束最优化方法,方向导数,沿d方向的方向向量,即,15,第三章 无约束最优化方法,方向导数的正负决定了函数的升降，而升降的快慢就由它的绝对值大小来决定。方向导数 又称为函数 在点x0 处沿 d方向的变化率。下降最快的方向称为最速下降方向。,16,第三章 无约束最优化方法,Hessian矩阵（函数 的梯度 是它的一阶导数，Hessian矩阵是函数 的二阶导数）,函数 取得极小的充分条件是函数 的Hessian矩阵为正定方阵,17,第三章 无约束最优化方法,方阵 为正定的定义是：若对任何向量d (d!=0)，有,对称正定方阵 的检验方法是所有主子式均大于零。,二、迭代方法,求解,min,的问题可以转变为求解n 元方程组,无约束最优化问题,的问题。一般地，这是一个非线性方程组，可对其采用迭代法求解之。,18,第三章 无约束最优化方法,下降迭代算法,算法：给定目标函数 的极小点的一个初始估计点 ，然后按一定的规则产生一个序列 ，这种规则通常称为算法。如果这个序列的极限恰好是问题（3-1）的极小点 ，即,或等价地,那么就说该算法所产生的序列收敛于,19,第三章 无约束最优化方法,下降迭代法：在给定初始点后，如果每迭代一步都使目标函数有所下降，即 ，那么这种迭代法称为下降法。,假定我们已经迭代到点 处，那么下一步迭代将有以下两种情况之一发生：,、从 出发沿任何方向移动，目标函数不再下降。 是局部极小点，迭代终止。、从 出发至少存在一个方向使目标函数有所下降。这时，从中选定一个下降方向 ，再沿这个方向适当迈进一步，即在直线,20,第三章 无约束最优化方法,上适当选定一个新点,使得,那么就说完成了第 次迭代。上式中的 称为步长因子。,在迭代过程中有两个规则需要确定：一个是下降方向 的选取；一个步长因子 的选取。,21,第三章 无约束最优化方法,下降迭代算法的基本格式如下：,、选定初始点 ，置 ；、按某种规则确定 使得 、按某种规则确定 使得 、计算 、判定 是否满足终止准则，若满足，则打印 和 ，停止迭代计算；否则置 ，转继续迭代。,22,第三章 无约束最优化方法,上述算法可用如下框图表达,23,第三章 无约束最优化方法,三、无约束最优化方法的分类,解析法,直接法,数学模型复杂时不便求解,可以处理复杂函数及没有数学表达式的优化设计问题,直接法: 单变量直接法0.618法，分数法，抛物线法，多项式插值；多变量直接法（爬山法）模态搜索法，方向加速法，单纯形法。,解析法: 函数的导数梯度法，牛顿法，共轭梯度法，变尺度法等。,24,3-2 一维搜索（0.618法）,3-2 一维搜索0.618法,实际问题的最优设计变量很多，经过分析简化，可以只考虑对目标函数影响最大的一个变量，也就是单变量的最优设计问题。,一维搜索就是求一元函数的极小点，即 假定 ，且函数可微，则由极限的必备条件得 一维搜索又称为直线搜索。,25,0.618法 0.618法适用于一般的单峰函数。所谓单峰函数，是指这样的函数：在极小点 的左边，函数是严格减小的；在 的右边，函数是严格增加的。也就是说，若 是任意两点：,当 时，则,当 时，则,3-2 一维搜索（0.618法）,26,从图中可看出，假定不知道极小点 的位置，任取两点 ，如果 ，则 必在 之间；若 ，则 ；若 ，则 。,3-2 一维搜索（0.618法）,27,设给定一个较小的步长，从=0开始，先计算(0)，然后计算在 的函数值()；如果()(0)，则讲步长增大1.618倍，得到一个新点 ,计算(2.618)；如果(2.618)仍小于()，再继续增加步长为原步长的1.618倍，如下图所示，从而得到一系列点的j的值为,3-2 一维搜索（0.618法）,28,在 内任取两点 ，由上面的讨论可以知道，通过比较 与 ，立刻可以断定极小点在区间 内，还是在 内，这样区间被缩小了，新的区间取作 。在 中，又可取两点 ，通过比较函数值得到新的区间 ，这样不断缩小区间，最后便可确定出近似的极小点，如图所示。,3-2 一维搜索（0.618法）,29,应该怎样选取 与 呢？,设区间 的长为1，在与点 相距分别为 和 的点插 和 。为确定 和 ，我们提出一些条件：,第一，希望 和 两点在 中的位置是对称的。这样一来，无论删除哪一段，总是保留长为 的区间（板书所示）。按这一条件有,即,（3-2.1）,3-2 一维搜索（0.618法）,30,第二，无论删除哪一段，例如删除 ，在保留下来的区间里，再插入一个点 使得 ， 在 中 的位置与 和 在 中的位置具有相同的比例。这就保证每次迭代都以同一 的比率缩短区间。按这一条件有,即,（3-2.2）,或,3-2 一维搜索（0.618法）,31,把（3-2.1）代入（3-2.2）中得到关于 的一元二次方程,合理的根是,上述缩短搜索区间的迭代方法称为黄金分割法或优选法。下面介绍它的步骤。,3-2 一维搜索（0.618法）,32,算法（黄金分割法）,已知 ，终止限 。, 确定 的初始搜索区间 ； 计算 ， ； 计算 ， ； 若 ，则打印 ，停机；否则，若 ，转； 判断 是否满足；若满足，则置 然后转；否则，若 ，则置 然后转 。,3-2 一维搜索（0.618法）,33,例3-1 用0.618法求 在区间 上的极小值，要求极小点所在区间长度小于0.05。,解 第一次迭代（板书） 1、在确定区间 内取两个试验点,2、计算函数值,3、比较函数值,3-2 一维搜索（0.618法）,34,是好点，要保留，于是区间缩小为 ，在此区间中，再去找好点。,第一次迭代至此完毕，仿此步骤迭代数次后，得,符合精度要求，无须再迭代。故极小点所在区间为 ，极小值为,3-2 一维搜索（0.618法）,35,3-2 一维搜索（0.618法）,36,例3-2 有一简支鱼腹式金属吊车梁，中心点有一集中荷载 ，求最轻设计的断面值。,3-2 一维搜索（0.618法）,37,由简支梁的弯矩图知,相应的抗弯模量为,3-2 一维搜索（0.618法）,38,化简后得,设梁容重为 ，则梁重为,于是可得问题的数学模型为,3-2 一维搜索（0.618法）,39,求 min s.t.,由约束条件，可以估算出各变量的上下限：,3-2 一维搜索（0.618法）,40,此时,3-2 一维搜索（0.618法）,41,3-2 一维搜索（0.618法）,42,二、抛物线法,假定目标函数 在三点 的函数值分别 ，且有 。利用这三点及相应的函数值作二次插值公式，即令,为所需的插值多项式，它应满足条件：,（3-2.3）,3-2 一维搜索（抛物线法）,43,（3-2.4）,插值多项式（3-2.3）的驻点为,由（3-2.4）解出,（3-2.5）,（3-2.6）,3-2 一维搜索（抛物线法）,44,将上式代入驻点计算式（3-2.5），便得极值公式：,（3-2.7）,当 等距离时，即,式（3-2.7）可简化为,若 ，那么，可把 或 中数值较小的点看作近似的最优解，这里 是要求的精度， 是上一次迭代的最优点。,3-2 一维搜索（抛物线法）,45,搜索区间的缩短, 比较 与 的大小，有两种情况：若 ，则转；否则，若 ，则转；, 若 （ ）与 同时成立，则 ，转；,若 与 同时成立，则 ，转；否则， ，转；, 区间收缩完结。然后转向；计算新的搜索区间 上插值抛物线的极小值 。,3-2 一维搜索（抛物线法）,46,抛物线法并不要求函数一定是单峰函数，但要求函数曲线光滑一些；否则，用抛物线的极值点来近似代替要求值的函数的极值点，效果不理想。,解 设初始点为 ，先确定一个极小点区间，取 ，计算函数值 ， ， ， ，代入公式得,3-2 一维搜索（抛物线法）,例3-3 用0.618法求 在区间 上的极小值，精度为0.01。,47,第二次迭代：取 为新的迭代点， ，代入公式得,依次迭代六次后得,3-2 一维搜索（抛物线法）,48,3-2 一维搜索（抛物线法）,49,3-2 一维搜索（抛物线法）,50,牛顿-芮弗逊迭代法属一点法，每次迭代只用到一点的f()，f()，f()。事实上，在点1附近可用二次函数q()近似f()，且二者在1有相同的函数及一二阶导数值：,然后代为求q()的极小点2，由导数等于零得到：,然后再2代入求新的q(),重复这一过程。注意，如果f()的曲线具有复杂的弯曲，此方法容易失败；另外起始点选择也比较关键。,3-2 一维搜索（牛顿-芮弗逊迭代法）,51,当目标函数二阶导比较难求时，可以用两个点的目标函数值及其导数值来求解。 假定有一个区间1,2,已知f(1)0，(f2)0。；两点格式的核心是逐步缩小区间，其方法是每次迭代时利用下列公式得到一个最小值的新估计：,属于0,1，根据所使用插值公式来定。,新区间由f(3)符号决定，若f(3)0，则新区间取为1,3若f(3)0则新区间取为3,2。然后定义为新区间1,2继续计算下去，直到满足误差限。,3-2 一维搜索（两点格式）,52,常见的决定的方法有弦位法和二分法。弦位法是利用在点1的f(1)及点2的f(2)，对f()进行线性插值：,该式给出f()=0的点的近似值3：,由此得到：,3-2 一维搜索（两点格式）,53,二分法简单地将取成0.5,即,二分法每次将搜索区间长度缩小为原长的一半，所以可以预测要经过多少次迭代才能将区间缩小到制定长度。例如，约经过20次迭代可以将原区间缩小为1/106的长度。,3-2 一维搜索（两点格式）,54,3-3 求多变量极值的直接搜索法,3-3 求多变量极值的直接搜索法,单纯形法,55,所谓单纯形，是在n维空间里对n+1个顶点组成的多面体，如果这个额多面体各边相等，则成为正单纯形。单纯形的优化方法，就是在单纯形的顶点处的函数值进行比较，丢掉其中最坏的点，而代之以新的点，构成新的单纯形。按此顺序，每次把坏的丢掉，好的留下，逐步逼近极小点。,单纯形法第一步是选择一个合理的初始设计x0=(x01,x02x0n)T，并以它为顶点构建边长为a的正单纯形，通常规定其余顶点为： x1=x0+(p,q,q,q)T . xn=x0+(p,q,q,q)T,3-4 无约束优化的单纯形法,56,可以验证该单纯形各边长为a，接着开始迭代过程。,设在第k次迭代得到一个单纯形，其n+1个顶点x0,x1.xn，迭代过程如下：,(1)准备。计算这n+1个顶点处的函数值：比较得到最优点xl、最坏点xh和次坏点xb;,去掉最劣点，把剩下点的形心找出来：,3-4 无约束优化的单纯形法,57,(2)反射。以 为中心将xh反射而得到 ，如图。,经验表明，取a=1较好。计算目标函数在 的值。若 ，即比最好点还好，可让 沿此直线延伸，转入第(3)步；否则转入第(4)步,3-4 无约束优化的单纯形法,58,(3)延伸。让 沿着直线 延伸到 ：,一般取=2较好。然后计算该点处函数值，若 则用 代替 ，得到新的单纯形，然后再返回(1)；反之，说明延伸不成功，退回到 ，返回(1)。,3-4 无约束优化的单纯形法,59,(4)收缩。进入这一步是因为： ，即反射点不比最优点好，有两种可能：1、如果新点比次坏点还差，如果按老套路会出现死循环，故此时，从 和 中挑出一个最坏点并舍弃，如果舍弃 ，则把 收缩到 ：,否则，按下式把 收缩到 ：式中，01，取=0.5较好。,3-3 求多变量极值的直接搜索法,60,如果得到的新点 是最坏点，则说明沿这条线移动希望很小，此时以最好点xl为中心收缩这个单纯形产生一个新的单纯形：2、如果新点 比次坏点好，则有使用价值,则以 来替代 构造新的单纯形。 因此，无论什么情况下，均可以构造出新的单纯形，直到满足迭代结束准则：,3-4 无约束优化的单纯形法,61,下图为在二维情况下单纯形法的示意图，直到x8为止，都是采用反射运算求出新的单纯形，在单纯形x6x7x8中，x7最劣，反射求得x9，但x9次于x6和x8,所以收缩求出x10,.,3-4 无约束优化的单纯形法,62,在应用单纯形法时有三个问题需要注意:(1)单纯形法在迭代过程中,当满足精度要求时,要及时停止迭代,否则迭代点又会跳出去,增加迭代次数.(2)若发生收敛很慢的情况,可能是选取的初值离最优点较远,或单纯形边长取得较小.这时可以加大单纯形边长,或另选初始点,再行迭代.(3)单纯形边长的选取也会影响收敛的快慢.当选取初始点较好,则边长可取小一些,若对选取的初值没有把握,则可以在正式计算前,分别对不同边长进行试算.,3-4 无约束优化的单纯形法,63,3-4 无约束优化的单纯形法,例3-3 用0.618法求 的极小值，x1取值范围为-3,6，x2取值范围为0,4，精度为0.01。,64,3-4 无约束优化的单纯形法,例3-3 用0.618法求 的极小值，x1取值范围为-3,6，x2取值范围为0,4，精度为0.01。,65,3-4 无约束优化的单纯形法,例3-3 用0.618法求 的极小值，x1取值范围为-3,6，x2取值范围为0,4，精度为0.01。,66,作业,3-1 用0.618法求函数 在区间1, 6中的极小值，要求误差,67,（1）梯度的长度已经充分小这意味着在点x(k)处，最优化必要条件已经已足够的精度得到满足。有些情况下，目标函数在极值点附近相当平坦，即使当前设计点和最优点相差很大，但目标值改进的可能性不大，迭代也会停止。（2）前后两次迭代得到的设计点之间的距离充分小,3-5 无约束最优化的解析法,停止迭代准则由于所有的下降算法形成的设计点序列具有下降的目标值，所以只需要检查最优化必要条件 是否满足，便可判断是否得到局部极小点。一般有下三种准则：,68,（3）前后两次迭代目标函数值下降的相对值足够小当在最优点邻近目标函数变化很慢时，和第一准则一样会得到粗糙结果。因此，很多清形下三个准则要结合使用。 大部分工程结构优化问题，在求解最优设计时精度不必要求很高。另外，全局最优问题，可以让迭代算法从几个不同初始设计出发，比较得到。,3-5 无约束最优化的解析法,注意在有的算法中，人为地对设计点移动的步长作了规定，如果规定不够合理就可能出现假收敛：即两次迭代设计点之间距离很小，但并未达到 的点。目标函数在最优点邻近特别陡峭时也会出现这种现象。,69,3-5 无约束最优化的解析法梯度法、牛顿法、共轭梯度法、变尺度法,函数 沿某指定方向P的变化率（方向导数）：设函数 沿 P 方向由 移到 ，则 按导数的定义， 沿P方向的导数应为,按泰勒级数展开,3-5 无约束最优化的解析法,70,是步长 的高阶微量,即函数 沿 方向的导数等于梯度 在 方向的投影。,3-5 无约束最优化的解析法,71,沿等值线的任意方向，函数f的方向导数应等于零，则 ，这表明梯度向量与等值线正交。,一、梯度法,梯度法是一种下降算法,3-5 无约束最优化的解析法,72,为了确定下降方向，假定 在 处按泰勒级数展开,其中,当第k+1次迭代时,（3-47）,（3-48）,表示步长，是常数， 表示每一步所遵循的方向，把式（3-48）代入式（3-47）得,3-5 无约束最优化的解析法,73,欲使,则必须使,是常数，可以去掉，于是,3-5 无约束最优化的解析法,74,即函数沿负梯度方向下降最快。,迭代公式,这是一维搜索问题,步长 的选取应保证使,3-5 无约束最优化的解析法,75,梯度法的迭代步骤如下：,1.确定初始点。,3-5 无约束最优化的解析法,76,3.以 作为第二循环的初始点，重复以上步骤，直至第 循环，使求得的 小于预先指定的误差为止，即以 作为 的近似最优解。,用最速下降法极小化目标函数 ，初始点选在x(0)=(0,0)T，精度为0.01。,解：目标函数梯度在初始设计点的搜索方向：沿着这个搜索方向：新设计点：,3-5 无约束最优化的解析法,3-5 无约束最优化的解析法,78,梯度法在开始几次迭代时，步长较大，自变量的改变量和函数值的下降幅度都比较大，但当接近最优点时，步长很小，自变量的改变也很小，因而函数值下降得很慢，“之”字形,3-5 无约束最优化的解析法,这种方法的缺点严重：（1）即使对于一个正定二次型的目标函数，为了最小值足够准确，可能要迭代很多次。（2）每次迭代时并不利用以前计算中得到的任何信息。（3）如果目标函数接近圆形，迭代所需次数很少；反之，当目标函数是椭圆形且偏心率很大时，收敛很慢，只是头二、三次迭代中最速下降法很有 效，之后，设计点就沿着之字形路径慢慢移动了。,79,由复合函数求导数的法则,因此得,由此证明梯度法在相邻两次迭代中，梯度方向是互相正交的。,3-5 无约束最优化的解析法,理论解释,80,优点：程序简单，一次迭代工作量小，且开始迭代时，收敛快，即使选择一个不好的初始点也能很快地收敛到一个较好的迭代点。因此，梯度法仍受到人们的亲睐，工程上常将它和其他方法结合使用，在求解的开始阶段采用梯度法可以求得一个较好的初始点，然后再用其他收敛快的方法求得所需的极小点。,3-5 无约束最优化的解析法,81,二、牛顿法,1.单变量的牛顿迭代公式,设一元函数为 ，现把函数 在点 附近按泰勒级数展开，并略去二次以上的高阶项，得,若 是函数 的极小点，则应满足函数的极值条件：,由于 是二次函数，故 是线性函数，即,3-5 无约束最优化的解析法,82,根据极值条件,可得,或,当,时，迭代终止。,3-5 无约束最优化的解析法,83,牛顿法的几何解释：曲线 在 处的切线与x轴的交点作为下一个点 。,切线方程,与x轴交点,3-5 无约束最优化的解析法,84,多元函数f(x),x=(x1,x2,.,xn)T的无约束优化问题可化成求下列方程组的根：,在第k次迭代求解方程解的一个近似为x(k)，在x(k)处展开函数 ，使得,如果H在点x(k) 处非奇异，则,在x(k+1) 处f(x)取极小，则,3-5 无约束最优化的解析法,85,搜索方向为：为保证搜索方向是下山方向：当H是正定矩阵时肯定满足此式 。,至此，我们可以把S(k)及(k)=1结合到基本的下降算法框图中去，得到基本的牛顿-瑞弗逊法的计算框图。注意，此时无以为一维搜索，矩阵H的求逆可以用三角化的算法。,3-5 无约束最优化的解析法,86,解,3-5 无约束最优化的解析法,用牛顿法求目标函数 的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,87,为了克服不收敛的缺点，可以在牛顿法中，步长 不取1，而每迭代一步沿方向 作一维搜索，即迭代公式,其中 通过一维搜索求得：阻尼牛顿法,3-5 无约束最优化的解析法,3-5 无约束最优化的解析法,牛顿法的失效原因:,（1）H-1存在且正定，但沿S（k）步长太长以致f(x(k+1)f(x(k),（2）方向S（k）和f(x(k)正交,（3） H-1存在但非正定，S（k）并不给出下山方向,（4） H-1不存在,89,三、共轭方向法和共轭梯度法,梯度法收敛慢，牛顿法虽加快了收敛，但每次要计算二阶导数矩阵及其求逆，计算工作量太大。共轭方向法收敛速度比牛顿法慢，但比梯度法快，而且不需要计算二阶导数和矩阵求逆，总的效果比牛顿法好。,考察二维情况,对于二元二次函数,3-5 无约束最优化的解析法,90,任选初始点 ，沿某个下降方向 作一维搜索得 ，即 取得极值的充要条件是,而,故式（3-65）将变成,而且向量 所在的直线必与某条等值线相切于 点。,3-5 无约束最优化的解析法,91,下一次迭代，若按最速下降法选择负梯度方向为搜索方向，那么，将要发生锯齿现象。,希望下一次迭代的搜索方向将直指极小点,方向 应满足什么条件，怎样确定？,3-5 无约束最优化的解析法,92,因为 直指极小点 ，所以可以写成,对,求导,因为 是极小点，所以,将式（3-68）代入式（3-70），可得,即,3-5 无约束最优化的解析法,93,等式两边左乘,其中第一项，据式（3-67)等于零， 为不等于零的常数，所以,这就是使向量 直指极小点所必需满足的条件。,满足式（3-73）的两个向量 和 称为C的共轭向量，或称 和 的方向是共轭方向。,对于二元二次目标函数，从任意初始点 出发，沿任意下降方向 作一维搜索得到 ，再从 出发沿 的共轭方向 作一维搜索得到的 必是极小点 。,3-5 无约束最优化的解析法,94,例3-10 用共轭方向法求函数 的极小值，设初始点为 。,3-5 无约束最优化的解析法,95,3-5 无约束最优化的解析法,96,3-5 无约束最优化的解析法,97,共轭方向法,梯度法收敛慢，牛顿法虽加快了收敛，但每次要计算二阶导数矩阵及其求逆，计算工作量太大。,3-5 无约束最优化的解析法,98,作为一种迭代法：共轭方向是在迭代过程中逐次产生的，在迭代的第一步中，取负梯度方向作为移动方向，即 ，而在以后各步中，则以负梯度方向加上已产生的方向的线性组合作为移动方向：,共轭梯度法,这时，利用向量 与 关于C共轭的特性，即,将式（3-75）两边的矩阵转置后均乘以 ，则得,3-5 无约束最优化的解析法,99,这种在迭代过程中逐次产生共轭方向的方法，称为共轭梯度法。,当 不是极小点时，可用下式代替式（3-77）：,这样，可以不必计算H（海色矩阵），而直接由函数的梯度计算 的值。,3-5 无约束最优化的解析法,100,共轭梯度法的迭代步骤如下：,1. 给定初始值 ， ，并令 。,2. 对于k=0,1,2,.,n-1令,其中， 可由下式求得,当kn-1时，令,其中,3-5 无约束最优化的解析法,101,3. 当 ，则迭代停止，否则以 代替 ，并回到第一步。,3-5 无约束最优化的解析法,用共轭梯度法求目标函数 的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,102,3-5 无约束最优化的解析法,用共轭梯度法求目标函数 的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,103,3-5 无约束最优化的解析法,用共轭梯度法求目标函数 的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,104,3-5 无约束最优化的解析法,105,四、变尺度法牛顿法、梯度法可以归结为下述公式：,其中， 为nn矩阵，若令矩阵 等于单位矩阵，即 ， 则得梯度法若令 为F(X)的二阶导数矩阵的逆矩阵 ，便是牛顿法。,收敛慢,收敛快，但要求二阶导数和矩阵求逆，计算工作量大,变尺度法是选取一个 ，使其逼近海色矩阵的逆 ，则由式（3-79）确定的算法就可以保持收敛快的特点， 又避免了冗繁的计算工作。,3-5 无约束最优化的解析法,106,构造一个矩阵序列 ，使之逼近二阶导数矩阵的逆阵。,开始时，取 ，然后按下列递推公式计算每次迭代的H:,式中， 为修正矩阵。可以构造不同形式的 最常用的一种形式，构成变尺度法的递推公式：,其中,3-5 无约束最优化的解析法,107,根据以上分析，可得变尺度法的迭代步骤：,1. 给定初始点 与初始矩阵,2. 令,其中，求 ，使,3. 若 ，则令 ，并终止迭代，否则利用,修正矩阵 ，并回到2，继续迭代。,3-5 无约束最优化的解析法,108,3-5 无约束最优化的解析法,用变尺度法求目标函数 的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,109,3-5 无约束最优化的解析法,用变尺度法求目标函数 的极小值，初始点选在x(0)=(0,0)T，精度为0.01。,110,3-5 无约束最优化的解析法,111,3-6 目标函数为平方和的极小问题,3-6 目标函数为平方和的极小问题,最小二乘法、修正阻尼最小二乘法,对于有些实际问题，要求满足不等式方程组,的点X，这里 为给定的性能控制指标，各 可以相同、也可以不同。,一般地说， 是非线性的，现在要解非线性不等式（3-82），经常采用的手段是把问题转化为求X，使,112,的问题。给定的诸 ，可以作为计算过程中的控制量，一旦达到所述要求，即可终止计算。,平方和形式,最小二乘法（高斯牛顿法）,函数（3-83）的一阶偏导数,设 是函数（3-83）的极小点 的一个近似点，为了求得下一个近似点 ，在 附近将函数各项 展开，取其线性近似式：,3-6 目标函数为平方和的极小问题,113,3-6 目标函数为平方和的极小问题,由式（3-84）得到f(X)的一个二次的逼近函数：,因为,即,其中,114,3-6 目标函数为平方和的极小问题,又因为,即,将式（3-87）与式（3-88）代入一般无约束极值的牛顿公式：,得,这种把非线性最小二乘问题化为一系列线性最小二乘问题来求解的方法，就是通常所说的最小二乘法。,此法收敛速度慢些，但它避免了通常牛顿法中必须求 二阶导数的逆阵。,115,3-6 目标函数为平方和的极小问题,例 求解,解：,先用一般求极值方法求f(x)的极小点,x=0是函数f(x)的一个极小点，因为,116,3-6 目标函数为平方和的极小问题,高斯 牛顿法,得,代入式（3-89），得到,117,3-6 目标函数为平方和的极小问题,若 =0，则 =0，此时用高斯-牛顿法一次迭代即得到极小点；若 ，而 适当小时，式（1）成为,如果 趋于零，则其收敛速度是线性的；而牛顿法是平方收敛的，这是因为高斯-牛顿法不是直接采用 的二阶导数矩阵，而是用 的近似线性函数的二阶导数矩阵的缘故。,高斯-牛顿法对一般最小二乘问题并不总是适用的。,118,3-6 目标函数为平方和的极小问题,为了防止序列 发散，可对高斯-牛顿法加以修正，如每次迭代都进行一次一维搜索,式中,而 为步长，它使一元函数,达到极小,确定方向Pk的问题等价于求解线性方程组,其中， 为未知力,119,3-6 目标函数为平方和的极小问题,高斯-牛顿法计算框图,120,3-6 目标函数为平方和的极小问题,二、修正阻尼最小二乘法,最小二乘法缺点矩阵 是病态的（奇异的或近似奇异的），求逆矩阵 很困难，甚至不能实现。,有时，由式（3-92）所确定的搜索方向 与 的梯度 接近于正交，因为而迭代进展很慢或出现假收敛,修正阻尼最小二乘法,下降方向P由下式确定,121,3-6 目标函数为平方和的极小问题,其中，I 为单位矩阵。当 上式即为最小二乘法。当 充分大时，Pk趋向于负梯度方向 ，因此，本法取 ，为给定的常数。,其中,在求得方向P之后，则修正阻尼最小二乘法的迭代格式为,可以用一维搜索或其他方法求解，使函数值极小。,