第四章无约束优化方法

1、第四章 无约束优化方法 4.1 4.1 概述概述 4.2 4.2 最速下降法（最速下降法（梯度法）梯度法） 4.3 4.3 牛顿法牛顿法 4.5 4.5 共轭梯度法共轭梯度法 4.6 4.6 变尺度法变尺度法 4.74.7 坐标轮换法坐标轮换法 4.84.8 Poweel Poweel 法法 4.10 4.10 无约束优化设计方法小结无约束优化设计方法小结一、目的：求一组 n 维设计变量 X= x1, x2 ,x n T, 使目标函数达到 min. f(x) XRn即求目标函数的最优解：最优点 x* 和最优值 f(x*) 。第一节 概 述无约束优化问题的极值条件:*0f x二、二、意义：l 为

2、有约束优化方法的研究提供了策略思想、概念基础和基本方法；l 为有约束优化问题的间接解法提供了有效而方便的方法；l不可避免地还存在无约束优化的设计问题。第一节 概 述三、求解方法：解析法数学模型复杂时不便求解数值法可以处理复杂函数及没有数学表达式的优化设计问题1kkkkxxa d搜索方向和最佳步长确定的问题是无约束优化方法的关键。最佳步长的确定可以有不同的方法：0.618法及插值法。各种无约束优化方法的区别：确定搜索方向的方法不同。无约束优化方法分类（确定搜索方向的方法不同）：利用目标函数的一阶或二阶导数：利用目标函数值（最速下降法、共轭梯度法、牛顿法）（坐标轮换法、鲍威尔等）一、一、基本思想基

3、本思想：优化设计追求目标函数值最小，回顾梯度方向的意义，梯度方向是通过某点的函数沿某一方向变化率最快的方向（梯度方向为函数值上升方向），那么负梯度方向就可作为搜索方向，期望很快找到最小值点。若搜索方向取该点的负梯度方向，就会使函数值在该点附近的范围内下降最快。第二节 最速下降法按此规律不断走步，形成以下迭代算法：1kkkkxxafx以负梯度方向为搜索方向，所以称最速下降法或梯度法。4.2 4.2 梯度法梯度法二、二、 搜索方向：搜索方向：量。是负梯度方向的单位向,)()()()()(kkkxfxfdka三、三、确定步长因子即求一维搜索的最佳步长，既有 1minminkkkkkkkfxfxafx

4、fxafx 0Tkkkkfxafxfx 10Tkkf xf x10Tkkdd由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。注意： 相邻两个搜索方向互相垂直，所以，迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象。 因此，在远离极小点的位置，每次迭代可使函数值有较多的下降，但在接近极小值的地方，下降缓慢。 图4-2 最速下降法的搜索路径四、四、 方法评价：方法评价：l 迭代过程简单，对初始点的选择，要求不高。l 梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。l 以二维二

5、次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径。例4-1 求目标函数 221225f xxx的极小点。第三节牛顿型方法在第三章中，我们已经讨论了一维搜索的牛顿方法。得出一维情况下的牛顿迭代公式1kkkkfxxxfx对于多元函数，在kx泰勒展开，得 f xx 212TTkkkkkkf xf xxxxxf xxx设1kx为函数的极小点，根据极值的必要条件10kx210kkkkf xf xxx112kkkkxxf xf x 这是多元函数求极值的牛顿法迭代公式。即：得：将 f(x) 在 x(k) 点作台劳展开，取二

6、次函数式(x) 作为近似函数,以(x) 的极小值点作为 f(x) 的近似极小值点。 基本思想：基本思想：说明：说明：（3）f(x) 若是正定二次函数，一般迭代一 次即可；若是严重非线性函数，则可 能不收敛，或收敛到鞍点。为牛顿方向。逆矩阵。矩阵的为即为：)()()2( )()()1 ()(1)(1)(1)(2KkkkxfxHHessexHxf例4-2 用牛顿法求 221225f xxx的极小值。为最优步长因子。其中则称为牛顿方向，令)()(12)()()1()(1)()(, )()()()(kkkkkkkkkxfxfxxxfxHd二、二、 阻尼牛顿法阻尼牛顿法：使用牛顿法时，若目标函数是非二次

7、函数，可能出现迭代的过程中函数值上升，所以给牛顿法加一阻尼因子，构成阻尼牛顿法。1minkkkkkkf xfxa dfxad步长因子通过如下极小化过程求得：方法评价：方法评价：l 使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。l 若初始点选得合适，牛顿法的收敛速度相当快。l 牛顿法求逆矩阵的工作量大，计算量与存储量均随 n2上升。1.1.共轭方向概念：共轭方向概念： 为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。 12TTf xx Gxb xc共轭方向的

8、概念是在研究二次函数时引出的。第四节共轭方向及共轭方向法首先考虑二维情况：二元二次函数的等值线为一组椭圆，任选初始点x0沿某个下降方向d0作一维搜索得x1：1000 xxa d考虑到x1点处方向导数和梯度之间的关系，有： 1100Txff xdd 如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行d0，d1两次直线搜索就可以求到极小点，即有：*111xxa d图4-7 负梯度方向与共轭方向1d应满足什么条件？对于二次函数 在 处取得极小点的必要条件 fx*x*0fxGxb*1111

9、11f xG xa dbGxbaGd 1110f xaGd 等式两边同乘 得0Td010TdGd 0d1d是对G的共轭方向。是共轭方向。对和的共轭向量，或称为称和，则若它们满足为两个非零向量，和为对称正定矩阵设GddGddjiGddddGjijijTiji)(0)(,2. 2. 共轭方向性质：共轭方向性质： 性质性质1 1 性质性质2 2 性质性质3 3 。二次函数极小点二次函数极小点次迭代就可以找到次迭代就可以找到过过进行一维搜索，最终通进行一维搜索，最终通的共轭方向的共轭方向个个出发，顺次沿出发，顺次沿从任意初始点从任意初始点。零向量的个数不超过零向量的个数不超过维空间中互相共轭的非维空间

10、中互相共轭的非在在是线性无关的。是线性无关的。个向量个向量共轭的，则这共轭的，则这是对是对若非零向量系若非零向量系*110011021)(,.,.,xcxbGxxxfndddGnxnnmGdddTTmm1. 1. 基本思想基本思想：2. 2. 共轭方向共轭方向： 初定一搜索方向，一般选坐标轴的单位向量方向，下一个搜索方初定一搜索方向，一般选坐标轴的单位向量方向，下一个搜索方向按照格拉姆向按照格拉姆- -斯密特向量系共轭方向法确定，使得相邻的两次搜索斯密特向量系共轭方向法确定，使得相邻的两次搜索方向变为共轭，成为二次收敛。方向变为共轭，成为二次收敛。为为共共轭轭系系数数。：其其中中次次搜搜索索的

11、的方方向向为为第第rkrrkkrkkdvdk, 1, 10)1()1(,13. 3. 共轭系数：共轭系数：jTjkTjjkGddGvd)()(1, 1三、共轭方向法1、选定初始点 ，下降方向 和收敛精度，k=0。0 x0d2、沿 方向进行一维搜索，得kd1kkkkxxa d3、判断 是否满足，若满足则打印1kf x1kx否则转4。4、提供新的共轭方向 ，使 1kd10TjkdGd5、置 ，转2。1kk4. 4. 共轭方向法步骤：共轭方向法步骤：第五节 共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量由迭代点的负梯度构造出来，所以称共轭梯度法。 12TTf xx Gxb xckkgGxb从点 出

12、发，沿G某一共轭方向 作一维搜索,到达kxkd1kx11kkgGxb而在点 、 处的梯度分别为：kx1kx二次函数：1kkkkxxa d1kkkkxxa d或11kkkkkkggG xxa Gd所以有：0TjkdGd 若dj和dk是对G共轭的，则有：利用上式对两端前乘(dj)T：即得：0)()(1kkTjggd一、一、 基本思想基本思想：得出共轭方向与梯度之间的关系。此式表明沿方向kd进行一维搜索，其终点 与始点 1kxkx1kkgg与 的共轭方向 正交。kdjd的梯度值差图4-9 共轭梯度法的几何说明二、二、 共轭方向：共轭方向：为共轭系数。：其中次搜索的方向为第次搜索的方向为第)()()(

13、)1()1()()(,)(1),(kkkkkkkdxfdkxfdk三、三、 共轭系数：共轭系数：2)(2)1()()()(kkkxfxf推导过程请自学。对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛，也叫旋转梯度法。四、步骤：四、步骤： 步步。转转第第令令：，构构造造新新的的共共轭轭方方向向计计算算则则进进行行下下一一步步；，若若步步；转转第第，则则令令，若若，检检查查搜搜索索次次数数步步；若若不不满满足足，则则进进行行第第；，若若满满足足，则则迭迭代代结结束束是是否否判判断断；方方向向作作一一维维搜搜索索，求求得得沿沿；计计算算，令令

14、；和和计计算算精精度度选选取取初初始始点点kkSxfSnkxxnkxxxfSxxSxfSkxkkkkkkkkkkkkkkk, 1,)(*,)()(0)()()1()()()1()0()1()1()()()()1()()()()0(五、方法评价：五、方法评价：l 迭代程序简单，容易实现，存储量较小。迭代程序简单，容易实现，存储量较小。l 开始采用梯度方向，目标函数值下降快，后开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛速度，收敛又为旋转梯度方向，具有二次收敛速度，收敛快。快。第六节变尺度法1kkkkxxHf x变尺度法的基本思想：梯度法和牛顿法的迭代公式可以看作下列公式的

15、特例。 它发扬梯度法和牛顿法各自的优点，避免梯度法收敛慢和牛顿法计算海赛矩阵缺点，将两者结合，形成变尺度法。利用牛顿法的迭代公式，减少。算和求逆，计算量大大法省去了海赛矩阵的计，显然此，最后逼近在迭代过程中不断改进，近似地代替阵而是用一个对称正定矩，但并不直接计算11111)()()(),()(kKkKkkkkkkxHHxHHxHxfxHxx一、尺度矩阵的概念变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。由于对称矩阵H在迭代过程中是不断修正改变的，它对于一般尺度的梯度起到改变尺度的作用，因此H又称变尺度矩阵。每确定一次搜索方向，调整一次模（尺度）的大小，称

16、为变尺度。则在新的坐标系中，函数的二次项变为：1122TTTx Gxx Q GQx选择这样变换的目的：降低二次项的偏心程度。若矩阵G是正定的，则总存在矩阵Q使TQ GQI对于一般二次函数 12TTf xx Gxb xc如果进行尺度变换xQx使得函数偏心度变为零。说明二次函数矩阵G的逆矩阵，可以通过尺度变换矩阵Q求得。这样，牛顿法迭代过程中的牛顿方向可写成：1kkTkdGf xQQf x 1kkkTkxxQQf x三、变尺度法的一般步骤用Q-1 右乘等式两边，得1TQ GQ再用Q左乘等式两边，得TQQ GI所以1TQQG4.6 4.6 变尺度法变尺度法3. 3. 迭代公式：迭代公式：了了牛牛顿顿

17、法法的的优优点点。矩矩阵阵的的逆逆矩矩阵阵，而而利利用用及及这这样样避避免免计计算算二二阶阶导导数数即即为为牛牛顿顿法法。最最终终迭迭代代时时，时时接接近近当当不不断断修修正正尺尺度度，逼逼近近，中中间间的的迭迭代代即即为为梯梯度度法法，首首次次迭迭代代时时，为为拟拟牛牛顿顿方方向向。的的矩矩阵阵一一个个为为变变尺尺度度矩矩阵阵，是是：其其中中：迭迭代代公公式式HessexfxHSxfxHSxHHxxxHHxfSIHxfHSnnHxfHxxkKkkKkKkkkkkkkkkkkkkkk, )()(, )()(,)(*,)(, )(, )(,),()(1)()()(1)()(1)()()(1)()

18、()()()0()()()()()()()()()1(4.6 4.6 变尺度法变尺度法4. 4. 变尺度矩阵的构造：变尺度矩阵的构造：原则：原则： 使目标函数值有下降性，则变尺度矩阵应为实对称矩阵使目标函数值有下降性，则变尺度矩阵应为实对称矩阵（请证明）（请证明）； 使算法有二次收敛性，则使算法有二次收敛性，则 S S(k)(k) (k=1,2,) (k=1,2,)应关于应关于 H H(k)(k) 是共轭的；是共轭的；。即即：件）件）变尺度条件（拟牛顿条变尺度条件（拟牛顿条)()()(,)()1()()1()1()()()1(kkkkkkkkxxxfxfHxgH构造变尺度矩阵的递推公式构造变尺

19、度矩阵的递推公式：5. 5. 修正矩阵修正矩阵: : 次迭代时的修正矩阵。次迭代时的修正矩阵。为第为第其中：其中：kEEHHkkkk)()()()1(,)()()()()()()()()()()()(kkTkkTkkkkTkTkkkgHgHggHxgxxE4.6 4.6 变尺度法变尺度法6. 6. 方法评价：方法评价：l DEFDEF变尺度法以逐次逼近的方法实现变尺度法以逐次逼近的方法实现 H H-1-1 的计算，当目标函数的的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。l 算法的第一步是梯度法，最速下降；接近算

20、法的第一步是梯度法，最速下降；接近 x x* * 时，又采用二次时，又采用二次收敛的共轭方向，总的收敛速度较快。收敛的共轭方向，总的收敛速度较快。l H H(k)(k) 近似代表近似代表 x x(k)(k)点的二阶导数，当其为零时，可判断点的二阶导数，当其为零时，可判断 x x(k)(k)为为鞍点。鞍点。l H H(k)(k) 的计算较复杂，存储量较大。的计算较复杂，存储量较大。l 算法稳定性较差，由于计算机有舍入误差，容易使算法稳定性较差，由于计算机有舍入误差，容易使 H H (k) (k) 的正的正定性破坏，趋于奇异。定性破坏，趋于奇异。 第七节 坐标轮换法坐标轮换法是每次搜索只允许一个变

21、量变化其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优化问题。因此又称变量轮换法。不用求目标函数的导数，只求目标函数值得信息。图4-12 坐标轮换法的搜索过程1. 1. 基本思想：基本思想： 每次以一个变量坐标轴作为搜索方向，将 n维的优化问题转化为n个一维搜索问题，并进行若干轮循环迭代求解的直接法。即：它每次搜索只允许一个变量变化，其余变量保持不变，也就是沿坐标方向轮流进行搜索。例，第 k轮迭代的第 i 次搜索，是固定除 xi外的 n-1 个变量，沿 xi 变量坐标轴作一维搜索，求得极值点 xi(k) n 次搜索后获得极值点序列 x1(k),

22、x2(k）, xn(k)，若未收敛，则开始第 k+1 次迭代，直至收敛到最优点 x*。 2.2.计算方法：计算方法：（二元函数（二元函数）完成第二轮迭代。两个点进行搜索，得第二轮的方向沿为迭代起始点，再依次作轮以完成了一轮迭代。第二。对二维问题得，确定作一维搜索即坐标方向为新起点，沿再以第一个迭代点，即可获得第一轮的优步长最，按照一维优化法确定方向搜索，即沿第一个坐标轴作为第一轮的始点，任选初始点,;2)1(2)1(1)1(21)1(1)0(2)1(121)0(2)0(2)0(2)0(1)0(2)0(22)0(222)0(101)0(100)0(1)0(1101100exxexxeexdxxe

23、dexxdxxedxx图4-12 坐标轮换法的搜索过程2. 搜索方向与步长的确定（1）搜索方向的确定对于第k轮第i次的计算1kkkkiiiixxa d第k轮第I次的迭代方向，它轮流取n维坐标的单位向量。0.1.0kiide 3.搜索步长的确定关于 值通常有以下几种取法（1）加速步长法（2）最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭代，即此时可以采用0.618方法或二次插值方法来计算 的值。)( ki3. 3. 方法评价：方法评价：（1）方法简单，容易实现。（2）当维数增加时，效率 明显下降。（3）收敛慢，以振荡方式 逼近最优点。（4）受目标函数的性态影 响（等值线的形状）很

24、大。a) 搜索有效。目标函数等值目标函数等值线出现山脊，线出现山脊，若搜索到若搜索到 A A 点，沿脊线方点，沿脊线方向一步可达最向一步可达最优点但此法总优点但此法总是沿两个坐标是沿两个坐标轴方向，找不轴方向，找不到最优点。到最优点。b) 搜索低效搜索低效c) 搜索无效搜索无效第八节 Powell法（方向加速法） Powell法是利用共轭方向可以加速收敛的性质所形成的一种搜索算法。一、共轭方向的生成一、共轭方向的生成是共轭方向。是共轭方向。与与，则称，则称的两个极小值点，若的两个极小值点，若进行一维搜索而得到进行一维搜索而得到出发，沿同一方向出发，沿同一方向为从不同点为从不同点和和设设jkkk

25、kjkkddxxddxx11图4-15 通过一维搜索确定共轭方向1x对于二维问题，f（x）的等值线为一族椭圆，A、B为 沿方向上的两个极小点，则A、B两点的连线就与 轴一起对G共轭。1x图4-16 二维情况下的共轭方向2. 2. 共轭方向的定义：共轭方向的定义：共轭。阵则称这组向量是关于矩能满足若有一组非零向量，为正定实对称矩阵设正交。和则即，时则，为单位矩阵若的方向是共轭方向。和是关于矩阵共轭，和则称向量满足，和维向量若有两个，为实对称正定矩阵设AjiASSSSSASSSSISSIASSSSASSSSnAjTinTTT),(0,., 00,021212121212121214.84.8 Po

26、weel Poweel 法法点点。作作为为下下一一轮轮的的迭迭代代起起始始，得得点点沿沿此此方方向向作作第第三三次次搜搜索索，构构筑筑共共轭轭方方向向：。分分别别求求得得点点作作两两次次一一维维搜搜索索，标标轴轴方方向向，依依次次沿沿两两个个坐坐任任选选一一初初始始点点第第一一轮轮迭迭代代：03100300210201210,xxxxxdxxeex3. 3. 步骤步骤（二维）（二维）030201121xxxdee、得得到到点点：、方方向向组组：。极小点是而得到的点，所以它就进行两次搜索、方向的两个共轭发，分别沿出相当于从。得点，沿此方向作第三次搜索构筑共轭方向：。分别求得点方向作两次一维搜索，

27、分别沿令第二轮迭代：*2101313101221211121003G,xddxxxxxdxxdexx131211212xxxdde、得到点：得到点：、方向组：方向组： 因为两条平行线因为两条平行线 d d1 1与同心椭圆族相切，与同心椭圆族相切，两个切点的连线两个切点的连线 d d2 2 直指中心。称直指中心。称 d d1 1与与 d d2 2 为共轭方向。为共轭方向。目的目的：以共轭方向打：以共轭方向打破振荡，加速收敛。破振荡，加速收敛。图 4-17二维情况下的Poweel 法4. 4. 说明：说明：l 若是n维正定二次函数，n 轮迭代后收敛于最优点 x* 。 若是非正定二次函数，则迭代次数

28、增加。l 若是 n 维问题，步骤相同。 搜索方向：第一轮迭代，沿初始方向组 ei(0) (i=1,2,n) 的 n 个方向和共轭方向 d(1)，搜索 n+1 次得极值点 xn+1(1) ；第二轮迭代，沿方向组 ei(2) ( i=1,2,n；im ) 的 n-1 个方向和共轭方向 d(1)，构筑共轭方向 d(2) 搜索 n+1次得极值点 xn+1(2) 。其中，为保证搜索方向的线性无关，去除了 Sm(2) 方向 。5. 5. 方法评价：方法评价：l 计算步骤复杂;l 是二次收敛方法，收敛快。对非正定函数，也很 有效;l 是比较稳定的方法。 l 在第 k 轮迭代中，为避免产生线性相关或近似线性相

29、关，需要去除前一轮中的某个方向 Sm(k)。 Poweel法的改进在鲍维尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原来向量组中的第一个向量，而不管它的“好坏”。所以可能产生线性相关的向量组。改进的算法是：首先判断原向量组是否需要替换。如需要替换，还要进一步判断原向量组中的哪个向量最坏，然后再用产生新的向量替换这个最坏的向量，以保证逐次生成共轭方向。、值值为反射点。对应的函数为反射点。对应的函数为终点，为终点，为这轮搜索的始点，为这轮搜索的始点，得点，得点沿此方向作第三次搜索沿此方向作第三次搜索，构筑共轭方向：构筑共轭方向：。分别求得点分别求得点作两次一维搜索，作两次一维

30、搜索，标轴方向标轴方向，依次沿两个坐，依次沿两个坐任选一初始点任选一初始点第一轮迭代：第一轮迭代：)()()(.,1030220010030200300210201210 xfFxfFxfFxxxxxxxdxxeex 步骤步骤: :)(kiixff 数值，并记为：同时计算各中间点的函),.2 , 1 , 0(ni nfFfF200,因此有mminimiiinnffniffffffffn 11112110max), 2 , 1(,其中最大者记作：记作：个函数值之差计算3）根据是否满足判别条件2302032003)(5 . 0)(2(FFFFFFFFFmm和来确定是否对原方程组进行替换。若满足条件

31、，则下轮迭代仍用原方向组，并以终点和反射点中函数值较小者作为下轮迭代起点。若不满足条件，则下轮迭代应对原方向组进行替换，将dkn+1补充到原方向组的最后位置，而除掉dkm。迭代始点取反射点。4）判断是否满足收敛准则。4.9 4.9 单形替换法单形替换法1. 1. 基本原理：基本原理： 单纯形：指在单纯形：指在n n维空间中具有维空间中具有n+1n+1个顶点的多面体。个顶点的多面体。 当当n=1n=1时，即一维问题时单纯形是直线。时，即一维问题时单纯形是直线。 当当n=2n=2时，即二维问题时单纯形是三角形。时，即二维问题时单纯形是三角形。 当当n=3n=3时，即三维问题时单纯形是四面体。时，即

32、三维问题时单纯形是四面体。基本原理：利用单纯形的顶点，计算其函数值并加以比基本原理：利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找到一个较好较，从中确定有利的搜索方向和步长，找到一个较好的点代替原来的单纯形中较差的点，组成新的单纯形的点代替原来的单纯形中较差的点，组成新的单纯形代替原来的单纯形。新的单纯形不断地向目标函数的代替原来的单纯形。新的单纯形不断地向目标函数的极小点靠近，直到搜索到极小点。极小点靠近，直到搜索到极小点。4.9 4.9 单形替换法单形替换法2. 2. 方法方法（二维（二维）：反射、收缩、扩张、缩边）：反射、收缩、扩张、缩边x1x8x7x6x5x

33、4x2x3。的反射点，并计算的反射点，并计算称作称作的方向，取的方向，取点点的中的中和和向进行搜索，即通过向进行搜索，即通过反对称方反对称方进行反射：向最差点的进行反射：向最差点的最差。此时最差。此时最好最好，说明，说明计算函数值并作比较计算函数值并作比较。、在平面上任取不同三点在平面上任取不同三点)()(,)()()(515144543211332132xfxxxxxxxxxxxxxfxfxfxxx1分以下几种情况：反射4.9 4.9 单形替换法单形替换法x1x8x7x6x5x4x2x3。，构成新单纯形则舍弃否构成新单纯形代替说明扩张有利，以，如果计算因子取为扩张称作扩张点，方向正确，做扩张：取说明反射点好，搜索5326632165666144635)()()(0 . 22 . 1)()()(xxxxxxxxxxfxfxfxxxxxxfxf扩张4.9 4.9 单形替换法单形替换法无无效效。否否则则成成新新单单纯纯形形，构构。若若子子，取取为为收收缩缩因因，点点缩缩走走的的太太远远，应应收收缩缩，收收说说明明差差。好好，比比次次差差点点比比最最差差点点点点，说说明明反反射射若若773217447515152)()()()()()(xxxxxfxfxxxxxxxxxfxfxf0.552x1x8x7x6x5x4x2x3收缩。单单纯纯