第二章无约束最优化 §1一维搜索 对于无约束问题 mIn (x ∈R 的求解思路,根据上一章最优性条件的分析可有两条: 1°、若f(x)可微,则可考虑求稳定点 Vf(x=0 (2)是一非线性方程组,可以动用求解非线性方程组的手段处理,不过这也是相当复杂的问题,何 况若∫(x)不可微,此路便行不通,故通常都采用使目标函数逐次下降的搜索方法 °、搜索方法是从某一初始点x°出发,先选择一个下降方向s°,然后于方向s上找一点 x=x+As"(4>0),使f(x)<f(x°),如此进行下去会得到点列{x},满足 f(x)>f(x3)>…>f(x3)>…。设x*→>x,若于x处已无下降方向,则x即为局部最小点 关于收敛速度有如下定义: 定义1:对于收敛于最优解x的序列{x},若存在与k无关的数B>0,和a≥1,当k从某个 k开始后,有 k+1-x (3) 则称序列{x}是α阶收敛的。当a=1,B<1时,称为线性收敛,a>1时称为超线性收敛,超线 性收敛的另一种形式是,1"-x|sAB2-x且m=0.a=2时称为二阶收敛,还有所 谓二次收敛,它是指当一个算法用于具有对称正定矩阵的二次函数时,在有限步内可以获得它的极 小点。一般说来,具有二次收敛的算法,往往具有超线性收敛性,因而属于比较好的算法之列。 对于预先给定的精度要求E>0,作为计算结束的检验条件可采取以下几种办法之 k+1-x4<E i、(x)-f(x)<E 7(x)<E iy、|/(x)b,其中b是一个可接受的目标值 一般的,从x2出发,沿着下降方向s4(称为搜索方向)找一x,使得f(x#)<f(x),则x可 173
173 第二章 无约束最优化 §1 一维搜索 对于无约束问题 ( ) n min f x x R (1) 的求解思路，根据上一章最优性条件的分析可有两条： 1°、若 f x( ) 可微，则可考虑求稳定点 f (x) = 0 (2) （2）是一非线性方程组，可以动用求解非线性方程组的手段处理，不过这也是相当复杂的问题，何 况若 f x( ) 不可微，此路便行不通，故通常都采用使目标函数逐次下降的搜索方法。 2°、搜索方法是从某一初始点 0 x 出发，先选择一个下降方向 0 s ，然后于方向 0 s 上找一点 1 0 0 x x s = + ( 0) ， 使 1 0 f x f x ( ) ( ) ， 如 此 进 行 下 去 会 得 到 点 列 { }k x ， 满 足 0 1 ( ) ( ) ( ) k f x f x f x 。设 k x x → ，若于 x 处已无下降方向，则 x 即为局部最小点。 关于收敛速度有如下定义： 定义 1：对于收敛于最优解 x 的序列 { }k x ，若存在与 k 无关的数 0 ，和 1 ，当 k 从某个 0 k 开始后，有 k k 1 x x x x + − − （3） 则称序列 { }k x 是 阶收敛的。当 =1， 1 时，称为线性收敛， 1 时称为超线性收敛，超线 性收敛的另一种形式是， k k 1 k x x x x + − − 且 lim 0 k k → = 。 = 2 时称为二阶收敛，还有所 谓二次收敛，它是指当一个算法用于具有对称正定矩阵的二次函数时，在有限步内可以获得它的极 小点。一般说来，具有二次收敛的算法，往往具有超线性收敛性，因而属于比较好的算法之列。 对于预先给定的精度要求 0 ，作为计算结束的检验条件可采取以下几种办法之一： i、 k k 1 x x + − ii、 1 ( ) ( ) k k f x f x + − iii、 1 ( ) k f x + ⅳ、 1 ( k + f x ) b ，其中 b 是一个可接受的目标值 一般的，从 k x 出发，沿着下降方向 k s （称为搜索方向）找一 k 1 x + ，使得 1 ( ) ( ) k k f x f x + ，则 k 1 x + 可
表示成 x"+ 4) 其中入>0称为步长,若它的选取满足 f(x)=f(x+ds")=min f(x+s)<f() (5) 则称搜索是精确的一维搜索,入为最优步长;否则称为不精确的。一维搜索是最优化方法的基础, 它有一个重要的性质 定理1、设f(x)具有连续偏导数,而x是从x出发沿着s方向做精确的一维搜索得到的, 则 Vf(s=0 (6) 证:设(1)=f(x2+As),则o(y=Vf(x+As)s2,因入为最优步长,即q(入)=mino(), 故必有以(43y=0,又因x=x2+入s4,故(6)成立。 一维搜索就是求一元函数()的极小值,但用求稳定点(4)=Vf(x+As4)s=0的方法 往往很困难,下面介绍一些常用方法。 1°、使用导数的方法。如 Newton法、抛物线法、三次样条插值法、对分法等 欲求(x)=0,x∈R的根。 ①考虑用(x)在某初始点x°的二阶 Taylor展开式近似代替(x): q(x)≈g(x)=(x)+g(x.)(x-x)+g(x0)(x-x°)2 由q'(x)≈g'(x)=0,得 X q"(x°) 由此可得迭代公式: x4-y( k=0,1, 这种求一元函数最小值的方法叫 Newton法。一般的,欲求(x)=0,则有x1=x-(x),号 f(x) 称切线法。它是二阶收敛的,缺点是对初值x要求较高,其附近二阶导数须不变号。 关于算法的收敛性有如下结果:
174 表示成： k k k 1 k x x s + = + （4） 其中 k 0 称为步长，若它的选取满足 1 ( ) ( ) min ( ) ( ) k k k k k k k f x f x s f x s f x + = + = + （5） 则称搜索是精确的一维搜索， k 为最优步长；否则称为不精确的。一维搜索是最优化方法的基础， 它有一个重要的性质： 定理 1、设 f x( ) 具有连续偏导数，而 k 1 x + 是从 k x 出发沿着 k s 方向做精确的一维搜索得到的， 则： 1 ( ) 0 k T k f x s + = （6） 证：设 ( ) ( ) k k = + f x s ，则 ( ) ( ) k k T k = + f x s s ，因 k 为最优步长，即 ( ) min ( ) k = ， 故必有 ( ) 0 k = ，又因 k k k 1 k x x s + = + ，故（6）成立。 一维搜索就是求一元函数 ( ) 的极小值，但用求稳定点 ( ) ( ) 0 k k T k = + = f x s s 的方法 往往很困难，下面介绍一些常用方法。 1°、使用导数的方法。如 Newton 法、抛物线法、三次样条插值法、对分法等。 欲求 ( ) 0 x = ， 1 x R 的根。 ①考虑用 ( ) x 在某初始点 0 x 的二阶 Taylor 展开式近似代替 ( ) x ： 0 0 0 0 0 2 1 ( ) ( ) ( ) ( )( ) ( )( ) 2 x g x x x x x x x x = + − + − 由 (x) g (x) = 0, 得 0 0 0 ( ) ( ) x x x x = − 由此可得迭代公式： 1 ( ) ( ) k k k k x x x x + = − ， k = 0,1, （7） 这种求一元函数最小值的方法叫 Newton 法。一般的，欲求 f x( ) 0 = ，则有 1 ( ) ( ) k k k k f x x x f x + = − ，号 称切线法。它是二阶收敛的，缺点是对初值 0 x 要求较高，其附近二阶导数须不变号。 关于算法的收敛性有如下结果：
定理2:设q:R1→R二次连续可微。考虑由映射4(4)=2-9()定义的 Newton算法,设 q"() λ使得o(4)=0和"()≠0,设开始点A充分接近,因而存在k2k2>0,kk2<1,使得对 满足2一2<12-7的每一个 o(a) (4)-(4)-g(4(2 ≤k, 则算法收敛于A。 (2)之分子相当于o()与其在点的 Taylor一阶展开之差,因此只有,充分接近,才能保证k 足够小,使kk2<1。 ②用二次函数g(x)来近似替代φ(x):选择三点x1<x”<x2,满足两头大,中间小 (x2)>o(x),p(x3)<9(x2),过(x,(x),(x,o(x),(x2,(x2)做二次函数g(x),令 g(x)=0,解得极小点x3,去掉x或x2,对余下的三点(仍须满足两头大,中间小)重复以上步 骤,直到满足精度为止,这种方法称为抛物线法,其收敛阶为1.618 ③用q(x)在两点a及b的函数值g(a),φ(b)及导数值p'(a),(b)(q(a)与φ(b)异号) 做三次函数g(x),使g(a)=p(a),g(b)=q(b),g'(a)=p(a),g'(b)=q(b),试图用g(x)的 极小值点近似o(x)的极小值点。若(x)<E,终止:否则,用x替换a或b中导数与之同号者, 继续迭代。这种方法称为三次样条插值法。一般来说比抛物线法敛速快。 ④对分法:要求φ'(x)连续,φ(a)'(b)<0,计算φ'(一),去掉φ(a),q(b)中与之同号 若(x)为伪凸函数即可采用上述方法。因为伪凸:1,若(4)=0,由伪凸性入是极小点。2, 若φ()>0,当A>→0(4)≥(),→去掉(λb]。3,若φ(λ)<0,当 <入→0(4)20(1),→[ak,A)。此外,次数n必须满足G)”≤,,l为最后区间的长度 2°、不用导数的方法,如“成功—一失败”法、分数法、0.618法等。 ①“成功一一失败”法:假定已确定初始点x°和初始步长λ>0,若o(x°+1)<q(x”),则称
175 定理 2：设 1 1 : R → R 二次连续可微。考虑由映射 ( ) ( ) ( ) A = − 定义的 Newton 算法，设 使得 ( ) 0 = 和 ( ) 0 ，设开始点 1 充分接近 ，因而存在 1 2 k k, 0 ，k k1 2 1 ，使得对 满足 − −1 的每一个 ，有： （1） 1 1 ( ) k ， （2） 2 ( ) ( ) ( )( ) k − − − − 则算法收敛于 。 (2)之分子相当于 ( ) 与其在 点的 Taylor 一阶展开之差，因此只有 1 充分接近 ，才能保证 2 k 足够小，使 k k1 2 1。 ②用二次函数 g x( ) 来近似替代 ( ) x ：选择三点 1 0 2 x x x ，满足两头大，中间小： 1 0 ( ) ( ) x x ， 0 2 ( ) ( ) x x ，过 1 1 ( , ( )) x x ， 0 0 ( , ( )) x x ， 2 2 ( , ( )) x x 做二次函数 g x( ) ，令 g x ( ) 0 = ，解得极小点 3 x ，去掉 1 x 或 2 x ，对余下的三点（仍须满足两头大，中间小）重复以上步 骤，直到满足精度为止，这种方法称为抛物线法，其收敛阶为 1.618。 ③用 ( ) x 在两点 a 及 b 的函数值 ( ) a ，( ) b 及导数值 ( ) a ，( ) b （ ( ) a 与 ( ) b 异号） 做三次函数 g x( ) ，使 g a a ( ) ( ) = ，g b b ( ) ( ) = ，g a a ( ) ( ) = ，g b b ( ) ( ) = ，试图用 g x( ) 的 极小值点 x 近似 ( ) x 的极小值点。若 ( ) x ，终止；否则，用 x 替换 a 或 b 中导数与之同号者， 继续迭代。这种方法称为三次样条插值法。一般来说比抛物线法敛速快。 ④对分法：要求 ( ) x 连续， ( ) ( ) 0 a b ，计算 ( ) 2 a b + ，去掉 ( ) a ，( ) b 中与之同号 者。 若 ( ) x 为伪凸函数即可采用上述方法。因为伪凸：1，若 ( ) 0 k = ，由伪凸性 k 是极小点。2， 若 ( ) 0 k ， 当 ( ) ( ) k k ， , ( 去掉 k bk] 。 3 ， 若 ( ) 0 k ， 当 ( ) ( ) k k ， [ , ) ak k 。此外,次数 n 必须满足 l b a l n ) , 2 1 ( − 为最后区间的长度. 2°、不用导数的方法，如“成功——失败”法、分数法、0.618 法等。 ①“成功——失败”法：假定已确定初始点 0 x 和初始步长 0 ，若 0 0 ( ) ( ) x x + ，则称
搜索成功,下一步令x2=x0+元,比较(x+月1)和o(x)(一般取B=2),继续向前搜索,若 o(x+1)≥0(x),则称搜索失败,下一步反向搜索,比较9(x2-B24)和o(x2),(一般取 月2=4),这样不断达代,每次步长都要改变,直到<E为止。此法简单易行,且对(2)无任 何要求,因此最实用 ②分数法及0.618法。这些方法适用于单峰函数。分数法(亦称 Fibonacci法)是用 Fibonacci Fo=F Fn=Fn-1+Fn2(n=2,3…) 计算头两个试验点 A=a+F-2(b-a) u=a+F-1(b-a) Fr A A, b λ,μ关于区间中点对称,比较∫(4),f(A),去掉值较大的一段,然后取余下区间内保留之试 验点的对称点为新试验点,如此继续下去,当进行(n-1)次试验后,余下的已试验点是区间的中 点,最后一次试验安排在这点附近,从而得到最终剩余区间。这里n是计算函数值的次数,它是事 先确定的,从而F亦事先确定,所选试验点均在F等分[a小的分点上。可证,经n次试验后,区 间缩短为 6(剩余空间之比依次为型,F2 (b-a) ,互,它们的积便是1),可由 F (b-a) sE,确定试验次数n。 分数法是n次试验后所余空间最短者,故亦称优选法 如果考虑使每次试验区间缩短率都相等(等于a),则试验点显然应关于中点对称: 于是有 a_1-a,解之得a=2 √5-1 ≈0.618。这就是0.618法,亦称黄金分割法。可证 a=limn,即a为分数法的极限 0.618法比较简单,并且不必预先确定试验次数,也避免使用 Fibonacci数,易于普及,但它收 敛速度要比分数法慢些,并且由于累计误差的影响,试验次数以最多安排11次为宜 176
176 搜索成功，下一步令 1 0 x x = + ，比较 1 1 ( ) x + 和 1 ( ) x （一般取 1 = 2 ），继续向前搜索，若 0 0 ( ) ( ) x x + ，则称搜索失败，下一步反向搜索，比较 1 2 ( ) x − 和 1 ( ) x ，（一般取 2 1 4 = ），这样不断迭代，每次步长都要改变，直到 为止。此法简单易行，且对 ( ) 无任 何要求，因此最实用。 ②分数法及 0.618 法。这些方法适用于单峰函数。分数法（亦称 Fibonacci 法）是用 Fibonacci 数： F F 0 1 = =1 1 2 ( 2,3, ) F F F n n n n = + = − − 计算头两个试验点: 2 1 ( ) n n F a b a F − = + − 1 1 ( ) n n F a b a F − = + − a 1 1 b 1，1 关于区间中点对称，比较 1 f ( ) ， 1 f ( ) ，去掉值较大的一段，然后取余下区间内保留之试 验点的对称点为新试验点，如此继续下去，当进行（n－1）次试验后，余下的已试验点是区间的中 点，最后一次试验安排在这点附近，从而得到最终剩余区间。这里 n 是计算函数值的次数，它是事 先确定的，从而 Fn 亦事先确定，所选试验点均在 Fn 等分 a b, 的分点上。可证，经 n 次试验后，区 间缩短为 ( ) n b a F − ，（剩余空间之比依次为 n 1 n F F − ， 2 1 n n F F − − ， ， 1 2 F F ，它们的积便是 1 Fn ），可由 ( ) n b a F − ，确定试验次数 n。 分数法是 n 次试验后所余空间最短者，故亦称优选法。 如果考虑使每次试验区间缩短率都相等（等于 ），则试验点显然应关于中点对称： 0 1− 1 于是有 1 1 − = ，解之得 5 1 0.618 2 − = 。这就是 0.618 法，亦称黄金分割法。可证 1 lim n n n F F − → = ，即 为分数法的极限。 0.618 法比较简单，并且不必预先确定试验次数，也避免使用 Fibonacci 数，易于普及，但它收 敛速度要比分数法慢些，并且由于累计误差的影响，试验次数以最多安排 11 次为宜
如果函数g(x)是严格拟凸的(与单峰函数大体相当),则通过计算在这个区间内两点的值,不 定区间能够被缩小。对此有以下定理 定理3:设q:R→R在区间[小上严格拟凸,设λ,∈[ab],A<H,若o(1)>o(), 则对vx∈[a,4],q(x)≥0();如果(2)≤q(4),则对vx∈[,b],q(x)≥9()(不然,对前 者则应有(x)<Q(),由=ax+(1-a)→9()<max{q(x),p()}=(4),矛盾)。 精确一维搜索计算量大,并且有时意义不是很大,反不如计算量小的不精确搜索效果好,后者 只要求f(x4+)比f(x)下降一定数量,以及Vf(x)s的绝对值比vf(x3)s的小一定数量。 现在通常采用 Goldstein(1965)和 Powell(1975)提出的两个条件来设计不精确一维搜索方法, 即对给定常数q12C2,0<<C2<1,要求 1°、f(x2)-f(x2)≥-cVf(x2)s4>0 2°、Vf(x)s≥c2vf(x)s 常取c1=0.1,c2=0.5。 设区间[ab]=(O,+),先取元=1,若满足要求1°、2°,令A=1;若不满足1° 令b==1,另取石=入+,重新计算:若不满足2°,令a==1,另取=mn12,bx, 重新计算。 §2最优性条件 考虑无约束问题(1) min f( 定义2下降方向 对于问题(1),设X∈R"是任一给定点,p为非零向量。若存在δ>0,使Vλ∈(0,),有 ∫(x+φ)<f(x),则称p为∫(x)在X点的下降方向。 定理4设f(x)在x∈R"上可微,若存在向量p∈R",使得 vf(x)p<o (8) 则P必为f(x)在X点的下降方向 177
177 如果函数 ( ) x 是严格拟凸的（与单峰函数大体相当），则通过计算在这个区间内两点的值，不 定区间能够被缩小。对此有以下定理： 定理 3：设 1 1 : R R → 在区间 a b, 上严格拟凸，设 , a b, ， ，若 ( ) ( ) ， 则对 x a[ , ] ， ( ) ( ) x ;如果 ( ) ( ) ，则对 x b [ , ] ， ( ) ( ) x （不然，对前 者则应有 ( ) ( ) x ，由 = + − x (1 ) = ( ) max{ ( ), ( )} ( ) x ，矛盾）。 精确一维搜索计算量大，并且有时意义不是很大，反不如计算量小的不精确搜索效果好，后者 只要求 1 ( ) k f x + 比 ( ) k f x 下降一定数量，以及 1 ( ) k T k f x s + 的绝对值比 ( ) k T k f x s 的小一定数量。 现在通常采用 Goldstein（1965）和 Powell（1975）提出的两个条件来设计不精确一维搜索方法， 即对给定常数 1 2 1 2 c c c c , ,0 1 ，要求 1°、 1 1 ( ) ( ) ( ) 0 k k k T k k f x f x c f x s + − − 2°、 1 2 ( ) ( ) k T k k T k f x s c f x s + 常取 c c 1 2 = = 0.1, 0.5。 设区间 a b, (0, ) = + ，先取 =1 ，若 满足要求 1 0 、2°，令 = k ;若 不满足 1°， 令 b = = 1 ，另取 1 2 a + = ，重新计算；若 不满足 2°，令 a = = 1 ，另取 1 min{2 , } 2 b + = ， 重新计算。 §2 最优性条件 考虑无约束问题(1): → n n x R min f (x) ( f : R R) 定义 2 下降方向。 对于问题（1），设 n x R 是任一给定点， p 为非零向量。若存在 0 ，使 (0, ) ，有 f (x + p) f (x) ，则称 p 为 f (x) 在 x 点的下降方向。 定理 4 设 f (x) 在 n x R 上可微，若存在向量 p n R ，使得 f (x) p 0 T （8） 则 p 必为 f (x) 在 x 点的下降方向