第五章 多变量无约束优化方法5-1 概 述¡无约束最优化问题是：求n维设计变量X=[x1,x2,…,xn]T使目标函数 为minf(X)，而对X没有任何限制；如果存在X*,使minf(X)= f(X*)分 别称X*为最优点，f(X*)为最优值¡无约束最优化方法归纳起来可分为两大类¡一类是只需要进行函数值的计算与比较来确定迭代方向和步长的 直接搜索法，简称直接法；¡另一类则是要利用函数的一阶或二阶偏导数矩阵来确定迭代方向 和步长的间接法直接搜索法与间接法相比，收敛速度较慢，但 它不要求函数具有好的解析性质,适用范围较广¡属直接法的有变量（坐标）轮换法、单纯形法、共轭方向 法和鲍威尔(Powell)法等 ¡属间接法的梯度法、共轭梯度法、牛顿法和变尺度法等 ¡无约束优化方法虽然种类很多，但一般由以下四个部分组成¡(1)选择一个初始点X(0),这一点越靠近局部极小点X*越好¡(2)如已取得某设计点X(k)( k＝0，1，2，…)，并且该点还不是近 似极小点，则在X(k)点根据函数f(X)的性质，选择一个方向S(k)，沿 此方向搜索函数值应是下降的，称S(k)为下降方向¡(3)当搜索方向S(k)确定以后，由X(k)点出发，沿S(k)方向进行搜索， 定出步长因子α(k)，得新设计点X(k+1)= X(k)+α(k) S(k) 并满足f(X(k+1))＜f(X(k))。
具有这种性质的算法称为下降算法α(k) 可以是一维搜索方法确定的最优步长因子，亦可用其他方法确定 ¡(4)若新点X(k+1)满足迭代计算终止条件，则停止迭代，X(k+1)点就作 为近似局部极小点X*；否则，又从X(k+1)点出发，返回第(2)步继 续进行搜索迭代如何产生这些搜索方向——成为各种无约束优化方法的主要特征 5-2变量轮换法¡一、变量轮换法的原理与计算方法¡ 变量轮换法又称坐标轮换法，它是把一 个n维无约束最优化问题转化为依次沿 相应的n个坐标轴方向的一维最优化问 题，并反复进行若干轮循环选代来求解 的直接搜索方法 设二元目标函数f(X)= f(x1, x2)其等值线示于图中 对该二维问题，经过沿 e1、e2两次一维搜索称为完 成了一轮迭代 第二轮迭代则是以第一 轮迭代的末点X2(1)作为第二 轮迭代的起始点 X1(2)= X0(2)+α1(2) e1 X2(2)= X1(2)+α2(2) e2 最后的迭代点必将逼近 该二维目标函数的最优点 X1(1)= X0(1)+α1(1) e1X2(1)= X1(1)+α2(1) e2任选一个初始点X(0)作为 第一轮的始点X0(1)二、迭代过程及算法框图 ¡根据上述原理，对于第k轮计算，变量轮换法迭 代公式为¡ Xi(k)= Xi-1(k) +αi(k) Si(k) (i=1,2,…,n) ¡式中 Si(k) ----搜索方向；¡ αi(k) ----步长因子。
¡Si(k) 轮流取n维空间各坐标轴的单位向量ei (i=1,2,…,n)，即1、加速步长法 加速步长法是以成倍数增加的试验步长来寻找新点的 方法 2、最优步长法 每次沿一个坐标轴方向搜索时，利用一维搜索法确 定最优步长αi(k) ，即在第k轮的第i次迭代中，其最优步 长αi(k)使min f(Xi-1(k)+ α(k) Si(k)) = f(Xi-1(k)+ αi(k) Si(k))αi(k)取正值或负值均可,但必须使f(Xi(k))＜f(Xi-1(k))，步长因 子的选取：搜索步长或步长因子通常有如下两种取法：变量轮换法的具体迭代步骤如下：(1)给定初始点X(0)∈Rn，迭代精度ε，维数n，Si(1)= ei (i=1,2,…,n) 2)置1→k3)置1→i4)置X(0)→Xi-1(k)5)从Xi-1(k)点出发，沿Si(k)方向进行关于α(k)的一维搜索，求出最优 步长α(k)，使f(Xi-1(k)+ αi(k) Si(k))= min f(Xi-1(k)+ α(k)Si(k)) 置Xi-1(k)+ αi(k)Si(k)) →Xi(k)6)判别是否满足i＝n?若满足则进行步骤(7)；否则置i+1→i返回 步骤(5)。
7)检验是否满足迭代终止条件‖Xn(k)- X0(k)‖≤ε?若满足，迭代停止， 得到Xn(k)为最优点，输出Xn(k)→X*，f(Xn(k))→f(X*)；否则置Si(k) →Si(k+1) (i=1,2,…,n)，Xn(k)→X(0)，k+1→k，返回步骤(3)变量轮换法的算法框图如图5-2所示1、用变量轮换法寻优就像是沿两个垂直的个固定方 向前进，虽然目标函数值是步步降低，但所走的“路”太 曲折，所以该方法收敛速度较慢2、变量轮换法的效能与目标函数的维数有关，当维 数增加时效率下降，一般适用于n＜10的低维优化问题3、这种方法的效能在很大程度上还取决于目标函数 的性质5-3原始共轭方向法¡一、共轭方向的基本概念¡关于搜索方向S(k)的选择问题，是最优 化方法中所讨论的重要问题之一¡以二维正定二次函数为例，采用变量 轮换法，其搜索方向是沿两个垂直的 固定方向前进，达到极小点要多次变 换方向搜索，道路曲折，收敛速度较 慢¡希望选择的搜索方向尽可能指向目标 函数f(X)的极小点如图5-5所示二维 正定二次函数、其等值线是一族同心 椭圆，在X(k)点构造的搜索方向最好是 通过极小点X*。
显然，最理想的方向 是S2(k)方向¡这就是将要介绍的有关“共轭方向”二)共轭方向在最优化问题中的应用 二维正定二次函数具有两个重要 特点 1)二维正定二次函数的等值线是 同心的椭圆族，且椭圆中心就是 以正定二元二次函数为目标函数 的极小点X*(图5-6) (一)共轭方向的定义设A为n×n阶实对称正定矩阵，如果有两个n维向量S1和S2满足S1TAS2=0 则称向量S1与S2对于矩阵A共轭 共轭向量的方向称为共轭方向2)过同心椭圆族中心X*作任意直线此直线与诸椭圆交 点处的切线相互平行(图 (a)) 也可以说，如果对同心椭圆族有两条平行的(如图 (b)中 平行于给定向量X1的方向)任意方向切线l1，l2,其切点 X(1)，X(2)的连线方向S2必通过椭圆族的共同中心X* 1.可以推出对于n维正定二次函数，共轭方向的一个十分重要 的极为有用的性质：从任意初始点X(0)出发，依次沿n个线性无关 的与A共扼的方向S1，S2，…, Sn各进行一维搜索，那么总能在第n 步或n步之前就能达到n维正定二次函数的极小点；并且这个性质 与所有的n个方向的次序无关因而说共轭方向法具有有限步收敛 的特性通常称具有这种性质的算法为二次收敛算法。
2.理论与实践证明，将二次收敛算法用于非二次的目标函数 ，亦有很好的效果，但迭代次数不一定保证有限次，即对非二次n 维目标函数经n步共轭方向一维搜索不一定就能达到极小点3.对于非二次的目标函数寻优的另一种处理方法是循环迭代 法，即当达n步迭代终点X(n)时还未收敛，此时可将X(n)作为新的初 始点，再重新开始迭代，实践证明，这样做要比一直迭代下去具 有更好的效果4.即便对于正定二次函数，在数值计算中，由于数据的舍入 以及计算误差的累积，往往破坏了这种共轭性质二、共轭方向的原始构成¡三维二次目标 函数f(X)的无约 束优化问题为 例，来说明共 扼方向的原始 构成见图5-8 对于n维二次目标函数原始共轭方向的构成方法可类同上 述步骤进行现概括为：有一组线性无关的初始基本方向 组Si(k) (i＝1，2，…，n)，依次沿Si(k)进行一维最优化搜索 ，并且以初始点和搜索终点连线作为新的方向，记作 Sn+1(k)，再沿Sn+1(k)一维搜索，得完成一环搜索的末点Xn+1(k) 以后每环的初始点总是取上一环的搜索末点，即 Xn+1(k)→ X0(k+1)，基本方向组Xn+1(k)为将上环的基本方向组 去掉第一个方向S1(k)，并以上环的新生方向Sn+1(k)补入本环 最后而构成，即Sn+1(k) → Sn (k+1)，再产生该环的新生方向 Sn+1(k+1)＝Xn(k+1)− X0(k+1)。
对n 维目标函数这样的迭代进行n 环称为完成一轮迭代Sn+1(1)， Sn+1(2)，…，Sn+1(n)，这些新 方向之间应该构成n个共轭方向对于正定二次函来说， 经n个共轭方向完成—轮迭代的终点Xn+1 (n)应为理论极小点 三、迭代过程及算法框图迭代步骤: (1)给定初始点X(0)，迭代精度ε，维数n，迭n线性无关 的向量Si(1)＝ei (i＝1,2,…,n)作为初始搜索方向2)置1→k (3)置 1→i4)置X(0) →X i−1(k)5)从X i−1(k)点出发，沿Si(k)方向进行关于 α(k)的一维搜索，求出最优步长αi(k)，置 X i−1(k)+ αi(k)Si(k) → X i(k) 6)判别是否满足i＝n?若满足则进行步骤(7);否则置i+1→i返回 步骤(5)7)计算共轭方向 Xn(k)− X0(k) →Sn+1(k) 8)从X0(k)点出发 ，沿新方向Sn+1(k)进行关于α(k)的一维搜索，求出最优步长αn+1(k)， 置 Xn(k)+ αn+1(k)Sn+1(k) →Xn+1(k)，获得了一个新方向Sn+1(k)及其Sn+1(k) 方向上的极小点Xn+1(k)。
9)判别是否满足k＝n?若不满足则进行步 骤(10),否则转向步骤(11)10)构成下一循环搜索的搜索方向去 掉前一循环搜索方向组中的第一个方向S1(k),将新搜索方向Sn+1(k)排 在Sn(k)之后，构成下一循环搜索的搜索方向，即Si+1(k) →Si(k+1) (i＝ 1,2,…,n)，Xn+1(k) → X(0)，k+1 → k，返回步骤(3)11)检验是否满 足迭代终止条件║ Xn+1(k)− X0(k)║≤ ε?若满足，迭代停止，得到 Xn+1(k)为最优点，输出Xn+1(k) →X*，f( Xn+1(k) )→f(X*)；否则，置 Xn+1(k) → X(0)，返回第(2)步开始新的一轮迭代运算)原始共轭方向法 的算法框图如图5 -9所示图5-10显示了二维 正定二次函数用原 始共轭方向法求极 小点的搜索路线， 清楚地看出使用两 个共轭方向S3(1)和 S3(2)后就能达到极 小点从几何意义 上将其推广到n维 正定二次函数，使 用n个共轭方向后 理论上亦能达到极 小点 说明：1、n维问题共轭方向法的要点是：在每一循环迭代中都有一个 初始点X0(k)和n个线性无关的搜索方向Si(k)，i=l，2，…n。
从预先给 定的初始点X0(k)出发，用坐标轮换法依次沿n个方向进行一维搜索 得终点Xn(k)， 由始点X0(k)和终点Xn(k)连线得一新的方向Sn+1(k)，用这 方向替换原n个方向中的一个，形成下一循环的搜索方向组Si(k+1)（ i=l，2，…n）替换的原则是：去掉原方向组中的第一个方向S1(k) ，而将新方向Sn+1(k)排在最后，形成下一循环搜索的搜索方向组 Si(k+1)＝ Si+1 (k)（i=l，2，…n）：并规定从该K循环的搜索终点Xn(k) 出发，沿新方向Si(k+1)进行一维搜索得到的极小点Xn+1(k)，作为下一 循环迭代的始点，即X0(k+1)＝ Xn+1(k)这样进行n循环迭代后， 原方 向组中的n个方向便完全由新产生的一组共轭方向所代替当目标 函数是n维正定二次函数时，从理论上讲，经过这样n个循环迭代 后，就可以收敛到最优点2、该算法可能出现的问题 上述算法仅具有理论意义，因为在迭代中的n个搜索方向，有可 能出现线性相关或接近线性相关，导致搜索过程在降维的空间进 行，无法获得函数的极小点，使计算失败5-4鲍威尔法 ¡一、基本愿理¡鲍威尔(M.J.D.Powell) 提出了对原始共轭。