常用无约束最优化方法ppt课件.ppt

《常用无约束最优化方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《常用无约束最优化方法ppt课件.ppt（72页珍藏版）》请在三一办公上搜索。

1、第五章 常用无约束优化方法,最速下降法 Newton法修正Newton法共轭方向法 共轭梯度法 变尺度法 坐标轮换法 单纯形法,第五章 常用无约束优化方法,成立点 就是问题（5.1）的全局最优点但是，大多数最优化方法只能求到局部最优点这个矛盾对于实际问题来讲一般容易解决，因为根据问题的实际意义多半可以直接判定用优化方法求出的局部最优解是否为全局最优解但在理论上这是个比较复杂的问题，本书不涉及,无约束优化方法是优化技术中极为重要,它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解同时，有些无约束优化方法只需略加处理，即可用于求解约束

2、优化问题,第五章 常用无约束优化方法,无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（或解析法）直接法不涉及导数和Hesse矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但需计算梯度，甚至需要计算Hesse矩阵一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法,第五章

3、 常用无约束优化方法,5.1 最速下降法,为求问题（5.1）的最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代公式 ，按照特定的算法产生一串点列 ，如果点列收敛，则该点列的极限点为问题（5.1）的最优解,最速下降法基本原理,在基本迭代公式 中，每次迭代搜索方向 取为目标函数 的负梯度方向，即 ，而每次迭代的步长 取为最优步长，由此所确定的算法称为最速下降法,在第二章中，我们曾经提到，对于函数，其函数值下降最快的方向是该函数的负梯度方向。,第五章 常用无约束优化方法,对于问题（5.1），假定我们已经迭代了k次，获得了第k个迭代点Xk现在从Xk出发，可选择的下降方向很多，一个

4、非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在邻近的范围内是这样因此，取搜索方向为:,为了使目标函数在搜索方向上下降最多，沿Pk进行一维搜索，由此得到第k+1个迭代点，即,其中步长tk因子由 来确定。,记为,令k=0,1,2,. ，就可以得到一个点列（初始点可任意选择）。当函数满足一定的条件时， 该点列必收敛于函数的极小点。,为书写方便，记 故 在不发生混淆时，再记 ,第五章 常用无约束优化方法,迭代步骤,已知目标函数 及其梯度，终止限 、 和 ,（1）选定初始点 ，计算 ， ；置,（3）用终止准则检测是否满足：若满足，则打印最优解 , ,结束；否则，置 ，转（2）

5、,第五章 常用无约束优化方法,由此解出,第五章 常用无约束优化方法,例5.1 试用最速下降法求函数 的极小点迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点为 ,解 与式（5.4）比较，得,梯度表达式是,由 ，计算出,第五章 常用无约束优化方法,因为目标函数是二次的，可以使用式（5.8），所以有,计算,因为,说明相邻两个搜索方向是正交的,第五章 常用无约束优化方法,有关说明,最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢,沿负梯度方向函数值下降很快的说法，容易使

6、人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快,第五章 常用无约束优化方法,5.2 Newton法,如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵正定并且可以表达成为显式（记 ，那么可以使用下述的Newton法这种

7、方法一旦用好，收敛速度是很快的它是一维搜索Newton切线法的推广,基本原理,为寻求收敛速度快的算法,在应用基本迭代公式中 ，每轮迭代在迭代的起始点 处用一个适当的二次函数来近似该点处的目标函数，由此用点 指向近似二次函数极小点的方向来构造搜索方向 .,第五章 常用无约束优化方法,不妨设经过 次迭代已获点 ，现将 在 处展成二阶泰勒公式，于是有,显然 是二次函数，并且还是正定二次函数，所以 是凸函数且存在唯一全局极小点为求此极小点，令,即可解得,第五章 常用无约束优化方法,方向 是直指点 处近似二次函数 的极小点的方向此时称此方向为从点 出发的Newton方向从初始点开始，每一轮从当前迭代点出

8、发，沿Newton方向并取步长 的算法称为Newton法,迭代步骤,已知目标函数 及其梯度 ，Hesse矩阵 ，终止限 ,（1）选定初始点 ；计算 ；置 ,（2）计算 .,（3）由方程 解出 ,（4）计算 .,（5）判别终止准则是否满足：若满足，则打印最优解 ， 结束；否则，置 ，转（2）,第五章 常用无约束优化方法,第五章 常用无约束优化方法,例5.2 试用Newton法求 的极小点，初始点取为 ,解 梯度为,Hesse矩阵为,其逆矩阵为,由迭代公式（5.9）得第1 迭代点为,由此 ，停止迭代得,第五章 常用无约束优化方法,对于目标函数是非二次函数的非约束最优化问题，一般来说，用Newton

9、法通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是较快的,从例5.2我们看到，用Newton法求解，只经一轮迭代就得到最优解这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解,事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的但是当初始点选得离最优解太远时，Newton法并不一定是收敛的方法，甚至连其下降性也很难保证,

10、第五章 常用无约束优化方法,有关说明,Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：,（1）尽管每次迭代不会使目标函数上升，但仍不能保证下降当Hesse矩阵非正定时，Newton法的搜索将会失败,（2）对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的,（3）在进行某次迭代时可能求不出搜索方向由于搜索方向为 ,若目标函数在 点Hesse矩阵是奇异的，则 不存在，因而不能构成newton方向，从而使迭代无法进行,（4）newton方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大,第五章 常用

11、无约束优化方法,5.3 拟Newton法,基本原理,为了克服Newton法的缺点，人们保留选取Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步长，由此产生的算法称为修正Newton法（或阻力Newton法）,迭代步骤,已知目标函数 及其梯度 ，Hesse矩阵 ，终止限 ,（1）选取初始点 ，令 ,（2）计算 若 ，停止迭代输出，否则转（3）,（3）构造Newton方向计算 ，取,（4）进行一维搜索求 ，使得 令 ，转（2）,第五章 常用无约束优化方法,修正Newton法克服了Newton法的缺点特别是，当迭代点接近于最优解时，此法具有收敛速度快的优点，对初始点的选择要求不

12、严但是，修正Newton法仍需要计算目标函数的Hesse矩阵和逆矩阵，所以计算量和存贮量均很大另外，当目标函数的Hesse矩阵在某点处出现奇异时，迭代将无法进行，因此修正Newton法仍有相当的局限性,有关说明,第五章 常用无约束优化方法,5.4 共轭方向法,不同最优化方法，取决于基本迭代公式中确定搜索方向的构造,最速下降法， ，导致搜索路线出现锯齿状，收敛速度降低；,Newton法 ， ，收敛速度虽很快，但计算量很大，特别是还要求Hesse矩阵正定，从而导致该算法对初始点选择要求过严,下面介绍共轭方向法 ，该方法计算量小，收敛速度没有Newton法快，但比最速下降法快得多。,第五章 常用无约

13、束优化方法,基本原理,首先介绍共轭方向概念及其些性质,定义5.1 设 是对称正定矩阵对于非零向量 ，若有 （5.10）则称 与 相互 共轭或 正交的,若 ，则式（5.10）和式（5.11）成为 和 由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广,第五章 常用无约束优化方法,定理5.1 设 是正定矩阵， 是非零向量若 是一组 共轭方向，则它们是线性无关的,证明：设有一组实数 ，使得,因为 是一组 的共轭方向，故有,又由于A是正定矩阵，所以 对于，有,故,由此 是线性无关,第五章 常用无约束优化方法,定理 5.2设 是对称正定矩阵，是一组 的共轭方向对于问题（5.13），若从任意点

14、出发依次沿 进行一维搜索，则至多经过 轮迭代，可得问题（5.13）的最优解,证明 （略）,通常，我们把从任意点 出发，依次沿某组共轭方向进行一维搜索的求解最优化问题的方法，叫做共轭方向法,第五章 常用无约束优化方法,算法形成,为了直观起见，考虑形式为（5.13）的二元二次函数,任选初始点 ，从 出发沿某个下降方向 作一维搜索得到,下一次迭代，若按最速下降法选择负梯度方向作为搜索方向，则将发生锯齿现象，为了克服这种现象，我们设想，若下一次迭代的搜索方向能直指极小点 ，那么对于二元二次函数只须顺次进行两次直线搜索就可以求到极小点了这样的方向是否存在？若存在，应该满足什么条件？怎样确定？,第五章 常

15、用无约束优化方法,将式（5.21）代入上式，并由式（5.22）可得,这就是为 使直指极小点所必须满足的条件显然式（5.23）中 和 是 的共轭向量,第五章 常用无约束优化方法,式(5.24)两边同时左乘 ，有,由此解出,代回到式（5.24），得,第五章 常用无约束优化方法,一般地，在n维空间中可以找出n个互相共轭的方向，对于n元正定二次函数，从任意初始点出发，顺次沿这n个共轭方向最多作n次直线搜索就可以求得目标函数的极小点这就是共轭方向法的算法形成的基本思想,对于n元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那末这种算法称为具有二次终止性例如Newton法对于二次

16、函数只须经过一次迭代就可以求得极小点，因此是二次终止的；而最速下降法不具有二次终止性共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快,第五章 常用无约束优化方法,迭代步骤,已知具有正定矩阵 的二次目标函数 和终止限 ,（1）选定初始点 和具有下降的方向 ，置 ,（2）作直线搜索,（3）判别是否满足 ：若满足，则打印 ，结束；否则转（4）,（4）提供共轭方向 使得,（5） ，转（2）,第五章 常用无约束优化方法,5.5 共轭梯度法,如果在共轭方向法中初始的共轭向量 恰好取为初始点 处的负梯度 ，而以下各共轭方向 由第 迭代点 处的

17、负梯度 与已经得到的共轭向量 的线性组合来确定，那么就构成了一种具体的共轭方向法因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法,基本原理,设从任意点 出发，第一个搜索方向取为 处的负梯度方向 .,第五章 常用无约束优化方法,为了使选择 所产生的 和是 共轭，以 右乘上式的两边，于是有,因为,故,这样，就可以生成n个方向：,（5.25）,第五章 常用无约束优化方法,式（5.25）中含有问题（5.13）的目标函数系数矩阵，这对于目标函数是非二次函数的问题是不方便的通过简化，一般可以利用目标函数的梯度信息，来产生n个共轭方向,由此得共轭梯度法,第五章 常用无约束优化方法

18、,迭代步骤,已知目标函数 ，终止限 ,（1）选取初始点 ，给定终止限 ,（2）求初始梯度计算 ，若 ，停止迭 代输出 ，否则转（3）,（3）构造初始搜索方向取 ，令 ，转（4）,（5）求梯度向量计算 ，若 ，停止迭代 输出 否则转（6）,（6）检验迭代次数若 ，令 ，转（3），否 则转（7）,第五章 常用无约束优化方法,第五章 常用无约束优化方法,解,令,第五章 常用无约束优化方法,则,故,令,由于,第五章 常用无约束优化方法,有关说明,实际上，可以把共轭梯度法看作是最速下降法的一种改进当 时，就变为最速下降法,共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题,另

19、外，共轭梯度法不要求精确的直线搜索但是，不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低方法的效能克服的办法是，重设初始点，即把经过n次迭代得到的Xn作为初始点重新迭代,第五章 常用无约束优化方法,5.6 变尺度法,我们知道Newton法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的因此，建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解然而Newton法还有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton法的优点为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优

20、点，又可以摆脱关于Hesse矩阵的计算，这就是本节要给大家介绍的变尺度算法,变尺度法是一种非常好的方法其中DFP算法和BFGS算法，可以说直到目前为止是在不用Hesse矩阵的方法中最好的算法,第五章 常用无约束优化方法,一、变尺度法基本原理,Newton法在基本迭代公式 中， ， 。记,为了消除迭代公式(5.26)中的Hesse逆矩阵 ,可用某种近似矩阵 来替换它，即构造一个矩阵序列去逼近Hesse逆矩阵序列 此时式（5.26）变为,式（5.27）是一类更很广泛的迭代公式例如，当 ，它变为最速下降法的迭代公式,第五章 常用无约束优化方法,为使 与 近似,并且有容易计算的特点，必须对附加某些条件

21、：,第一，为保证迭代公式具有下降性质，要求 中的每一个矩阵都是对称正定的,第五章 常用无约束优化方法,第三， 必须满足拟Newton条件所谓拟Newton 条件由下面的推导给出,设迭代过程已进行到 步， 和 均已求出，现在推导 所必须满足的条件,设目标函数 具有连续的二阶偏导数现在 将在 处展成二阶泰勒公式,令 ，于是有,即,当 正定时，,第五章 常用无约束优化方法,为了书写方便，记,变尺度法也称为拟牛顿法。下面总结变尺度法的迭代步骤 。,第五章 常用无约束优化方法,迭代步骤,已知目标函数 及其梯度 ，终止限 ,（1）选定初始点 ；计算 ；选定初始矩阵 ，要求对称正定（例如， ）；置 ,（2）

22、计算搜索方向 ,（3）作直线搜索 ，计算,（4）判别终止准则是否满足：若满足，则 就是所求的极小点，打印，结束；否则转（5）,（5）计算,（6） ，转（2）,这里，校正矩阵 可由确定的公式来计算不同的公式对应不同的拟Newton算法,第五章 常用无约束优化方法,第五章 常用无约束优化方法,满足式 （5.31） 的有无穷多个，因此上述拟Newton算法构成一簇算法下面分别介绍两个常用的公式,DFP算法,BFGS算法,第五章 常用无约束优化方法,（一）DFP算法,DFP算法首先是由Davidon（1959年）提出来的，后来，Fletcher和Powell（1963年）对Davidon的方法作了改进

23、，最后才形成DFP算法D、F、P是这三位学者名字的字头这种算法是无约束最优化方法最有效的方法之一,DFP算法基本原理,下面来来讨论如何确定,第五章 常用无约束优化方法,满足这个方程的待定向量 和 有无穷多种取法，下面是其中的一种：,这里 和 都是数量，不妨取,同时取,第五章 常用无约束优化方法,DFP算法迭代步骤,DFP算法的迭代步骤只需用将拟牛顿法中第（5）步具体化即可。,但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，可能要破坏迭代矩阵 的正定性，从而导致算法失效为保证 的正定性，采取以下重置措施：迭代 次后，重置初始点和迭代矩阵，即 ，重新迭代,已知目标函数 及其梯度 ，问题的

24、维数 ，终止限 ,（1）选定初始点计算 ,（2）置 ,（3）作直线搜索 ；计算,第五章 常用无约束优化方法,（4）判别终止准则是否满足：若满足，则打印，结束；否则转（5）,（5）若 ，则置 ，转（2）；否则转（6）,第五章 常用无约束优化方法,例5.4 用DFP算法求 ，取 ,解 当我们取 时，DFP法与最速下降法具有相同的第1迭代点，在例5.1中已作了计算,以下用DFP法作第二次迭代,第五章 常用无约束优化方法,按DFP算法中的第（6）步计算,因为,所以,第五章 常用无约束优化方法,搜索方向为,从X1出发沿P1进行直线搜索，即,由,知,所以,由于 ，所以 是极小点,第五章 常用无约束优化方法

25、,（二）BFGS算法,BFGS算法是Broyden， Fletcher（1970年），Goldfarb（1969年）和Shanno（1970年）共同研究的结果 ,故名BFGS算法,BFGS算法基本原理,其中,此时校正矩阵为,而参数 可取任何实数，每取一个实数就对应一种拟Newton算法易证，当 取时就是DFP校正公式,第五章 常用无约束优化方法,令,则,这就是著名的BFGS校正公式。,BFGS算法迭代步骤,已知目标函数 及其梯度 ，问题的维数 ，终止限 ,（1）选取初始点 ，初始矩阵 ，给定终止限 ,（2）求初始梯度向量，计算 ，若 ，停止迭代输出 ，否则转（3）,（3）构造初始BFGS方向，

26、取 ，令 ，转（4）,第五章 常用无约束优化方法,（4）进行一维搜索，求 ，使得 ，令 ，转（5）,（5）求梯度向量，计算 ，若 ，停止迭代输出 ；否则转（6）,（6）检验迭代次数，若 ，令 转（3）；否则转（7）,第五章 常用无约束优化方法,变尺度法有关说明,变尺度法中的两个重要算法DFP算法和BFGS算法，它们的迭代过程相同，区别仅在于校正矩阵选取不同，对于DFP法，由于一维搜索的不精确和计算误差的积累可能导致某一轮的 奇异，而BFGS法对一维搜索的精度要求不高，并且由它产生的 不易变为奇异矩阵BFGS法比DFP法更具有好的数值稳定性，它比DFP法更具有实用性,第五章 常用无约束优化方法,

27、5.7 坐标轮换法,基本原理,基本思想：是把含有n个变量的优化问题轮换地转化为单变量（其它变量视为常量）的优化问题所谓单变量优化问题就是沿某个坐标轴方向进行一维搜索的问题,寻优思路 ：先选定一个初始点X0作为第一轮搜索的始点，依次沿n个坐标轴方向进行一维搜索，每次只在一个坐标轴方向上改变相应变量的值，其它n-1个变量均保持不变在沿第一个坐标轴方向进行一维搜索得到目标函数值的最小点 （或近似最小点）后，再以此点作为始点转到沿第二个坐标轴方向进行一维搜索得到 ，直到沿第n个坐标轴方向搜索结束得到 为一个循环如果 不满足收敛准则，则以 作为初始点转入下一轮循环，直到经过k次循环，获得满足收敛准则的点

28、 ，即作为最优点,第五章 常用无约束优化方法,在坐标轮换法中，沿各个坐标轴方向进行一维搜索时，常选用最优步长法或加速步长法加速步长法从初始点出发，沿搜索（坐标轴）方向先取一个较小的步长 ，作前进（或后退）试探如试探成功（目标函数值有所减小），则按步长序列 ，加大步长（注意每次加大步长都是由初始点算起），直至试探失败（目标函数值比前一次的有所增加）时，则取其前一次的步长作为沿这个坐标轴方向搜索的最优步长，并计算出该方向上的终止点，而后以这个终止点为始点再进行下一坐标轴方向的搜索，并重复上述步骤如此迭代下去，直到找到最优点 本节只用一维搜索法来确定最优步长,第五章 常用无约束优化方法,迭代步骤,首

29、先沿 方向进行一维搜索，求出该方向上目标函数的极值点 ；再以 为初始点沿 方向进行一维搜索，得到极值点 ；仿此依次沿 进行一维搜索，最终得到极值点 这就完成了第一轮搜索,如果 能够满足收敛准则，即可停止搜索，以 作为 输出否则，继续以 为初始点，进行第二轮循环，依次沿 进行一维搜索，得到第二循环的极值点 如此进行下去，直至最终找到满足收敛准则（终止准则）的点 ，即求得了最优解 ，再求出目标函数值 具体迭代过程如下：,第五章 常用无约束优化方法,已知目标函数 ，终止限 ,（1）任选取始点 作为第一轮循环的初始点， ,（3）按下式求最优步长并进行迭代计算,（4）如果 ，即转（5）；如果 ，则转（3

30、）,（5）收敛性准则 ，若满足判别式，即停止迭代，输出最优解 及 ；若不满足，则令 转（3）,第五章 常用无约束优化方法,有关说明,坐标轮换法的优点是算法简单，计算量小，其缺点是计算效率低，对高维问题尤为突出因此，坐标轮换法通常用于维数较低的优化问题（一般 ）,第五章 常用无约束优化方法,例5.5 用坐标轮换法求 ，初始点 ,解 从初始点出发，依次沿方向 搜索，以第一步为例，从 出发，沿方向 搜索，求得点,求,即,得 ，即取 ，于是得,再从 出发，沿方向 搜索，求得 点,第五章 常用无约束优化方法,求,可得 ，即取 ，于是有,第五章 常用无约束优化方法,5.8 单纯形法,单纯形法基本原理,以二

31、元函数为例，说明单纯形法的原理,设二元函数 在平面上取不在同一条直线上的三个点 ， 和 ，并以它们为顶点构成一单纯形三角形算出各顶点的函数值 ， ， ，比较其大小，不妨假定比较后有,这说明 点最差， 点最好， 点次差,第五章 常用无约束优化方法,计算函数值 ，可能出现以下几种情形：,(1),如果 ，说明扩张有利，以点 代替点 构成新的单纯形 .,如果 ，说明扩张不利，舍去 ，仍以 代替点 构成新的单纯形 .,第五章 常用无约束优化方法,(3),如果 ，则以 代替 构成新的单纯形 。,第五章 常用无约束优化方法,如果 ，则认为 方向上所有点的函数值 都大于 ，不能沿此方向搜索这时，可以以 为中心

32、进行缩边若使顶点 和 向 移近一半距离,得新单纯形 以此单纯形为基础再进行寻优,以上说明，不管哪种情况，我们都可以得到一个新的单纯形，其中至少有一顶点的函数值比原单纯形为小如此继续，直至满足收敛终止准则,在n维情况下，一个单纯形含有n+1个顶点，计算工作量较大，但原理和上述二维情况相同,下面具体看一下单纯形法迭代步骤。,第五章 常用无约束优化方法,单纯形法迭代步骤,已知 为n维变量，目标函数为 ，终止限为 ,(1) 构成初始单纯形,在n维空间中选初始点 （离最优点越近越好），从 出发，沿各坐标方向以步长 得 个顶点 ，这样选择顶点可保证向量组,线性无关否则，就会使搜索范围局限在较低维的空间内，

33、有可能找不到极小点当然，在各坐标方向可以走不同的距离,步长 的范围可取0.515.0，开始时常取 ，接近最优点时要减小，例如取0.51.0,第五章 常用无约束优化方法,(4) 当 时，需要扩张令,如果 ，则以 代替 形成一新单纯形；否则，以 代替 构成新单纯形然后转(8),第五章 常用无约束优化方法,(5) 当 时，以 代替 构成新单纯形，然后转(8) .,第五章 常用无约束优化方法,(8) 收敛性检验,例5.6 试用单纯形法求 的极小值,解,选取,这三点不在一条直线上，用它们作为初始单纯形的顶点 然后计算各顶点的函数值：,第五章 常用无约束优化方法,以 表示 和 的重心，则,反射点,由于 ，故需扩张取 ，则,因为 ，故以 代替 ，构成新单纯形，然后进行下一个循环,第五章 常用无约束优化方法,