非线性规划
南京航空航天大学经济与管理学院
党 耀 国
教授、博士生导师
管理科学与工程系主任
无约束极值问题
现在我们来研究n元函数的无约束极值问题。
这种问题的表达式为：
Min f(X) XE(n) (1)
为求此问题的最优解或近似最优解，常使用搜索法，并要进行若干次迭代。
当用迭代法求解问题（1）时，常从某一近似点X(k)出发，接着在这一点选定一搜索方向P(k)，使目标函数值沿该方向下降，然后选择步长，沿P(k)方向移动一个步长，即可得下一个近似点X(k＋1)
X(k＋1)＝ X(k) ＋ P(k)
且满足 f(X(k＋1))< f(X(k))
这样即可逐步趋近极小点，当满足精度条件
|| f(X(k＋1)) ||2<1, |f(X(k＋1))- f(X(k)) |<2时，停止迭代。
在求解无约束极值问题时常用迭代法，迭代法大致上可分为两大类。一类要用到函数的一阶导数或二阶导数，由于用到了函数的解析性质，故称为解析法。
另一类迭代过程中仅用到函数值，而不要求函数的解析性质，这种方法称为直接法。
一般来说，直接迭代法的收敛速度较慢，只是在变量个数较少时才适用。但直接法的迭代步骤简单，特别是目标函数的解析式十分复杂时，或写不出具体表达式时，这时求导就很困难，或导数不存在，这时只有利用直接法，下面介绍几种常用的基本方法。
该方法是1847年柯西提出的，它是求解无约束极值问题的解析法中最古老但又十分基本的一种方法，它的迭代过程简单，使用方便，对初始点的选取要求不严。
假设无约束极值问题中的目标函数f(x) 有一阶连续偏导数，且有极小点x*。我们取一初始近似点x(0)和一方向g(0)，作射线
x=x(0)+ 0 g(0) 0 >0
这里的方向g(0)和步长 0都是待定的。
一、梯度法（最速下降法）
为了使f(x) 的函数值在x(0)沿方向g(0)移动步长 0后有所下降，我们将f(x)在x(0)上展开泰勒级数
f(x(0)+ 0 g(0))= f(x(0))+ 0 f(x(0) )T g(0)+o( 0 )
只要 0 f(x(0) )T g(0)<0,就可以保证f(x(0)+ 0 g(0))< f(x(0))
若记x(1)＝ x(0)+ 0 g(0)，则 f(x(1) ) < f(x(0) )
现在的问题就是如何方向g(0)和步长 0，
使 0 f(x(0) )T g(0)尽可能的小。
由于 f(x(0) )T g(0)＝ || f(x(0) )T ||. || g(0) ||cos,
是向量 f(x(0) )T 与g(0)的夹角。
只有 f(x(0) )T 与g(0)反向时， f(x(0) )T g(0)最小
即： g(0)＝ － f(x(0) )
由此可以看出，函数在处沿梯度的反方向是函数值下降最快的方向。
由于优化设计是追求目标函数值最小，因此，自然可以设想从某点出发，其搜索方向取该点的负梯度方向，使函数值在该点附近下降最快。这种方法也称为最速下降法。
1、基本原理 梯度法的迭代公式为： x(k+1)=x(k)-(k)g(k) 其中g(k)是函数f(x)在迭代点x(k)处的梯度f(xk) ， (k)一般采用一维搜索的最优步长，即 f(x(k+1))=f(x(k)-(k)g(k))
=min f(x(k)-(k)g(k))=min()
因为
f(x(k)— f(x(k) )= f(x(k))- f(x(k) )T f(x(k) ) +
2 f(x(k) )T H(x(k) ) f(x(k) )/2 +o(2)
df(x(k)— f(x(k) )/d = - f(x(k) )T f(x(k) ) +
f(x(k) )T H(x(k) ) f(x(k) )=0
= f(x(k) )T f(x(k) ) / f(x(k) )T H(x(k) ) f(x(k) )
称为最优步长。它不但与梯度有关，而且与海赛矩阵 H(x(k) )有关。
根据一元函数极值条件和多元复合函数求导公式，得 ’()= -( f(x(k)-(k)g(k)))T g(k) =0 即 （ f(x(k+1)))T g(k) =0 或 (g(k+1))Tg(k)=0
即 （ f(x(k+1)))T f(x(k)) =0
此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。 这是因为，梯 度是函数的局部性质， 从局部上看，在该点 附近函数的下降最快， 但从总体上看则走了 许多弯路，因此函数 值的下降并不快。
2、迭代终止条件 采用梯度准则： || g(k) ||
3、迭代步骤 （1）任选初始迭代点x(0)，选收敛精度 。 （2）确定x(k)点的梯度（开始k=0) （3）判断是否满足终止条件|| g(k) || ？若满足输出最优解，结束计算。否则转下步。 （4）从x(k)点出发，沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点 x(k+1)=x(k)-(k)g(k) ，令k=k+1 返回步骤（2）。
4、梯度法流程图
入口
给定： x(0)，
k=0
||g(k)|| ？
x*=x(k)
f*=f(x(k))
出口
x(k)= x(0
计算：g(k)
k=k+1
沿g(k)方向一维搜索，
求最优步长(k)。
N
Y
5、例题 试用最速下降法（梯度法）求
64
2
2
1
0
1
2
3
4
5
6
k
由上表可以看出，x(k)随着迭代次数的增加，越来越接近于极小点（0，0），但也应看到，随着迭代次数的增加，收敛速度越来越慢，在极小点附近差不多沿着一种锯齿形状前进。
共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。
1、共轭方向 对于n维欧氏空间中的两个非零向量x和y，
如果 xTy=0 称x和y是正交的。
假设A是n阶对称正定矩阵，如果向量x和Ay正交，即 xTAy=0
称x和y是A共轭的。
若A为单位矩阵时， x和y是A共轭的和x和y是正交是相同的。即A共轭的概念是正交概念的推广。
不过， A共轭与正交之间并与任何联系。
二、共轭梯度法
如
即x和y是A共轭。
而
即x和y也是正交的。
但对于同一矩阵A，向量(1，0)T，(1，-2)T是A共轭。但它们不正交。
一般地，对于n阶对称正定矩阵A，如果 非零向量组x(1),x(2),…,x(n)满足条件
x(i)TAx(j)=0 (i j)
称该向量组为A共轭向量组。
定理：设A为n阶对称正定矩阵， x(1),x(2),…,x(n)为A共轭非零向量组，则该向量组一定线性无关。
由于在n维空间中，任意n个线性无关的向量组都可以构成n维向量空间的一个基。
因而， n个共轭非零向量组也是n维空间的一个基。
下面我们研究二次函数极小化问题。
A 是n阶对称正定矩阵，b是n维向量，C是常数。设X*为极小点，X(0)为任一给定的初始点，如果p(0）,p(1),…,p(n-1)为A共轭向量组，所以向量X*-X(0)可以唯一地表示成这组共轭向量的线性组合。
X*-X(0)＝0 p(0） ＋1 p(1) ＋…＋n-1 p(n-1)
即 X*＝X(0)＋0 p(0）＋1 p(1) ＋…＋n-1 p(n-1)
不难看出，只要能求出0 ,1 ,…,n-1 ,便可求出极小点X*，下面我们来求这些系数。
上式两边左乘(p(k))TA得：
(p(k))TA X*＝ (p(k))TA X(0)＋0 (p(k))TA p(0）＋1 (p(k))TA p(1) ＋…＋n-1 (p(k))TA p(n-1)
因为 (p(k))TA p(j)=0 (j k)
所以(p(k))TA X*－ (p(k))TA X(0) ＝ k (p(k))TA p(k) （1）
另一方面，因为X*是极小点，
所以 f(X* )= A X*+b=0
同时 f(X(0) )= A X（0）+b
代入（1）得：
－(p(k))b－ (p(k))T( f(X(0) )-b)＝ k (p(k))TA p(k)
由此得： k ＝-(p(k))T( f(X(0) ))/((p(k))TA p(k) )
k=0,1,2,…,n-1
顺便指出，这样求出的k实际上是二次函数f(X)从X(k)出发，沿p(k)方向进行一维搜索的最佳步长。
所以欲求极小值问题，只要知道A共轭 的n个方向p(0）,p(1),…,p(n-1) ，而不管初始点X(0)如何选取，如果从X(0)出发，分别沿p(0）,p(1),…,p(n-1)进行一维搜索，那么最多进行n次一维搜索，便可求得极小点X* 。
上述求二次函数极小点的方法称为共轭方向法。
下面是共轭方向p(0）,p(1),…,p(n-1)的如何选取。选取共轭方向的方法很多，使用不同的方法产生的共轭方向就得到不同的共轭方向法。我们这里只介绍一种最简单的方法。
设给定初始点X(1) ，并取第一个方向p(1)＝(1,0,…,0)T，求X(2) ＝ X(1) ＋ 1 p(1)
其中 1是使得二次函数f(X)在X(1)点沿p(1)达到
min f(X(1)+ p(1))= f(X(1)+1p(1))的 。
再从X(2) 出发沿某一与p(1)共轭的方向p(2)进行一维搜索，以确定p(2)＝e2+ 1 p(1),其中e2＝(0,1,0,…,0)T，由于p(2)与p(1)＝e1共轭，将上式两边左乘( p(1) )TA得：
( p(1) )TA p(2)＝ ( p(1) )TA e2+ 1 ( p(1) )TA p(1)
因为A是对称矩阵，所以 1 ＝-a12/a11
得p(2) ＝ e2- (a12/a11)e1=(-a12/a11,1,0,…,0)
从而得X(3) ＝ X(3) ＋ 2p(2)
其中2是使得
min f(X(2)+ p(2))= f(X(2)+2p(2))
的
现在假设已经求出X(k) 以及k-1个A共轭方向p(1）,p(1),…,p(k-1)，为求X(k+1)，必须现求p(k)
p(k)＝ek+ 1 p(1) + 2 p(2)+…+ + k-1 p(k-1) (*)
利用p(k)与p(j) 共轭,，将上式两边左乘(p(j))TA得：
(p(j))TA p(k)＝ (p(j))TA ek+ 1 (p(j))TA p(1) + 2 (p(j))TA p(2)+…+ + k-1 (p(j))TA p(k-1)=0
j=1,2,…,k-1
所以 j ＝- (p(j))TA ek / (p(j))TA p(j)
代入（*）式得p(k) ,显然p(k)与p(j)与A共轭
从而得X(k+1) ＝ X(k) ＋kp(k)
其中k是使得
min f(X(k)+ p(k))= f(X(k)+kp(k))
的
共轭梯度法的特点 共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由于计算机舍入误差的影响，虽然经过n次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。
例：求解
前面介绍了用于正定二次函数的共轭梯度法，下面把这种方法推广到用于极小化任意n元函数。
一、共轭梯度法的搜索方向 设f(X)为某一凸函数，它具有二阶连续偏导数，其唯一极小点为X*。现取初始点X（0），计算 f(x(0))，选取p(0）= f(x(0))为初始搜索方向，作射线X(0) ＋ p(0)，并将f(X)= f(X(0)＋ p(0))于X(0)附近作泰勒展开式：
f(X(0)＋ p(0))＝ f(X(0))＋ f(x(0)) p(0)＋2p(0)TH(x(0)) p(0）/2
上式的为二次函数，因为p(0)TH(x(0)) p(0)>0
故使该二次函数沿p(0)方向取极小值的为
这就是推广后的共轭梯度法的计算公式。它与原来共轭梯度法的差异就是：步长的计算公式发生了改变。在原共轭梯度法中凡是用到A的地方，都要改成当前的海赛矩阵。
牛顿法
为了寻找收敛速度快的无约束最优化方法，我们考虑在每次迭代时，用适当的二次函数去近似目标函数f，并用迭代点指向近似二次函数极小点的方向来构造搜索方向，然后精确地求近似二次函数的极小点，以该极小点作为 f 的极小点的近似值。这就是牛顿法的基本思想。也是单变量牛顿法的推广。
牛顿法是求无约束最优解的一种古典解析算法。 牛顿法可以分为原始牛顿法和阻尼牛顿法两种。实际中应用较多的是阻尼牛顿法。
原始牛顿法
一、原始牛顿法的基本思想 在第k次迭代的迭代点xk邻域内，用一个二次函数去近似代替原目标函数f(x)，然后求出该二次函数的极小点作为对原目标函数求优的下一个迭代点，依次类推，通过多次重复迭代，是迭代点逐步逼近原目标函数的极小点。 如图所示。
F(x)
1(x)
0(x)
x0
x1
x2
x*
二、原始牛顿法的迭代公式 设目标函数f(x)具有连续的一、二阶导数，在xk点邻域内取f(x)的二次泰勒多项式作近似式，即
取逼近函数(x)为 设xk+1为(x)极小点，根据极值的必要条件，应有 (xk+1)=0，即 f(xk)+ H(xk)x=0 若f(x)在点xk处的海赛矩阵正定，则由上式解出的驻点就是(x)的极小点，所以它可以作为f的第k＋1次迭代的极小点，记为xk+1 得
xk+1 = xk- [H(xk)]-1 f(xk)
即牛顿法迭代公式，方向- [H(xk)]-1 f(xk)称为牛顿方向
我们知道，对于正定二次函数的无约束最优化问题
例：用牛顿法求解
这个例子说明，牛顿法要比最速下降法收敛的快，事实上
例：用牛顿法求解
三、原始牛顿法的特点 若用原始牛顿法求某二次目标函数的最优解，则构造的逼近函数与原目标函数是完全相同的二次式，其等值线完全重合，故从任一点出发，一定可以一次达到目标函数的极小点。 因此，牛顿法是具有二次收敛性的算法。其优点是：对于二次正定函数，迭代一次即可以得到最优解，对于非二次函数，若函数二次性较强或迭代点已经进入最优点的较小邻域，则收敛速度也很快。 原始牛顿法的缺点是：由于迭代点的位置是按照极值条件确定的，并未沿函数值下降方向搜索，因此，对于非二次函数，有时会使函数值上升，即 f(xk+1) > f(xk)，而使计算失败。
阻尼牛顿法
一、对原始牛顿法的改进
为解决原始牛顿法的不足，在由xk求xk+1时，不直接用迭代公式，而是沿牛顿方向进行最优一维搜索，以确定最优步长k ，这就是所谓的阻尼牛顿法。
因此，迭代公式变为： xk+1 = xk - k [H(xk)]-1 f(xk) 这就是阻尼牛顿法的迭代公式，最优步长k也称为阻尼因子，是沿牛顿方向一维搜索得到的最优步长。
二、阻尼牛顿法的迭代步骤 （1）给定初始点和收敛精度 （2）计算 f(xk) 、 H(xk)、 [H(xk)]-1 （3）求xk+1 = xk - k [H(xk)]-1 f(xk) （4）检查收敛精度，若|| xk+1- xk || < 则x*=xk+1，停止，否则 k=k+1，返回（2）继续
三、阻尼牛顿法的特点 优点：由于阻尼牛顿法每次迭代都在牛顿方向进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有苛刻的要求。 缺点： 1、对目标函数要求苛刻，要求函数具有连续的一、二阶导数；为保证函数的稳定下降，海赛矩阵必须正定；为求逆阵要求海赛矩阵非奇异。 2、计算复杂且计算量大，存储量大.
例:用阻尼牛顿法解
DFP变尺度法
变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由Davidon于1959年提出又经Fletcher和Powell加以发展和完善的一种变尺度法，故称为DFP变尺度法。
一、变尺度法的基本思想 变尺度法的基本思想与牛顿法和梯度法有密切联系。观察梯度法和牛顿法的迭代公式 x(k+1)=x(k)- k f(xk) 和 xk+1 = xk - k [H(xk)]-1 f(xk) 分析比较这两种方法可知：梯度法的搜索方向为- f(xk) ，只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢。牛顿法的搜索方向为- [H(xk)]-1 f(xk) ，不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，
计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。 思考：若迭代过程先用梯度法，后用牛顿法并避开牛顿法的海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的基本构想。 为此，综合梯度法和牛顿法的优点，提出变尺度法的基本思想。 变尺度法的基本迭代公式写为下面的形式： xk+1 = xk - k A(k) f(xk)
式中的A(k)为构造的n n阶对称矩阵，它是随迭代点的位置的变化而变化的。若A(k) =I，上式为梯度法的迭代公式，若A(k) = [H(xk)]-1 ，上式为阻尼牛顿法的迭代公式。
变尺度法的搜索方向- A(k) f(xk) ，称为拟牛顿方向。
二、尺度矩阵的概念 通过坐标变换可以改变函数的偏心程度，我们也称之为尺度变换。尺度变换能显著地改进几乎所有极小化方法的收敛性质。如用梯度法求f(x)=x12+25x22的极小值时， 需要迭代10次才能到达极小点x*=[0 0]T。若作变换 y1=x1 y2=5x2
则可以将函数的等值线由椭圆变为圆，即(y)=y12+y22，从而消除了函数的偏心，用梯度法只需一次迭代即能求得极小点。
对于一般二次函数 为减低函数二次项的偏心程度，进行尺度变换 xQx 则在新的坐标系中，函数的二次项变为 若矩阵G是正定的，则总存在矩阵Q使 QTGQ=I 将函数的偏心变为零。
用Q-1右乘等式两边，得 QTG=Q-1 再用Q左乘等式两边，得 QQTG=I 所以 QQT=G-1 这说明二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q求得。 QQT实际上是在空间内测量距离大小的一种度量，称为尺度矩阵，记作A，即 A= QQT 例如向量x的长度为 ||x||=(xTx)1/2 尺度变换后，向量x对于尺度下的长度为 ||x||A = [(Qx)T(Qx)]1/2=[xT(QQT)x]1/2=(xTAx)1/2
三、尺度变换矩阵的建立 根据变尺度法的基本原理，需要构造一个变尺度矩阵序列{Ak}来逼近海赛逆矩阵序列{Hk-1}，每迭代一次，尺度改变一次。 为了建立变尺度矩阵Ak ，必须对其附加某些条件。 1、为保证迭代公式的下降性质，要求{Ak}中的每一个矩阵都是对称正定的。因为若要求搜索方向Sk= - Ak f(xk) 为下降方向，即要求 f(xk) T Sk <0，也就是 - f(xk) T Ak f(xk) <0 ，故 f(xk) T Ak f(xk) >0 ，即Ak应为对称正定。 2、要求Ak之间的迭代具有简单的形式，显然Ak+1= Ak+Ek为最简单的形式，其中Ek为校正矩阵。 3、要求必须满足拟牛顿条件。
所谓拟牛顿条件，可以如下推导。 设迭代已经进行到k+1步，xk+1、 f(xk+1)均已经求得，当f(x)为具有正定矩阵G的二次函数时，根据泰勒展开得 f(xk+1) = f(xk) +H(xk)(xk+1-xK) 即 H-1 (xk)( f(xk+1) - f(xk))=xk+1-xk
令Ak+1满足类似上式的关系，也就是用Ak+1逼近H-1 (xk) 即 Ak+1( f(xk+1) - f(xk))=xk+1-xk 则Ak+1可以近似于H-1 (xk) ，因此把上式称为拟牛顿条件，为简便起见，记 ΔGk= f(xk+1) - f(xk) Δxk= xk+1-xk
则拟牛顿条件变为 Ak+1 ΔGk = Δxk
四、变尺度法的一般步骤 1、选定初始点和收敛精度 2、计算初始点处的梯度，选取初始对称正定矩阵A0，置k=0。 3、计算搜索方向Sk = - Ak f(xk) 4、沿Sk方向一维搜索，计算 f(xk+1) 、Δxk 、ΔGk 。 5、判断是否满足终止准则，若满足输出最优解，否则转6。 6、当迭代n次还未找到极小点，重置Ak为单位矩阵，并以当前点为初始点返回2，否则转7。 7、计算Ak+1= Ak+Ek ，置k=k+1返回3。
五、DFP变尺度法 在变尺度法中，校正矩阵Ek取不同形式，就形成不同的变尺度法， DFP算法中的校正矩阵Ek取下列形式： Ek=k Δxk T+ Ak ΔGk vkT 其中， k 、vk是待定向量。根据拟牛顿条件 Ak+1 ΔGk = Δxk 从而得到DFP算法中的校正公式
例：用DFP法计算
BFGS变尺度法
因为DFP算法是用Ak逼近H-1 ，但在计算时由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年提出更稳定的算法，称为BFGS算法，它是用Bk逼近H，相应的拟牛顿条件为
ΔGk = BkΔxk
其校正公式为
例：用BFGS法计算
坐标轮换法
坐标轮换法属于直接法，既可以用于无约束优化问题的求解，又可以经过适当处理用于约束优化问题求解。
坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。
一、坐标轮换法的迭代过程
任取一初始点x0作为第一轮的始点x01,先沿第一坐标轴的方向e1作一维搜索，用一维优化方法确定最优步长11，得第一轮的第一个迭代点x11=x01+ 11 e1，然后以x11为新起点，沿第二坐标轴的方向e2作一维搜索，确定步长21 ，得第一轮的第二个迭代点x21=x11+ 11 e2 第二轮迭代，需要
x1x21
x12 x21+ 12 e1
x22=x12+ 22 e2
依次类推，不断迭代，目标函数值不断下降，最后逼近该目标函数的最优点。
二、终止准则
可以采用点距准则或者其它准则。
注意：
若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。
三、坐标轮换法的流程图
给定：x0，
K=1
i=1
X0k=x0
沿ei方向一维搜索求
xik=xi-1k+ ikei
x=xk f=f(x)
i=n?
||xnk-x0k||?
x*=x
f*=f(x*)
i=i+1
x0=xnk
k=k+1
N
Y
N
Y
四、小结
坐标轮换法程序简单，易于掌握。但是计算效率比较低，尤其是当优化问题的维数较高时更为严重。一般把此种方法应用于维数小于10的低维优化问题。
对于目标函数存在
“脊线”的情况，在脊线的尖
点处没有一个坐标方向可以
使函数值下降，只有在锐角
所包含的范围搜索才可以达
到函数值下降的目的，故坐
标轮换法对此类函数会失效。
例：利用坐标轮换法计算
单纯形法
单纯形法
所谓单纯形就是n维欧氏空间R n中具有n+1个顶点的凸多面体。例如一维空间中的线段；二维空间中的三角形；三维空间中的四面体。
1、单纯形法基本思路：
设 x(0),x(1),…, x(n)是R n中n+1个点构成的一个当前的单纯形。
假设求函数的极小值。
去掉x max，加入x(n+1)得到新的单纯形。
重复上述过程。
设 x(0),x(1),…, x(n)是R n中n+1个点构成的一个当前的单纯形。
比较各点的函数值得到：x max,x min使
f( x max)=max{f(x(0)),f(x(1)), …,f(x(n))}
f( x min)=min{f(x(0)),f(x(1)), …,f(x(n))}
取单纯形中除去x max点外，其他各点的形心：
几点注意：
⑴当x(n+1)又是新单纯形的最大值点时，取次大值点进行反射；
⑵若某一个点x′出现在连续m个单纯形中的时候，取各点与x′连线的中点（n个）与x′点构成新的单纯形，继续进行。
经验上取 m≥ +
例如：n=2时，可取m≥ × 2+× 4 =
可取 m=4.
1
2
3
4
5
7
8
9
10
6
11
12
13
优点：不需求导数，不需要一维搜索。
缺点：无法加速，收敛慢，效果差。
2、改进单纯形法： （可变多面体算法）
设第k步迭代得到n+1个点： x(0),x(1),…, x(n) ，得到x max,x min及
通过下列4步操作选新迭代点：
1º 反射： 取反射系数α >0,(单纯形法中α =1)
2º 扩展：给定扩展系数γ >1,计算。（加速）
若f(y(1))<f(x min), 则将y(1)继续扩展到y(2)。
若f(y(1))> f(y(2)), 那么y(2)取代x max; 否则， y(1)取代x max 。若max{f(x(i))| x(i) ≠x max } ≥ f(y(1)) ≥ f(x min), y(1)取代x max 。
3° 收缩：若f(x max )> f(y(1)) > f(x(i)), x(i) ≠x max ,计算
以y(3)取代x max 。
4 ° 减半：若f(y(1)) > f(x max ), 重新取各点，使
x(i)= x min +1∕ 2(x(i) - x min ) 得到新单纯形。
经验上：α=1,≤β≤, ≤γ≤ .
有人建议:α=1, β=， γ=2 。
算法停机准则取：
例：利用单纯形法求解。
模式搜索法
模式搜索法是胡克 和基夫斯（Hooke & Jeeves ）1961年提出的。
基本思想与主要过程：
△利用两类移动（探测性移动和模式性移动）进行一步迭代：
探测性移动的目的：探求一个沿各坐标方向的新点并得到
一 个“有前途”的方向（下降的有利方向）；
模式性移动的目的：沿上述“有前途”方向加速移动。
考虑无约束最优问题 min f(X) X Rn
△主要过程：第k步迭代，设已得到x(k)
1°探测性移动：
给定步长k ，设通过模式性移动得到y(0),
依次沿各坐标方向e(i)=(0, …,1,0, …,0)T
i
移动k步长：i=0,1, …,n-1 , Ŷ =y(i)+ke(i+1)
若f(Ŷ)<f(y(i)), 则 y(i+1) = Ŷ；
否则取 Ŷ =y(i) -ke(i+1)
若f(Ŷ)<f(y(i)), 则 y(i+1) = Ŷ；
否则 y(i+1) = y(i)
最后得到y(n) 。
若f(y(n) )<f(x(k)), 令x(k+1)=y(n).
将每一次探测性移动后得到的点，作为下一次探测性移动的开始点，经过n次探测性移动，一般地可以得到使f下降的点，这就完成了一次探测性移动。每次探测性移动的开始点称为参考点。
设x(k+1)是以点x(k)为参考点进行一次探测性移动所得到的点。
若f(x(k+1)) )<f(x(k)), 则从点x(k+1)出发作模式性移动。
2°模式性移动：
x(k+1) - x(k)为一个有前途的方向，取
y(0)= x(k+1) +(x(k+1) - x(k))=2 x(k+1) - x(k)
3 °几点措施：
①若探测性移动得到y(n)使f(y(n) )≥f(x(k)), 则跳过模式性移动而令y(0)=x(k) 重新进行探测性移动，初始y(0)=x(1) ；
②若y(n)= y(0) （即每一个坐标方向的移动都失败），减小k ，重复上述过程。
③当进行到k充分小（ k <ε ）时，终止计算。最新的 迭代点x(k)为解。
2、算法：
初始x, α ,y(0)=x, ε>0
计算f=f(x)
f1=f(y(0)),i=1
y(i)=y(i-1)+ αe(i)
计算f2=f(y(i))
f2<f1?
f1=f2
i<n?
yes
yes
1
No
i=i+1
2
No
y(i)=y(i-1)+ (-α)e(i)
计算f2=f(y(i))
f2<f1?
y(i)=y(i-1)
yes
No
2、算法： (续)
1
f1<f ?
No
yes
X=y(n), y(0)=2X -x
x=X ,f=f(x)
y(n)=x?
No
y(0)=x
Yes
α<ε ?
Yes
No
α= α
2
停；x为解
例：用模式搜索法求解
鲍威尔方法
鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，它是以正定二次型为背景的共轭方向为基础的一种方法，因此该方法本质上是一种共轭方向法。是鲍威尔1964年提出的。
一、原始鲍威尔基本算法 如图所示，是二维二次目标函数的无约束优化问题。
如图所示，是三维二次目标函数的无约束优化问题。
原始鲍威尔基本算法的步骤： 第一环基本方向组取单位坐标矢量系e1、 e2、 e3 、…、 en，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向，再沿新生方向作一维搜索，完成第一环的迭代。以后每环的基本方向组是将上环的第一个方向淘汰，上环的新生方向补入本环后而构成。n维目标函数完成n环的迭代过程称为一轮。从这一轮的终点出发沿新生方向搜索所得到的极小点，作为下一轮迭代的始点。这样就形成了算法的循环。
原始鲍威尔基本算法的缺陷： 可能在某一环迭代中出现基本方向组为线性相关的矢量系的情况。如第k环中，产生新的方向： pk=xnk-x0k= 1kp1k+ 2kp2k + • • • + nkpnk 式中， p1k、p2k 、 • • • 、pnk为第k环基本方向组矢量,1k 、 2k 、• • • 、nk为第k个基本方向的最优步长。 若在第k环的优化搜索过程中出现1k =0，则方向pk表示为p2k 、 p3k 、• • • 、pnk的线性组合，以后的各次搜索将在降维的空间中进行，无法得到n维空间的函数极小值，计算将失败。 如图所示为一个三维优化问题的示例，设第一环中1 =0 ，则新生方向与e2 、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。
原始鲍威尔基本算法的退化
x1
x2
x3
1=0
1e2
3e3
S1
例：用原始powell法求解。
二、鲍威尔修正算法 在某环已经取得的n+1个方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组。 鲍威尔修正算法的搜索方向的构造： 在第k环的搜索中， x0k 为初始点，搜索方向为p1k、p2k 、 • • • 、 pnk，产生的新方向为pk ，此方向的极小点为xk。点 xn+1k=2xnk-x0k 为x0k对xnk的映射点。 计算x0k 、 x1k 、 • • • 、 xnk 、 xk、 x n+1k 各点的函数值，记作： F1=F(x0k) F2=F(xnk) F3=F(xn+1k) = F(xmk) -F(xm-1k) 是第k环方向组中，依次沿各方向搜索函数值下降最大值，即pmk方向函数下降最大。
为了构造第k+1环基本方向组，采用如下判别式：
按照以下两种情况处理： 1、上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组p1k、p2k 、 • • • 、pnk。 k+1的环初始点取 x0k+1=xnk F2<F3
x0k+1=xn+1k F2F3 2、两式均不成立，则淘汰函数值下降最大的方向，并用第k环的新生方向补入k+1环基本方向组的最后，即k+1环的方向组为p1k、p2k 、 • • • 、pm-1k、pm+1k • • • 、 pnk 、 pn+1k 。k+1环的初始点取 x0k+1=xk xk是第k环沿pn+1k方向搜索的极小点。
鲍威尔算法的终止条件： || xk-x0k ||
迭代步骤
及流程图
例：用修正powell法求解
无约束优化问题的评价准则
本章介绍了多种无约束优化方法，在实际应用中如何选择这些优化方法就显得尤为重要。为了比较各种优化方法的特性，必须建立合理 的评价准则。 无约束优化方法的评价准则主要包括以下几个方面： 1、可靠性。即在合理的精度要求下，在一定允许时间内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好。 2、有效性。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数。 3、简便性。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。
下面讨论本章所介绍的几种优化方法的适用范围： 可靠性：牛顿法较差，因为它对目标函数要求太高，解题成功率较低。 有效性：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性。 简便性：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。 由以上讨论可知，在选用无约束优化方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。 1、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。 2、对于二次性较强的目标函数，使用牛顿法效果好。 3、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。 4、综合而言，鲍威尔法和DFP法具有较好的性能。
