向量,于是由(20)可得 PVf(r)=V(x)+Mo+ a=o 从而 Pvf(x)-PVf(x)=Mo-o)-u a=0 而,<0。上式说明M的所有行向量线性相关,从而与M行满秩的假设相矛盾。这就证明了 网v(x)≠0.又易见P是投影矩阵,因此由v(xyS=-V(x)v(x=1y(x)<0,可 知S=-PVf(x)是一个下降方向。下面再证S是一个可行方向。首先注意到MP=0,因此 S=MS=-MPV(x)=0,可见要证S是可行方向,只要证aS≤0就够了 B 用a,P乘(21),并注意到PM=0,就有 a, PVf(x)+a PMO+a Pu, a=-aS+u, Pa=0 由于P是半正定的,而u2<0,所以上式成立意味着a,S≤0,即S为可行方向 证毕。 从x出发沿S作一维搜索时,步长A的确定与 Zoutendijk的相同 S4、既约梯度法 这种方法是1963年首先由 Wolfe提出来的,当时是为了解决具有线性约束条件的非线性规划问 题,1969年,由 Abadie与 Carpentier推广到解决非线性约束条件的问题,既约梯度法的基本思想是 利用约束条件将所考察问题中某些变量用其它一组独立变量来表示,如对线性约束,将非基变量当 作独立变量,把基变量用非基变量表示,消去目标函数中的基变量,那么目标函数在低维(n-m维) 空间中的负梯度方向便是原问题的一个下降方向,再考虑到可行性,就可确定一个下降可行方向。 线性约束情形 考察如下的线性约束优化问题 min f(x) s.t. Ax=b (22) ≥0 其中A为mXn矩阵,Rank(A)=m,x∈R",b∈R",m≤n。设∫(x)连续可微,问题(22) 的可行集的每一个顶点都是非退化的,即每个顶点x都有m个正分量。 定理12设x是问题(22)的一个可行解,使得x=(xB2x),xB>0,其中A=(B,N),而 基矩阵B是mXm可逆矩阵,用I表示基变量指标集,令y=V(x)-VB/(x)BA=(B,y)。 210210 向量，于是由（20）可得 0 ˆ  ( ) =  ( ) + + = T j j T P f x f x M  u a （21） 从而 ( ˆ ) 0 ˆ ( ) ( ) ˆ  −  = − − = T j j T P f x P f x M   u a 而 u j  0 。上式说明 M 的所有行向量线性相关，从而与 M 行满秩的假设相矛盾。这就证明了 ( ) 0 P ˆ f x  。又易见 P ˆ 是投影矩阵，因此由 ( ) ( ) ˆ ( ) ˆ ( ) 0 2 f x S = −f x Pf x = − Pf x  T T ，可 知 ( ) ˆ S = −Pf x 是一个下降方向。下面再证 S 是一个可行方向。首先注意到 0 M ˆ P ˆ = ，因此 ( ) 0 ˆ ˆ ˆ ˆ 1 = = −  =         S MS MP f x B A ，可见要证 S 是可行方向，只要证 a j S  0 就够了。 用 ajP ˆ 乘（21），并注意到 0 ˆ ˆ = T PM ，就有 0 ˆ ˆ ˆ ˆ ( ) ˆ  + + = − + = T j j j j T j j j T a jP f x a jPM  a Pu a a S u a Pa 由于 P ˆ 是半正定的，而 u j  0 ，所以上式成立意味着 a j S  0 ，即 S 为可行方向。 证毕。 从 k x 出发沿 k S 作一维搜索时，步长  max 的确定与 Zoutendijk 的相同。 §4、既约梯度法 这种方法是 1963 年首先由 Wolfe 提出来的，当时是为了解决具有线性约束条件的非线性规划问 题，1969 年，由 Abadie 与 Carpentier 推广到解决非线性约束条件的问题，既约梯度法的基本思想是： 利用约束条件将所考察问题中某些变量用其它一组独立变量来表示，如对线性约束，将非基变量当 作独立变量，把基变量用非基变量表示，消去目标函数中的基变量，那么目标函数在低维（n－m 维） 空间中的负梯度方向便是原问题的一个下降方向，再考虑到可行性，就可确定一个下降可行方向。 线性约束情形 考察如下的线性约束优化问题 min ( ) . . 0 f x s t Ax b x    =    （22） 其中 A 为 m n 矩阵，Rank（A）＝m， n x R  ， m b R  ，m n  。设 f x( ) 连续可微，问题（22） 的可行集的每一个顶点都是非退化的，即每个顶点 x 都有 m 个正分量。 定理 12 设 x 是问题（22）的一个可行解，使得 ( , )T B N x x x = ， xB  0 ，其中 A B N = ( , ) ，而 基矩阵 B 是 m m 可逆矩阵，用 I 表示基变量指标集，令 1 ( ) ( ) T T T  f x Bf x B A− =  − ( , ) T T B N =  