o(x)0(x)20=1.n 从而(1)式右边第三项亦是|-的高阶无穷小故(1)可写成 f(x)=f(x)+ 2 (x)+ (12) ax 其中第二项由于假定0(xmil,故其不是|-x的高阶无穷小且由于(10)成立故必有 f(x)<f(x),x∈O(x,o)/x∩s 这说明x是问题(1)的严格局部最优解,即在上述条件下、10)是取极值的充分条件 §2、可行方向法 最早的可行方向法是1960年由G、 Zoutendijk提出的,现在可行方向法已发展成求解约束优化 问题的一类重要方法。其基本思想是:在给定一个可行点x之后,用某种办法确定一个改进的可行 方向S,然后沿S求解一个有约束的线搜索问题,得极小点2,令x41=x+AS。若x仍不 是最优解,则重复上述步骤。各种不同的可行方向法的主要区别在于:选择可行方向sk的策略不同 大体可分为三类 1)用求解一个线性规划问题来确定S,如 Frank--Wole方法, Zoutendijk方法等 2)利用投影矩阵直接来构造一个改进可行方向S,如 Rosen投影梯度法 3)利用既约梯度直接构造出一个改进的可行方向Sk,如 Wolfe既约梯度法及其各种改进。 下面介绍其中的几种: 1° Frank-Wolfe方法 考虑非线性规划问题 min f(x) st.Ax≤b (13) Bx= d 其中A和B分别是m×n和×n阶矩阵,且B是行满秩的 b和d分别是m和1维列向量,令
204 lim * x→x i i i x f x x f x − ( ) ( ) ( ) =0,i=1, n 从而(11)式右边第三项亦是 x − x * 的高阶无穷小,故(11)可写成 ( ) ( ) ( ) ( ) (x ) * n ( ) i 1 * i * x x x f x f x f x x i i i + − = + − = (12) 其中第二项由于假定 0 ) ( * lim → x f x x ,故其不是 x − x * 的高阶无穷小,且由于(10)成立,故必有 ( ) ( ), * f x f x x * * (x , )/ x S 这说明 * x 是问题(1)的严格局部最优解,即在上述条件下,(10)是取极值的充分条件. §2、可行方向法 最早的可行方向法是 1960 年由 G、Zoutendijk 提出的，现在可行方向法已发展成求解约束优化 问题的一类重要方法。其基本思想是：在给定一个可行点 x k 之后，用某种办法确定一个改进的可行 方向 S k，然后沿 S k 求解一个有约束的线搜索问题，得极小点 k ,令 k k k k x = x + S +1 。若 k+1 x 仍不 是最优解，则重复上述步骤。各种不同的可行方向法的主要区别在于：选择可行方向 S k 的策略不同， 大体可分为三类： 1) 用求解一个线性规划问题来确定 S k，如 Frank---Wolfe 方法，Zoutendijk 方法等。 2） 利用投影矩阵直接来构造一个改进可行方向 S k ,如 Rosen 投影梯度法。 3） 利用既约梯度直接构造出一个改进的可行方向 S k ,如 Wolfe 既约梯度法及其各种改进。 下面介绍其中的几种： 1°Frank—Wolfe 方法 考虑非线性规划问题 = Bx d st Ax b f x . . min ( ) （13） 其中 A 和 B 分别是 m n和l n 阶矩阵，且 B 是行满秩的。 b 和 d 分别是 m 和 l 维列向量，令
S=4x≤b,Bx=d,x∈Ry 表可行域,假定f(x)在包含S的某个开集D上是连续可微的函数 任取一初始可行点x∈S,在x处以f(x)的-阶 Taylor展开式作为f(x)的线性逼近函数: F(x)=f(x)+Vf(x)(x-x 求线性规划问题 的解显然等价于求解线性规划问题: min Vf(x)x (14) 为了保证(11)有有限解,假设对于任意可行点x∈S,线性函数vf(x)x在S上有下界 令(14)的最优解为y,下面分两种情形讨论。 )若Vf(x2)(y-x)=0,即x也是(14)的最优解,则迭代停止 2)若Vf(x2)(y2-x)≠0,此时必有 Vf(x)( )<0 则由第二章定理2,(y-x°)是∫(x)在x点的下降方向,又因y∈S,x∈S,且S为凸集,故 x+A(y-x)∈S(0<λ<1),从而y-x是可行方向。因此,从x出发,沿此方向进行一维搜 索,即求 min f(x+a (y-x)) 0<A<l 的最优解λ,令x=x+(y-x),则x是x与y连线上f(x)的最小值,且x3∈S,当A足 够小时有 f(x)≤f(x*+λ(y-x) =f(x)+avf(x)(y-x)+o xp<f(x) 得到x之后,再于x处线性逼近∫(x),重复上述步骤 注意:(14)是线性的,K-T条件中不含x,但是不同的x因松紧性不同,故有别。即只有最优解xk
205 n S = x Ax b, Bx = d, x R 表可行域，假定 f (x) 在包含 S 的某个开集 D 上是连续可微的函数。 任取一初始可行点 x S 。 ，在 。 x 处以 f (x) 的一阶 Taylor 展开式作为 f (x) 的线性逼近函数： F（x）= f (x 。）+ f（x 。）（T x − x 。） 求线性规划问题 min F(x) xS 的解显然等价于求解线性规划问题： f x x T x S min ( 。） （14） 为了保证（11）有有限解，假设对于任意可行点 x S 。 ，线性函数 f x x 。）T ( 在 S 上有下界。 令（14）的最优解为 。 y ，下面分两种情形讨论。 1） 若 ( ）( − ）= 0 。 。 。 f x y x T ，即 。 x 也是（14）的最优解，则迭代停止。 2） 若 ( ）( − ） 0 。 。 。 f x y x T ，此时必有 ( ）( − ） 0 。 。 。 f x y x T 则由第二章定理 2， (y 。 − x 。） 是 f (x) 在 。 x 点的下降方向，又因 y S x S 。 。 , ，且 S 为凸集，故 x + (y − x） S(0 1) 。 。 。 ，从而 。 。 y − x 是可行方向。因此，从 。 x 出发，沿此方向进行一维搜 索，即求 f x 。 + （y 。 − x 。）） min ( 0 1 的最优解 ，令 x 1 = x 。 + （y 。 − x 。） ，则 x 1是 x 。与 y 。连线上 f (x) 的最小值，且 x S 1 ，当 足 够小时有 ( ) ( ) f x 1 f x 。 + （y 。 − x 。） ( ) ( ( ) 。 。）（ 。 。） （ 。 。） 。 f x f x y x o y x f x T = + − + − 得到 x 1 之后，再于 x 1 处线性逼近 f (x) ，重复上述步骤。 注意：（14）是线性的，K-T 条件中不含 x，但是不同的 x 因松紧性不同，故有别。即只有最优解 x k