第二章无约束最优化 §1一维搜索 对于无约束问题 mIn (x ∈R 的求解思路,根据上一章最优性条件的分析可有两条: 1°、若f(x)可微,则可考虑求稳定点 Vf(x=0 (2)是一非线性方程组,可以动用求解非线性方程组的手段处理,不过这也是相当复杂的问题,何 况若∫(x)不可微,此路便行不通,故通常都采用使目标函数逐次下降的搜索方法 °、搜索方法是从某一初始点x°出发,先选择一个下降方向s°,然后于方向s上找一点 x=x+As"(4>0),使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,B1时称为超线性收敛,超线 性收敛的另一种形式是,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,kk2o(x),p(x3)0,当A>→0(4)≥(),→去掉(λb]。3,若φ(λ)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],Ao(), 则对vx∈[a,4],q(x)≥0();如果(2)≤q(4),则对vx∈[,b],q(x)≥9()(不然,对前 者则应有(x)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 点的下降方向
证:由 Taylor公式得 f(x+ dp)=f(x)+ivf(x)p+o(a p D 若(8)式成立,则易知定理结论成立 证毕 若ⅴf(x)≠0,取P=-f(x),(8)式自然成立,故知此时负梯度方向一定是下降方向。 定理5设f(x)在点x∈R"处可微,若x是问题(1)的局部最优解,则必有 Vf(x')=0 证:用反证法。若Vf(x)≠0,则在x点必存在下降方向-Vf(x*),从而与x是局部最优解的 假设矛盾,故Vf(x)=0 证毕 定理6(二阶必要条件)设∫(x)在点x'∈R”处二阶可微,若x是局部最优解,则vf(x)=0 且Hese矩阵H(x)半正定。 证:此时有 f(x+4)=f(x')+pH(x')p+o(2‖p|) 因x是局部最优解,故当λ充分小时,pH(x)p≥0,由p的任意性知,H(x)半正定。证毕 定理7(二阶充分条件)设∫(x)二阶可微,若Vf(x')=0,V2f(x)=H(x)正定,则x是问 题(1)的严格局部最优解 证:由H(x)正定,故vp,pH(x')p>0,于是对充分小的必有 12pH(x')p+o(2‖p2)>0 又因Vf(x)=0,从而由 aylor公式知,f(x2+4)>f(x) 证毕 在使用上述最优性条件的过程中,人们普遍感到求得驻点x后,再计算Hese矩阵并判断其是 否正定有时相当麻烦,计算量也很大,更何况有时Hese矩阵半正定或有些函数的极值恰好在梯度 不存在的点处取得,则以上二阶充分条件便不能使用 19860年Boo0给出了八(x)是问题(1)严格局部最优解的一阶充分条件
178 证： 由 Taylor 公式得 f (x p) f (x) f (x) p ( || p ||) T + = + + 若(8)式成立，则易知定理结论成立。 证毕 若 f (x) 0 ，取 p = − f (x) ，(8)式自然成立，故知此时负梯度方向一定是下降方向。 定理 5 设 f (x) 在点 n x R * 处可微，若 * x 是问题(1)的局部最优解，则必有 ( ) 0 * f x = 。 证： 用反证法。若 ( ) 0 * f x ，则在 * x 点必存在下降方向 ( ) * − f x ，从而与 * x 是局部最优解的 假设矛盾，故 ( ) 0 * f x = 。 证毕 定理 6 （二阶必要条件）设 f (x) 在点 n x R * 处二阶可微，若 * x 是局部最优解，则 ( ) 0 * f x = ， 且 Hesse 矩阵 ( ) * H x 半正定。 证： 此时有 ( ) ( || || ) 2 1 ( ) ( ) * * 2 * 2 2 f x p f x p H x p p T + = + + 因 * x 是局部最优解，故当 充分小时， p H x p T ( ) * 0 ，由 p 的任意性知， ( ) * H x 半正定。 证毕 定理 7 （二阶充分条件）设 f (x) 二阶可微，若 ( ) 0 * f x = ， ( ) ( ) 2 * * f x = H x 正定，则 * x 是问 题（1）的严格局部最优解。 证： 由 ( ) * H x 正定，故 p, p H x p T ( ) * 0 ，于是对充分小的 必有 ( ) ( || || ) 0 2 1 2 * 2 2 p H x p + p T 又因 ( ) 0 * f x = ，从而由 Taylor 公式知， ( ) ( ) * * f x + p f x 。 证毕 在使用上述最优性条件的过程中，人们普遍感到求得驻点 * x 后，再计算 Hesse 矩阵并判断其是 否正定有时相当麻烦，计算量也很大，更何况有时 Hesse 矩阵半正定或有些函数的极值恰好在梯度 不存在的点处取得，则以上二阶充分条件便不能使用。 1986 年 Botsko 给出了 ( ) f x 是问题（1）严格局部最优解的一阶充分条件：
定理8设o(x’,6)表示以点x'=(xx2,…,x)∈R"为中心以8为半径的开球,又已知 n元函数f(x)(x∈R")在o(x,d)内连续,且在o(x,d)/{x}内可微,若x∈o(x,)/{x} 都有 )Vf(x) 则x是问题(1)严格局部最优解。 证:利用一阶 Taylor公式,将f(x·)在x点展开 f(x)=f(x)+V(x)(x-x)+(-x) (10) 由于(9)成立,故有Vf(x)(x-x)<0,Vx∈o(x’,δ)/{x'"},于是由(10)约略有 f(x°)<f(x),yx∈o(x,6)/{x'} 格地由中值公式及(9),有 f(x-f(x=Vf(x) ==V('(-x 其中x=x+6(x-x2)0<0<1 这说明x是问题(1)严格局部最优解。 上述一阶充分条件克服了以往的某些不足,是对原最优性条件的很好补充,但由于x的不确定性 这有时给检验(11)式是否成立带来一定的困难。下面的几个改进结果,可使其发挥更大的作用 °设O(x,δ)表示以点x=(x,x2…,x)∈R"为中心以δ为半径的开球,n元函数 f(x)x=(x1,x2…x,)∈R")在o(x,δ)内连续,在o(x,δ)/{x}内可微,则x是问题(1)的局部 最优解的必要条件是 ≥0,i=1.2 其中 ),i 证:若x是问题(1)的局部最优解,由(10)必有 (x-x)Vf(x)≥0,Vx∈o(x,d)/{x'} 179
179 定理 8 设 ( , ) * x 表示以点 T n x = x x xn R ( , , , ) 1 2 为中心以δ为半径的开球，又已知 n 元函数 ( )( ) n f x x R 在 ( , ) * x 内连续，且在 ( , ) * x / { } x 内可微，若 x ( , ) * x / { } x ， 都有 ( − ) ( ) 0 x x f x T (9) 则 x 是问题（1）严格局部最优解。 证: 利用一阶 Taylor 公式,将 f( ) x 在 x 点展开: f (x ) f (x) f (x) (x x) ( x x ) T = + − + − (10) 由于(9)成立,故有 f (x) (x x) T − <0, x ( , ) * x / { } x ,于是由(10)约略有 f (x ) f (x), x ( , ) * x / { } x 严格地,由中值公式及(9),有 ( ) ( ) 0 1 ( ) − ( ) = ( ) ( − ) = − f x f x f x x x f x x x T T 其中 = + ( − ),0 1 x x x x . 这说明 x 是问题（1）严格局部最优解。 证毕 上述一阶充分条件克服了以往的某些不足，是对原最优性条件的很好补充，但由于 x 的不确定性， 这有时给检验(11)式是否成立带来一定的困难。下面的几个改进结果，可使其发挥更大的作用[33]。 1 ° 设 ( , ) * x 表示以点 T n x = x x x n R ( , , , ) * * 2 * 1 为中心以 为 半 径 的 开 球 ， n 元函数 ( )( ( , , , ) ) 1 2 T n f x x = x x x n R 在 ( , ) * x 内连续，在 ( , ) * x / { } x 内可微，则 x 是问题（1）的局部 最优解的必要条件是 i i i i x f x x x − ( ) ( ) ( ) 0，i = 1,2, ,n (11) 其中 T i i i n i x (x , x , , x , x , x , , x ) 1 2 1 1 ( ) + − = ，i = 1,2, ,n 。 证: 若 x 是问题（1）的局部最优解,由(10)必有 ( − ) ( ) 0 x x f x T , x ( , ) * x / { } x
将x"=(x’,x2…x-,x,x1…,x),l=12,…,n代入上式即得( 证毕 据10可立得 2°在1°的假设条件下,若61>0,可1≤j≤n,满足x∈o(x,01)/{x},且有 a(x0) ”则它 差不多还是x为问题(1)的局部最优解的充分条件。特别是当Vf(x)在x某邻域连续,且 ⅴ∫(x)≠0(条件极值情形)时,此条件充分性一定成立。不过若vf(x)=0,则还需增加一定 的条件,这就是下面的 3°在1°的假设条件下,若V点x∈o(x,d)/{x”},有 x1-x2 >0,i=1.2. (13) af(x) af(x x;)( ∑(x,-x2)9(x") 则x是问题(1)的严格局部最优解 (14)有极限形式 xi-xi af(x) (15)用起来往往更便捷 4°在1°的假设条件下,若f(x)是伪凹函数,且条件(11)成立,则x是局部最优解。 180
180 将 T i i i n i x (x , x , , x , x , x , , x ) 1 2 1 1 ( ) + − = ，i = 1,2, ,n 代入上式即得(11). 证毕 据 1 0 可立得: 2° 在 1°的假设条件下，若 1 0,j,1 j n ，满足 ( j) x ( , ) 1 * x / { } x ，且有 0 ( ) ( ) ( ) * − j j j j x f x x x (12) 则 x 一定不是问题（1）的局部最优解。 容易看出，若把条件 i i i i x f x x x − ( ) ( ) ( ) 0，i = 1,2, ,n 式中的符号“ ”换成“ ”，则它 差不多还是 x 为问题（1）的局部最优解的充分条件。特别是当 f(x)在 x 某邻域连续，且 ( ) 0 * f x （条件极值情形）时，此条件充分性一定成立。不过若 ( ) 0 * f x = ，则还需增加一定 的条件，这就是下面的 3° 在 1°的假设条件下，若 点 x ( , ) * x / { } x ，有 i i i i x f x x x − ( ) ( ) ( ) 0，i = 1,2, ,n ； （13） 及 1 ( ) ( ) ) ( ) ( ) ( )( 1 ( ) * 1 ( ) − − − − = = n i i i i i n i i i i i i x f x x x x f x x f x x x ， (14) 则 x 是问题（1）的严格局部最优解。 (14)有极限形式: * lim x→x = = − − n i i i i i n i i i i x f x x x x f x x x 1 ( ) * 1 ( ) ( ) ( ) ( ) = >0 (15) (15)用起来往往更便捷. 4°在 1°的假设条件下，若 f (x) 是伪凹函数,且条件(11)成立,则 x *是局部最优解
由伪凹函数的性质及(11)知必有 f(x)≥f(x),i=1,n,yx∈o(x,6)/{x'} 注意当x∈o(x,6)/{x”}时有 x=(x+△x1…x+△x)=(x+mAx1,x…x)+…(x,x…x+nxn)=∑ 其中x=(x1,…x1,x+n△x1…x) 可取Ax(=1…n)适当小使x0=(x,…x1,x+nAx1…x)∈o(x,δ){x},由于 伪凹函数一定是拟凹函数,于是便有 (x)=/(∑)minf(x0)≥f(x*) 从而x为局部最优解 5°在1°的假设条件下,若V1>0,五k≠j,1≤k,j≤n,满足 x),x∈o(x,)/{x'},且对k有(12)式成立,对j有(13)式成立,则x一定不是f(x) 的极值点。 °在1°的假设条件下,若Vd1>0,五k,1≤k≤n,≠x,满足 04x4-xk61,04X-xk1,且对x有(12)式成立,对有(13)式成立,则x 定不是f(x)的极值点。 例判断四元函数f(x)=x12-2x2+x32-x42+4xx2+2x2x3+6xx3+2x2x4的极值情况。 解易解得唯一驻点x=(0,0,0,0)。 但Vx,≠0,i=1,2,总有 xf1(x10,0,0)=2x12>0 f2(0,x2,0,0)=-4x2<0 l81
181 由伪凹函数的性质及(11)知.必有 ( ) ( ) ( ) * f x f x i ,i=1,…n, x ( , ) * x / { } x 注意当 x ( , ) * x / { } x 时有 ( ) 1 * * 1 2 * 1 * * 1 1 2 * 1 * 1 1 * 1 ( , ) ( , ) ( , ) i n i n n n n n n n n x x x x x x n x x x x x x n x x = = + + = + + + = 其中 ( , , , ) * * * 1 * 1 ( ) i i i n i x = x x x + nx x − 可取 x（i i = 1, n） 适当小,使 ( , , , ) * * * 1 * 1 ( ) i i i n i x = x x x + nx x − ( , ) * x / { } x ,由于 伪凹函数一定是拟凹函数，于是便有 f (x) = f ( ( ) 1 1 i n i n x = ) min ( ) ( *) ( ) f x f x i i 从而 * x 为局部最优解。 5 0 在 1°的假设条件下，若 1 0, k j, 1 k, j n ，满足 ( ) ( ) , k j x x ( ) 1 * x ， / { } x ，且对 k 有（12）式成立，对 j 有（13）式成立，则 x 一定不是 f (x) 的极值点。 6° 在 1°的假设条件下，若 k k k k n x x ~ 0, , 1 , 1 ，满足 1 1 | ~ 0 | − | , 0 | − k k k k x x x x ，且对 k x 有（12）式成立，对 k x ~ 有（13）式成立，则 x 一 定不是 f (x) 的极值点。 例 判断四元函数 1 2 2 3 1 3 2 4 2 4 2 3 2 2 2 1 f (x) = x −2x + x − x + 4x x + 2x x +6x x + 2x x 的极值情况。 解 易解得唯一驻点 x = （0，0，0，0）。 但 xi 0, i = 1,2 ，总有 ( ,0,0,0) 2 0 2 x1 f 1 x1 = x1 ； (0, ,0,0) 4 0 2 x2 f 2 x2 = − x2
故由4°知,点(0,0,0,0)不是极值点。所以,函数f(x)无极值。 §3下降法 对于无约束问题(1)的求解思路,根据前述分析,通常都采用使目标函数逐次下降的搜索方法 在一维搜索的基础上,对于搜索方向s4选择的不同方式,就得到各种不同的方法。下面介绍几种常 见的方法。 1°最速下降法(梯度法) 取s4=-Vf(x3),则在精确一维搜索之下便有 f(x-a vf(x=mn f(x-avf(x ) n vf(x) 它因目标函数局部下降最快而得名。对之有以下收敛结果 定理9设f(x)具连续一阶偏导数,给定x°∈R",f(x°)=a,假定水平集 sa={x|f(x)≤a}有界,令{x}是由最速下降法产生的点列,则{x}的每一个聚点x满足 f(x)=0。 证:显然f(x3)严格下降,故有极限,记mf(x2)=f”,由f(x3)的严格单调性知,对{x*} 的任一收敛子列{x},亦有lmf(x+)=f,设x4→x若Vf(x)≠0,则对适当小的>0, 有 f(x -avf(x))<f(x)=f 从而由连续性,必有充分接近x的x∈{x3},使 f(x)=f(x5-2V(x5)sf(x5-v(x5)<fx)=f 但x∈{x}{x4},故必有f(x4)≥f,矛盾。因此,必有Vf(x)=0。 由定理6知,Vf(x4)s4=-Vf(x)Vf(x3)=0。即相继两次迭代中,搜索方向是正交 的,这使得最速下降法通过极小点的路线是锯齿形的,并且越靠近极小点步长越小,收敛越慢。这 182
182 故由 4°知，点（0，0，0，0）不是极值点。所以，函数 f (x) 无极值。 §3 下降法 对于无约束问题(1)的求解思路，根据前述分析，通常都采用使目标函数逐次下降的搜索方法。 在一维搜索的基础上，对于搜索方向 k s 选择的不同方式，就得到各种不同的方法。下面介绍几种常 见的方法。 1° 最速下降法（梯度法） 取 ( ) k k s = −f x ，则在精确一维搜索之下便有 = − − = − + ( ) ( ( )) min ( ( )) 1 k k k k k k k k k x x f x f x f x f x f x （16） 它因目标函数局部下降最快而得名。对之有以下收敛结果： 定理 9 设 f (x) 具连续一阶偏导数，给定 x n R ， ( ) = f x ，假定水平集 { | ( ) } s = x f x 有界，令{ k x }是由最速下降法产生的点列，则{ k x }的每一个聚点 * x 满足 ( ) 0 * f x = 。 证： 显然 ( ) k f x 严格下降，故有极限，记 * lim f (x ) f k k = → ，由 ( ) k f x 的严格单调性知，对{ k x } 的任一收敛子列{ i k x }，亦有 * lim f (x ) f i k i = → ，设 * x x i k → ,若 ( ) 0 * f x ，则对适当小的 0 ， 有 * * * * f (x − f (x )) f (x ) = f 从而由连续性，必有充分接近 * x 的 i k x { } i k x ，使 i i i k k k f x = f x − + ( ) ( 1 * * f (x )) f (x f (x )) f (x ) f i i i k k k − = 但 { } { } 1 k k k x x x i+ i ，故必有 * ( ) 1 f x f i k + ，矛盾。因此，必有 ( ) 0 * f x = 。 由定理 6 知， ( ) ( ) ( ) 0 1 1 = − = k+ T k k+ T k f x s f x f x 。即相继两次迭代中，搜索方向是正交 的，这使得最速下降法通过极小点的路线是锯齿形的，并且越靠近极小点步长越小，收敛越慢。这
