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因松紧性不同,故有别。即只有最优解xk205   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) xS 的解显然等价于求解线性规划问题： 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