第八章 无约束多维问题的最优化方法

1、第八章第八章 无约束多维问题的无约束多维问题的最优化方法最优化方法1 概述概述2 最速下降法最速下降法3 牛顿型方法牛顿型方法4 共轭方向及共轭方向法共轭方向及共轭方向法5 共轭梯度法共轭梯度法6 变尺度法变尺度法7 坐标轮换法坐标轮换法8 鲍威尔法鲍威尔法9 单形替换法单形替换法1 1 概概 述述 无约束优化方法只考虑搜索的适行性，结合罚函数法，也可解约束优化问题。目前，成熟可靠的优化算法中，无约束优化方法占多数，总体上无约束优化方法的有效性及实用性都优于约束优化方法。 无约束优化方法可分为两大类：1)不求导数的，主要有随机方法和直接搜索方法；2)求导数的，按所求导数的最高阶数又可分为一阶方

2、法和二阶方法。二阶方法很少采用。优化算法的一般搜索迭代公式 xk+1= xk+xk xk+1= xk+kdk 注意，在搜索迭代中，由于一维搜索需增加大量计算，因此，并不是所有优化方法都采用一维搜索。2 2 最速下降法最速下降法 (1)以负梯度方向作为搜索方向并作一维搜索，因此又称为“梯度法”，属于求导数的间接法。它的基本思想早在1847年就已提出。尽管它本身不再被认为是一种有效的方法，但它是许多优化方法尤其是二次收敛方法的基础。 各点的梯度一般各不相同，因此“最速下降方向”仅对某一点附近而言，它具有局部性质。 当作一维搜索时，搜索方向是与目标函数等值线相切的，而切点的梯度方向是与等值线正交的。

3、因此，相邻两次搜索方向相互垂直，搜索路径呈严重的“之”字形，特别是目标函数接近二次型时更为明显。 可以利用梯度矢量在极值点为零这一重要性质设立收敛准则 f(x*) 2 2 最速下降法最速下降法 或nixfii, 2 , 1 数值微分在优化中是一个非常重要的问题，对优化结果影响较大。具体作法是用 代替 ，其中xfxf f = f f0式中，f0 = f(x0)，是计算偏导数那点 x0 处的目标函数值； f = f(x) = f(x1, x2, , xi+xi, , xn)，是其它变量保持不变，xi 变化为 xi+xi 时的目标函数值。 xi = 0.001(ui li) ui 和 li 分别为变

4、量 xi 的估计上限和下限。xfxf尽可能接近，xi 应取得小一些，但过小又 为使会引起舍入误差。一般可取2 2 最速下降法最速下降法 求 f(x1, x2) = x12+25x22 的极小点。 取初始点 x0 =2 2T，则 f(x0) =104 f(x0) =4 100T 沿负梯度即-4 -100T方向进行一维搜索，有 x1 = x0 0 f(x0) =2 2T 04 100T = 2 40 2 1000T 在x1点 f(x1, x2) =(2 40)2+25(2 1000)2 =(0) 令(0) = 0，有 2(2 40) (-4)+50(2 1000) (-100) = -16+320

5、 10000 +5000000 = 5000320 10016 = 0 0 = 0.020030718 得到第一次迭代的结果： x1 = 2 40 2 1000T= 1.919877 -3.0718034-2T f(x1) =3.686164 经过十次迭代，得到最优解： x* = 0 0T f(x* ) =03 3 牛顿型方法牛顿型方法 是用目标函数二阶偏导数的间接方法，因类似于解非线性方程的牛顿法而得名，又叫“二阶导数法”、“拟线性法”。 将目标函数泰勒展开，保留到二次项，原目标函数就转变为下列二次型函数： f(xk)+2f(xk)(x* xk) = 0 对于二次型函数，从理论上来说，牛顿法

6、从任选初始点一步就能收敛到最优点。但对于目标函数不是二次型，或计算机截断误差的影响，往往需要多次迭代才能得到最优点。牛顿法的迭代公式为： xk+1 = xk 2f(xk)-1f(xk) (k=0, 1, 2, )2f(xk)为f(x)在xk点处的海赛矩阵。21 f(x) (x)= f(xk)+f(xk)T(x xk)+ (xxk)T2f(xk)(xxk) 为求极值点，对上式求偏导数，并令xf=0，得到3 3 牛顿型方法牛顿型方法 为防止牛顿法收敛到极大点而不是极小点，可在迭代过程中作一维搜索，形成改进的牛顿法“阻尼牛顿法”。 牛顿法的最大缺点是需要计算海赛矩阵，并求其逆矩阵，计算量很大。 用牛

7、顿法求 f(x1, x2) = x12+25x22 的极小点。 取 x0 = 2 2T f(x0) = 2x10 50 x20 T = 4 100T 50100215000210202xxff3 3 牛顿型方法牛顿型方法 因为f(x1, x2)是二次型函数，用牛顿迭代公式，一步就可达到最优点： 对照梯度法和牛顿法迭代公式，可以看出只相差一项海赛矩阵的逆矩阵。因此，牛顿法是对梯度法的进一步修正。事实上，梯度法是对目标函数f(x)在点xk的一阶(线性)近似，而牛顿法是对f(x)在点xk 的二阶(二次)近似。000100501401000421221004501002122xxfTTTTT4 4 共

8、轭方向及共轭方向法共轭方向及共轭方向法 二次正定函数的一般形式为：式中，G为 nn 阶对称正定矩阵，b=b1, b2, ,bnT 为常矢量，c为常数。 对于矩阵 G，若存在两个 n 维非零矢量 d0 和 d1，使 (d0)TGd1=0成立，则称d0和d1是(或G共轭矢量)。特别地，当G为单位矩阵时，(d0)Td1=0 ，则称d0 和d1是的。矢量正交是矢量共轭的特例。 cfTTxbGxxx214 4 共轭方向及共轭方向及共轭方向法共轭方向法x1x2 如n=2，二次函数的等值线为一同心椭圆族，它的极小点就是椭圆中心。该椭圆族有一重要性质，即两平行线与椭圆的两个切点的连线必过椭圆族的中心，且连线与

9、平行线的方向是共轭的(见下图)。4 4 共轭方向及共轭方向法共轭方向及共轭方向法 因此，从任一点出发，沿任意方向作一维搜索找到的极小点就是椭圆的切点，再沿共轭方向作一维搜索找到的极小点就是椭圆中心也就是目标函数的极小点。这说明，对二维二次正定目标函数只要沿共轭方向作两次一维搜索就可得到其极小点。 推广到n维，若采用共轭方向作为搜索方向，任何一个具有极小值的n维二次正定目标函数，理论上最多只要n步就能达到极小点且与所用搜索方向的次序无关。这种性质称为“”，利用这种性质的优化方法称为。4 4 共轭方向及共轭方向法共轭方向及共轭方向法 共轭方向是一大类方法，包括共轭梯度法，Powell法等。其中一种

10、产生共轭方向的方法为格拉姆斯密特 (GramSchmidt)法。 比较有效的共轭方向法都尽量避免计算海赛矩阵。5 5 共轭梯度法共轭梯度法 gk = Gxk + b 前面已给出优化算法的搜索迭代公式： xk+1= xk+kdk 若进行一维搜索，k 则为最优步长因子。 xk 和xk+1 两点负梯度方向的差为 gk+1 gk = G(xk+1 xk) = G(xk+kdk xk)=k Gdk 若dk+1 和 dk 是G 共轭方向，则 (dk+1)TG dk = 0 用(dk+1)T前乘 (gk+1 gk)，有 (dk+1)T(gk+1 gk) = k(dk+1)TGdk = 0 即 dk+1与(g

11、k+1 gk)正交。 二次正定函数 cfTTxbGxxx21在 xk 点的梯度为 5 5 共轭梯度法共轭梯度法 上式表明：。因此，利用这个性质，不必计算矩阵G 即可求出共轭梯度法的共轭方向。Xk+2xkxk+1gkgk+1gk+1 gkdkdk+15 5 共轭梯度法共轭梯度法 设从xk出发，沿dk=-gk 方向作一维搜索到 xk+1点，并算出xk+1点的梯度方向gk+1。由于gk+1 是沿等直面在该点的法线方向，而dk是沿等直面在该点的切线方向，故(dk)Tgk+1= 0，即 ，。 为了在 gk+1 和 gk 构成的正交系中确定共轭方向dk+1，令 dk+1 = -gk+1+k dk 即把共轭

12、方向dk+1看成-gk+1与 dk的线性组合，k 为待定系数。要使dk+1与dk 共轭，就应使 (dk+1)TGdk =0而 (dk+1)TGdk =(-gk+1+kdk)TGdk =(-gk+1 kgk)TG(-gk ) =gk+1TGgk+k gkTGgk =05 5 共轭梯度法共轭梯度法 因此kTkkTkkGggGgg1 前面已推导出 gk+1 gk = k Gdk，即 gk+1 gk = -kGgk或代入上式得kkkkggGg122111111111111100kkkTkkTkkTkkTkkTkkTkkTkkTkkkTkkkTkkTkkTkkgggggggggggggggggggggg

13、ggGggGgg5 5 共轭梯度法共轭梯度法 因此,下一个搜索方向确定为kkkkkkkkdgggdgd221111 同样,可以证明按上述公式确定的 dk+2与dk+1为共轭方向，依此类推而确定的 n个dk (k=0,1,2,n-1)方向为一组关于G的。上述结论也可由数学归纳法证明。 最后，我们得到共轭梯度法的迭代公式为 x k+1 = x k+k dk式中 dk = -gk+k-1 dk-12121kkkgg 在迭代中第一次搜索方向 d0 取 x0 的负梯度方向-g0。5 5 共轭梯度法共轭梯度法 与梯度法相比，由于修正项kdk 改进了收敛性，使搜索方向共轭，故能以较少的迭代次数收敛到最优点。

14、 由于计算梯度时很可能出现误差，使搜索方向不能完全保持共轭，同时目标函数也可能不是正定的二次函数，因此n次迭代后一般都不会达到精确的极小点。可在每n次迭代后令 d0 = dn = -gn作为下一轮迭代的第一次搜索方向，重新开始新一轮迭代。 上述共轭梯度法又称。而PRP(Polak-Ribiere-Poiyak)共轭梯度法按下式计算k-1：1111kTkkTkkkggggg5 5 共轭梯度法共轭梯度法 1)给定变量个数n，选取收敛精度和初始点x0，计算x0点的梯度 g0，取第一次搜索方向d0 = -g0 ，令k = 0。 2)沿dk方向作一维搜索，得到 xk+1点，xk+1= xk+k dk 。

15、 k k +1。转2)继续进行迭代。2121kkkgg则结束迭代，输出当前点作为最优点。否则，若k=n，dk= -gk，k0，转2)进行新一轮迭代。若kn，dk按下式计算: dk=-gk+k-1dk-1，其中kg 3)计算当前点的梯度 gk ，若迭代收敛准则成立，5 5 共轭梯度法共轭梯度法 用共轭梯度法求f(x1, x2) = x12+2x22 4x1 2x1x2的极小点。 取 x0 = 1 1T d0 = -g0 = -2x1 2x2 4 4x2 2x1x0 = 4 -2T 沿 d0 进行一维搜索 x1 = x0+0 d0 =1 1T+04 -2T = 1+40 1 20T 在x1点 f(

16、x1, x2) =(1+40)2+2(1-20)2 4(1+40) 2(1+40)(1 20) 令df/d0 = 0，有 8(1+40) 8(1 20) 16 2(2 160) = 8+320 8+160 16 4+320 = 800 20 = 0 0 = 0.25 x1 = 2 0.5T g1 = 2x1 2x2 4 4x2 2x1x1 = -1 -2T 25. 020500110ggggTT5 5 共轭梯度法共轭梯度法 d1 = -g1+0 d0 = 2 1.5T 沿d1 进行一维搜索 x2 = x1+1d1=2 0.5T+12 1.5T = 2+21 0.5+1.51T 在 x2点 f(

17、x1, x2) =(2+21)2+2(0.5+1.51)2 4(2+21) 2(2+21)(0.5+1.51)令 df/d1 = 0，有 4(2+21)+6(0.5+1.51) 8 2(4+61) = 8+81+3+91 8 8 121 = 51 5 = 0 1 = 1 x2 = 4 2T 因为 g2 = 0 0T，且在 x2 点处海赛矩阵正定，故 x2 为极小点。 x* = x2 = 4 2T f(x*) = -86 6 变尺度法变尺度法 又被称为“拟牛顿法”、“大步梯度法”、“共轭方向法”，其中最有名的是DFP算法。 变尺度法是在牛顿法的基础上演变发展的，但它是一阶方法，不求二阶偏导数，而

18、是用一个矩阵近似表示海赛矩阵的逆矩阵，然后在搜索迭代过程中不断修正这个矩阵，使它逐步逼近海赛矩阵的逆矩阵。 通过可改进收敛性。对于一般二次函数 cfTTxbGxxx21 进行尺度变换 xQx，则二次项GQxQxGxxTTT2121若G正定，则总存在矩阵Q使 QTGQ = II 为单位矩阵。6 6 变尺度法变尺度法 用Q-1左乘等式两边，再用Q左乘等式两边，得到 QQTG = I即 QQT = G-1令 H = QQTH 称为，要求H 正定。则牛顿法迭代公式变为 xk+1 = xk kHf(xk) (k=0, 1, 2, ) 用尺度矩阵逼近海赛矩阵的逆矩阵G -1，则构成一个尺度矩阵序列Hk。因

19、此，尺度在不断变化，迭代公式为 xk+1 = xk k Hk gk (k=0, 1, 2, ) gk f(xk)6 6 变尺度法变尺度法 对Hk的要求：1) Hk应对称正定。2) Hk之间的迭代应具有下列简单的形式： H k+1 = H k+ Ek Ek为nn 阶矩阵，称为。3) Hk必须满足拟牛顿条件 H k+1 yk = sk yk gk+1 gk sk xk+1 xk6 6 变尺度法变尺度法 根据校正公式中Ek选取的不同，形成不同的变尺度法，其中最著名的为DFP算法。DFP算法中Ek取下列形式： Ek = k uk ukT+k vk vkT式中k、k 为待定常数，uk、vk 是n维待定向

20、量，ukukT 和 vkvkT 都是对称、秩为1的n n 阶矩阵。 取k 、k 、uk、vk，使它们满足： kuk ukTyk = sk k vk vkTyk =-Hk yk注意到uyk和vyk均为1 1阶矩阵即常量，可取 uk = sk vk = Hk yk定出 kkTkkkkTkyHyys116 6 变尺度法变尺度法 因此，DFP算法校正公式为 用DFP法求f(x1, x2) = x12+2x22 4x1 2x1x2的最优解。 1)取x0 = 1 1T k=0 g0 = -4 2T H0 = I d0 = - H0 g0 = 4 -2T 沿d0进行一维搜索 x1 = x0+0 d0 = 1

21、+40 1 20T 令df/d0 = 0, 得到 0 = 0.25， x1 = 2 0.5T 2) k = 1 g1 = -1 -2T y0 = g1 g0 = 3 -4T s0 = x1 x0 = 1 -0.5T kkTkkTkkkKTkTkKKKyHyHyyHysssHH16 6 变尺度法变尺度法 d1 = - H1 g1 = 0.84+0.76 0.38+0.82T= 1.6 1.2T x2 = x1+1 d1 = 2+1.61 0.5+1.21T 令df/d1 = 0, 得到 1 = 1.25， x2 = 4 2T 3) g2 = 0 0T41. 038. 038. 084. 0161

22、212925125. 05 . 05 . 0151100143434343435 . 015 . 015 . 0110010000000000100yHyHyyHysssHHTTTT (x2)T2f(x2)x2 = 4 0 4 2T =16 0 2f(x2) 正定 x* = x2 = 4 2T f(x*) = -8422222xf7 7 坐标轮换法坐标轮换法 坐标轮换法属于不求导数的直接搜索法。它的基本思想是取x的n个坐标方向作为搜索方向，即从x0出发，第一次搜索沿x1坐标方向，第二次搜索沿x2坐标方向，第n次搜索沿xn坐标方向，第n+1次搜索沿x1坐标方向，依次类推。搜索不断沿坐标方向轮换进

23、行，直到收敛条件被满足。坐标轮换法一般不作一维搜索。 坐标轮换法的算法如下： 1)选取初始点x0(x0又称为)，初始步长xi，收敛精度i。一般初始步长可取为变量估计变动范围(uili) 的1/100，收敛精度i可取为初始步长xi的1/100。令k=0。 2) k k+1。进行一轮依次沿坐标方向的。先给x1 一个增量x1，其它变量保持不变，得到一个试验点Tknkksxxxx112111,x7 7 坐标轮换法坐标轮换法 检验 xs 的适行性。若f(xs) f(xk-1)，则xs 就作为下一个坐标方向搜索的起点；否则，从xk-1点沿反方向搜索Tknkksxxxx112111,x 若两个方向的搜索都失

24、败了，则停在原来的点不动。 接着，以步长x2沿x2坐标方向搜索，直到 xn为止。此轮探查搜索的终点称为xBk。 3)作 (Pattern Move) 到点xMk。模式移动的方向是从前一个基点xBk-1到当前基点xBk，移动量是两基点之间的距离，即 检验模式移动的适行性。若f(xMk)f(xBk)，则xMk就作为下一轮搜索的起点；否则，取消此次模式移动，xBk作为下一轮搜索的起点。1kBkBkBkMxxxx7 7 坐标轮换法坐标轮换法 4)重复2)、3)的搜索模式移动的循环，直到各个坐标方向探查搜索都失败，仍停留在原基点不动为止。检验收敛准则 xiI 是否满足。若不满足，则将各变量步长xi (i

25、 =1, 2, n) 都减少一半，重新开始新一轮探查搜索；若满足，则输出最优点x*= xBk。 用坐标轮换法解 f(x) = x12+x226(x1 + x2) + x3min. 求经过一轮探查搜索和模式移动后的终点xM(1)。 1)选取变量估计下限xl = 0 0 0T，变量估计上限xu = 10 10 10T，初始点x0 = xB(0)=5 5 5T，初始步长x1=x2= x3= 0.1，收敛精度1= 2= 3= 0.001 。求出 f0 =f(x0) = -5 2)进行探查搜索。 向正向搜索：xs = 5.1 5 5T，f(xs) = -4.59 （不适行） 向反向搜索：xs = 4.9

26、 5 5T，f(xs) = -5.39 （适行）7 7 坐标轮换法坐标轮换法 向正向搜索：xs = 4.9 5.1 5T，f(xs) = -4.98 （不适行） 向反向搜索：xs = 4.9 4.9 5T，f(xs) = -5.78 （适行） 向正向搜索：xs = 4.9 4.9 5.1T，f(xs) = -5.68 （不适行） 向反向搜索：xs = 4.9 4.9 4.9T，f(xs) = -5.88 （适行） 因此，xB(1)= 4.9 4.9 4.9T，f(xB(1) = -5.88。 3)作模式移动 xM(1)= xB(1)+(xB(1) xB(0) ) =4.9 4.9 4.9T+(

27、4.9 4.9 4.9T 5 5 5T) =4.9 4.9 4.9T+-0.1 -0.1 -0.1T =4.8 4.8 4.8T 由于f(xM(1)=-6.72 f(xB(1)，因此模式移动满足适行性，点4.8 4.8 4.8T 作为下一轮探查搜索的起点。 7 7 坐标轮换法坐标轮换法 坐标轮换法被认为是目前最成功的优化算法之一，至今仍被广泛应用着。国外有些专家曾以工程实际中实际提出的优化设计问题作为考题，对各种优化方法进行专门研究对比，坐标轮换法是名列前茅的算法之一。坐标轮换法的缺点是有时收敛较慢。由于其搜索方向是固定的，如果恰好遇到某些约束曲面的走向对它的搜索特别不利时，往往会在接近最优点

28、之前，“粘”在约束边界上中止收敛而得到一个假最优点。针对这个缺点，已提出了一些改进措施。如:；8 8 鲍威尔法鲍威尔法 (Powell)法的搜索方向是共轭的，但不需要计算目标函数的导数，这是它的一大优点。 二次正定函数 cfTTxbGxxx21在xk 和xk+1点的梯度为 gk = Gxk + b gk+1 = Gxk+1 + b gk+1 gk = G(xk+1 xk ) = Gdk 设xk、xk+1为沿同一方向dj进行一维搜索得到的两个极小点，因此dj和梯度方向正交(图4-15)，有 (dj)T gk = 0 (dj)T gk+1 = 0 根据共轭方向的定义(式4-11)，有 (dj)T

29、(gk+1 gk ) = (dj)TG dk = 0 因此，dj和dk是G共轭方向。8 8 鲍威尔法鲍威尔法 图4-17为 Powell 法搜索过程。 1) 任选一初始点x0，确定收敛精度，选择坐标轴方向ei (i= 1,2, . ,n)为第一轮搜索方向，令k = 0, xB(0) = x0。 2) k k+1。从xB(k-1)出发，分别沿ei (i= 1,2, . ,n)作一维搜索，此轮搜索的终点为xB(k) 。 3) 作模式移动。沿dk = xB(k) xB(k-1)作一维搜索，得到xk，作为下一轮搜索的起点。 4) 检验收敛准则。如满足则输出当前点xk作为最优点。 5) 若未收敛，则重复

30、2)、3) 的一维搜索和模式移动，但每一轮一维搜索中都用上一轮模式移动方向代替原有的一个坐标轴方向。如第二轮搜索方向为e2, e3, en, d1，依次类推。8 8 鲍威尔法鲍威尔法 框图见图4-18。在每一轮搜索后，模式移动与坐标轮换法的相同而不作一维搜索。另外增加了Powell 判别条件，若满足判别式，则用模式移动方向替换目标函数值下降量最大的一个方向，以保证下一轮搜索方向组线性无关。 用Powell法求f(x1, x2) =10(x1+x2 5) 2+(x1 x2)2 的极小值。 选取x0(0) = 0 0T，F0 = f0 = 250。第一轮搜索：第一轮搜索： 1) 沿e1 = 1 0

31、T方向作一维搜索，得到 x1(0) =4.5455 0T, f1=22.727, 1= f0 f1 =227.273。 2) 沿e2 = 0 1T方向作一维搜索，得到x2(0) = 4.5455 0.8264T, F2 = f2=15.214, 2= f1 f2 =7.513, m = 1= 227.273。 3) 模式移动: x3(0) =2 x2(0) x0(0) = 9.091 1.6528T F3 = f(x3(0) = 385.248 8 鲍威尔法鲍威尔法 4) 检验Powell 判别条件。因为 F3 F0，因此下一轮搜索方向仍用e1 、e2方向。因为 F2 F3，因此x2(0)作为

32、下一轮搜索的起点。第二轮搜索：第二轮搜索： 起点x0(1) = x2(0) = 4.5455 0.8264T, F0 = f0=15.214。 1) 沿e1=1 0T方向作一维搜索，得到x1(1) = 3.8693 0.8264T, F1= f1=10.185, 1= f0 f1 =5.029。 2) 沿e2 = 0 1T方向作一维搜索，得到x2(1) = 3.8693 1.3797T, F2 = f2=6.818, 2= f1 f2 =3.367, m = 1= 5.029。 3) 模式移动: x3(1) =2 x2(1) x0(1) = 3.1931 1.9330T F3 = f(x3(1

33、) = 1.747 4) 检验Powell 判别条件。因为 F3 F0 且(F0 2F2+F3 ) (F0 F2 m)2 0.5m (F0 F3)2，故用模式移动方向 d3(1) = x2(1) x0(1) = -0.6762 0.5533T代替e1。沿d3(1)方向作一维搜索，得到下一轮搜索的起点： x0(2) = 2.49995 2.5091T F0 = f0 = 0.0008 若不满足收敛准则，则再进行第三轮搜索。9 9 单形替换单形替换法法 又称Simplex)法，属于直接搜索方法。 就是在n维空间中由n+1个顶点构成的形体。在优化搜索过程中要满足适行性，就要对目标函数的变化趋势有大概

34、的估计，避免盲目选择搜索方向。可以根据若干点的目标函数值大小的变化推测这种趋势，这些点可取为单纯形的顶点。单纯形的基本思想是利用单纯形的顶点构造有利的搜索方向和步长，用新的较好点取代原来较差的点，构成新的单纯形，不断向最优点逼近。 假定在一个二维问题中，已求得不在一条直线上的三个点H、S、L，及它们的目标函数值fH、fS、fL，且fH fS fL。这三点构成一个单纯形三角形。如有更好点，则在最差点H的反对称方向可能性最大。9 9 单形替换单形替换法法 因此，取S和L两点的中点M，从H出发沿H和M的连线作模式移动到A点。然后舍弃H点，剩下的S、L和A又构成一个单纯形。推广到n维的情况，仍在单纯形的n+1个顶点中取三个点。H为最差点，S为次差点、L为最好点，M为除H点外其它各点的中点(或称“重心”)，模式移动的方向仍在过H和M的连线上。 1) 建立初始单纯形。选择一个初始点x0，再依次改变其中一个变量的值，给变量一个事先确定的步长xj，得到另外n个点xi (i = 1, 2, . , n)。每个点由下两式确定： xj (1) = xj (0) +xj ( j = i ) xj