第四章 不等式约束的优化
§1、最优性条件考虑不等式约束的优化问题。
（1）
定义1 设是非空集合，若及，有，则称集合C为以原点为顶点的锥。如果锥C又是凸集，则称C为凸锥。
定义2 设非空，是可行解集，点闭包，若对某P∈Rn,P≠0,存在数δ〉0，使，均有则称P为点处的可行方向。
用D表示在S中从出发的所有可行方向向量的集合，即
称为在点处的可行方向锥。
若记，则对局部最优解来说，必有
（2）
这是因为在最优点x*，不可能存在下降的可行方向，反之若于某点x*已不存在下降的可行方向，则此点一定是局部最优解。
定义3 若问题（1）的一个可行点使某个不等式约束变成等式即，则该约束称为关于的起作用约束（紧约束），否则，即则称之为不起作用约束（松约束）。
用集合表示在可行点的紧约束指标集。
定理1 设x*是问题（1）的可行点，在x*可微，在x*连续，如果x*是局部最优解，则
（3）
其中，称G0为S在点x*处的局部约束方向锥（或内方向锥）
证明：（略）(提示:只需证G0)
条件（2）和（3）均为几何最优性条件，实际计算中不好用，下面由之引出经常使用的代数最优性条件。
定理2（Fritz-John必要条件） 设x*是（1）的可行解，在x*可微，
在x*连续，如果x*是局部最优解，则存在不全为0的数使得
（4）
通常称（4）为Fritz-John必要条件，满足（4）的点称为Fritz-John点，如果在x*也可微，则有
（5）
证：因x*是（1）的局部最优解，由定理1知，即不存在向量使得和（）同时成立，若，且记
于是AP<0无解。根据Gordan定理（第一章定理8）存在非0向量，使记，则有
这就证明了(4)。
如果也可微，只要令就有改述的Fritz-John条件（5）。（5）中的第二式又称为互补松弛条件。
在Fritz-John条件中，当时，目标函数梯度消失，这不利于寻找最优点。例如问题
在最优点处，由F-J条件，有
成立，仅当（此时可以取，任意）。为了保证，需要再加一些约束条件，这样一些附加约束条件通常称为约束规格，约束规格可以不同，下面定理所加约束规格是最自然的和容易想到的。
定理3（Kuhn-Tucker必要条件） 设x*是问题（1）的可行解，在x*可微，在x*连续，再假设线性无关，如果x*是局部最优解，则存在使得
（6）
通常称（6）式为Kuhn-Tucker条件，简称K-T条件，满足这个条件的点称为K-T点，如果再假定在x*也可微，则上述K-T条件可写成
（7）
证：由定理2知，存在使
由于线性无关，故必，从而，以除上式并令，则，这说明（6）成立。
如果也可微，只要令就有改述的K-T条件（7）。称为Lagrange乘子，（7）中的第二式称为互补松弛条件。
K-T条件有明显的几何意义：对于任意一组，向量属于起作用约束函数梯度向量所张成的锥，由（6）知
即目标函数的负梯度向量属于这个锥。
若f(x)是凸函数，则K-T条件还是充分的。
定理4（K-T充分条件） 若是可微凸函数，可行点x*满足K-T条件，则x*是问题（1）的全局最优解。
证：令因为为凸函数，所以S为凸集，的凸性，有
由于在点x*满足K-T条件，则有，使得
又由于是凸函数，故又有
因当时，，从而，进而，故
即x*是全局最优解。
定理4的条件可以减弱，利用伪凸和拟凸的概念，仿定理4的证明有以下结果。
定理5 若是伪凸函数，是可微拟凸函数，可行点x*满足K-T条件，则x*是问题（1）的全局最优解。
定理条件还可以减弱为f在x*点伪凸，在点x*可微拟凸，则相应的结论成立。
对于既有等式约束又有不等式约束的一般数学规划问题（8）：
（8）
只需令，然后考虑
便会得到与定理2、3的相应结果，下面仅叙述相应的K-T条件。
定理6（K-T必要条件） 设x*是问题（8）的可行解，可微，再假设和线性无关，如果是局部最优解,则存在
，使得
（9）
若问题是凸规划则亦可证K-T条件是充分的。
可把Botsko改进条件用于(1),有结果:
定理7假定于上连续,且.如果条件
(10)
成立,其中,S是可行解域,则是问题(1)的严格局部最优解.
证明:由Taylor公式:
可有
(11)
当x,x(i) 且充分小时,由于的连续性,故有
=0,i=1,
从而(11)式右边第三项亦是的高阶无穷小,故(11)可写成
(12)
其中第二项由于假定,故其不是的高阶无穷小,且由于(10)成立,故必有
这说明是问题(1)的严格局部最优解,即在上述条件下,(10)是取极值的充分条件.
§2、可行方向法
最早的可行方向法是1960年由G、Zoutendijk提出的，现在可行方向法已发展成求解约束优化问题的一类重要方法。其基本思想是：在给定一个可行点xk之后，用某种办法确定一个改进的可行方向Sk，然后沿Sk求解一个有约束的线搜索问题，得极小点,令。若仍不是最优解，则重复上述步骤。各种不同的可行方向法的主要区别在于：选择可行方向Sk的策略不同，大体可分为三类：
1) 用求解一个线性规划问题来确定Sk，如Frank---Wolfe方法，Zoutendijk方法等。
2） 利用投影矩阵直接来构造一个改进可行方向Sk,如Rosen投影梯度法。
3） 利用既约梯度直接构造出一个改进的可行方向Sk,如Wolfe既约梯度法及其各种改进。
下面介绍其中的几种：
1°Frank—Wolfe方法
考虑非线性规划问题
（13）
其中A和B分别是阶矩阵，且B是行满秩的。
b和d分别是m和l维列向量，令
表可行域，假定在包含S的某个开集D上是连续可微的函数。
任取一初始可行点，在处以的一阶Taylor展开式作为的线性逼近函数：
求线性规划问题
的解显然等价于求解线性规划问题：
（14）
为了保证（11）有有限解，假设对于任意可行点，线性函数在S上有下界。令（14）的最优解为，下面分两种情形讨论。
1） 若，即也是（14）的最优解，则迭代停止。
2） 若，此时必有
则由第二章定理2，是在点的下降方向，又因，且S为凸集，故，从而是可行方向。因此，从出发，沿此方向进行一维搜索，即求
的最优解，令，则x1是x。与y。连线上的最小值，且，当足够小时有
得到x1之后，再于x1处线性逼近，重复上述步骤。
注意：（14）是线性的，K-T条件中不含x，但是不同的x因松紧性不同，故有别。即只有最优解xk才与（13）有相同的K-T条件。
关于F-W方法的收敛判别准则，有如下定理：
定理8 若(11)的最优解yk满足,则是原问题（13）的K-T点。
证：显然，此时是（14）的最优解，从而也必是(14)的K-T点，由（14）与（13）有相同的K-T条件，立即可知是（13）的一个K-T点。证毕。
F-W方法虽然收敛较慢，但由于迭代求解的每一线性子规划（14）都具有相同约束条件（即可行域相同），因此可用灵敏度分析的手段处理一系列子规划问题（相当于目标函数系数变化检验数变化）这样，效果还是较好的。
2° Zoutendijk可行方向法
对于问题（13）先介绍一个确定下降可行方向的充要条件：
定理9 设x。是（13）的可行解，在 x。点有，其中，
，则非0向量S0是点x。处的可行方向的充要条件是：
（15）
证明：（简单从略）
由第二章定理2知，为使S0又是下降方向，这需满足
- （16）
因此在一点x0的下降方向可通过解下列线性规划问题来求得
（17）
这里加约束是为了获得一个有限解，因若存在满足（15）和（16），则对任意亦满足这些条件，进而导致（17）目标函数无下界，无法确定有限解S.
在问题（17）中，由于S=0是可行解，故最优值必定小于或等于0；若小于0，则最优解即为下降可行方向；若等于0，则以下定理保证x0是K-T点。
定理10 在无约束问题中，设x0是可行解，且，其中，,，则x0为K-T点的充要条件是问题（17）的目标函数等于0。
证：注意到问题（13）是线性约束问题，依定义，x0为K-T点等价于存在向量和，使得
令向量于是
依Farkas定理，这个系统有解的充要条件是，，无解。即无解，这等价于问题（17）的最优目标函数值等于0。所以x0是K-T点的充要条件是（17）的最优值为0。 证毕。
求得第k步迭代的下降可行方向Sk后，其最优步长应满足
由此出发不难推出（定理9）步长可由如下有约束的一维搜索求得
其中
对于非线性约束问题（1），我们知道，如果
（18）
则S是下降可行方向。
为求满足（18）的S，可解如下线性规划问题
(19)
(19)是由Zoutendijk首先提出，后来由Topkis和Veino等加以修正的可行方向法，可证由这种算法产生的点列的任一聚点都是Frita-John点。然后再验证（10）式成立，即知其为最优解。其特点是在确定移动方向时，无论起作用约束和不起作用约束都用上了，从而不致于在达到不起作用约束边界时，会使方向发生突然的变化。
§3、Rosen投影梯度法
这是Rosen在1960年针对线性约束的优化问题（13）首先提出来的，后来他又将该法推广到非线性约束情况，现已成为求解非线性规划的一类重要的有效方法。
梯度投影法的基本思想是，当迭代点在可行域内部时，取为迭代方向，当作无约束情形处理，当点在可行域边界上而且负梯度指向可行域的外界时，就改变方向沿梯度在边界上的投影搜索，使之成为可行方向，下边就问题（13）进行讨论。
设x是问题（13）的一个可行解，且使，这里,，设f(x)在x点可微，行满秩，则
是对零空间之投影矩阵（）。这样，若是下降可行方向。事实上（），故S是下降方向。又因
即，由定理9，S又是可行方向。
定理11 设x是（13）的一个可行解，分解,，使得
，若行满秩，，f在x可微，且，令，相应地分解
① 若，则x是一个K-T点。
② 若，令，置，其中是由中去掉第j行后得到的矩阵，令
则S是一个改进的可行方向。
证,① 因 ，即
（20）
所以若，则由K-T条件知x为一个K-T点。
② 首先证明（用反证法）设，并令
，可得，由于
可写成，这里是的第j列,是去掉第j个分量后的向量，于是由（20）可得
（21）
从而
而。上式说明M的所有行向量线性相关，从而与M行满秩的假设相矛盾。这就证明了。又易见是投影矩阵，因此由，可知是一个下降方向。下面再证S是一个可行方向。首先注意到，因此，可见要证S是可行方向，只要证就够了。
用乘（21），并注意到，就有
由于是半正定的，而，所以上式成立意味着，即S为可行方向。 证毕。
从出发沿作一维搜索时，步长的确定与Zoutendijk的相同。
§4、既约梯度法
这种方法是1963年首先由Wolfe提出来的，当时是为了解决具有线性约束条件的非线性规划问题，1969年，由Abadie与Carpentier推广到解决非线性约束条件的问题，既约梯度法的基本思想是：利用约束条件将所考察问题中某些变量用其它一组独立变量来表示，如对线性约束，将非基变量当作独立变量，把基变量用非基变量表示，消去目标函数中的基变量，那么目标函数在低维（n－m维）空间中的负梯度方向便是原问题的一个下降方向，再考虑到可行性，就可确定一个下降可行方向。
线性约束情形
考察如下的线性约束优化问题
（22）
其中A为矩阵，Rank（A）＝m，，，。设连续可微，问题（22）的可行集的每一个顶点都是非退化的，即每个顶点x都有m个正分量。
定理12设x是问题（22）的一个可行解，使得，，其中，而基矩阵B是可逆矩阵，用I表示基变量指标集，令。
是按下述规则确定：
–
(23)
(24)
若，则S是一个改进的可行方向，而S＝0的充要条件是x为K－T点。
证明：先证S是可行方向，据第二章定理2知，S是一个可行方向，当且仅当AS＝0，且若，则。由（24）知：。若是基变量，则，若不是基变量，则由（23）式可知，当且仅当时可以是负的，于是若，则，所以S是一个可行方向。下面证是一个改进方向。
由（23）知，，当时，则或不全为0，再乘一个不为0的自然不为0，从而显然有，由此可知S是一个改进方向。
最后证S＝0的充要条件是x为K－T点。注意到，x为K－T点当且仅当存在向量和，使得，，。因为，且，所以当且仅当，代入上式，可得，再代回上式可得。因此K－T条件简化为和
（25）
但是由S定义（23）可知，S＝0的充要条件是及0=，由于，此即（25）。
证毕。
计算步骤
1°选定计算精度，初始点满足，，其中，B为m×m可逆矩阵，用表示对应于B中向量的指标集，令k＝0。
2°计算，有n－m个分量，称为既约梯度。对，令，若，计算结束，为K－T点，否则转3°。
3°令（保证），求解线性搜索问题，得最优解。
4°令，若，令，转2°。若。求出中使那些下标i，将它们从中除掉，换入中使值最大的那些j，得出新的及相应的B，N，令，转2°。
例1：用既约梯度法求解。
·
解：取初始可行点。。
第一次迭代，，，，，，，，，。所以，，，。
解线性搜索问题，得最优解。因此，。
第二次迭代。在点，与相应的B，N为，，而，，，，，，，，，，。
解线性搜索问题，得最优解。因此，。
第三次迭代。在点，因此，，，，，，，，故为K-T点，而最优值为。
非线性约束情形
考察如下的标准非线性约束优化问题
（26）
一般的非线性约束优化问题总可化为上述形式，因为当约束条件为不等式时，可以通过引入松弛变量变成为等式约束，当无界时，可视或为无穷。假定连续可微，与线性约束类似，对任一可行点x，假定满足如下条件：（1），（2）若用表示对应于B中向量的指标集，用表示对应于N中向量的指标集，则，（3）令，，为在x点的m×m非奇异矩阵，，，，我们称为的既约梯度。
广义既约梯度法（GRG）计算步骤如下：
1．给定计算精度，选取初始可行解，分解，使其满足条件（1）、（2）、（3），令k＝0。
2．计算既约梯度。，按下面公式计算的分量。若，或，令，；否则令，。
3．若，计算结束，为K－T点，否则转第4步。
4．解非线性方程组，其中是按下式确定的，试取步长，则
得，对选择新基B，使，满足（1）、（2）、（3），令，返回2。
由上述可见，用于非线性约束情况的广义既约梯度法（GRG），是比较复杂的，在实际计算时，还有许多细节需要很好解决，才能取得好的效果，但值得注意的是，1970年以来的实际计算说明，在非线性约束优化算法的比较性研究中，GRG是比较优秀的之一。
§1、最优性条件考虑不等式约束的优化问题。
（1）
定义1 设是非空集合，若及，有，则称集合C为以原点为顶点的锥。如果锥C又是凸集，则称C为凸锥。
定义2 设非空，是可行解集，点闭包，若对某P∈Rn,P≠0,存在数δ〉0，使，均有则称P为点处的可行方向。
用D表示在S中从出发的所有可行方向向量的集合，即
称为在点处的可行方向锥。
若记，则对局部最优解来说，必有
（2）
这是因为在最优点x*，不可能存在下降的可行方向，反之若于某点x*已不存在下降的可行方向，则此点一定是局部最优解。
定义3 若问题（1）的一个可行点使某个不等式约束变成等式即，则该约束称为关于的起作用约束（紧约束），否则，即则称之为不起作用约束（松约束）。
用集合表示在可行点的紧约束指标集。
定理1 设x*是问题（1）的可行点，在x*可微，在x*连续，如果x*是局部最优解，则
（3）
其中，称G0为S在点x*处的局部约束方向锥（或内方向锥）
证明：（略）(提示:只需证G0)
条件（2）和（3）均为几何最优性条件，实际计算中不好用，下面由之引出经常使用的代数最优性条件。
定理2（Fritz-John必要条件） 设x*是（1）的可行解，在x*可微，
在x*连续，如果x*是局部最优解，则存在不全为0的数使得
（4）
通常称（4）为Fritz-John必要条件，满足（4）的点称为Fritz-John点，如果在x*也可微，则有
（5）
证：因x*是（1）的局部最优解，由定理1知，即不存在向量使得和（）同时成立，若，且记
于是AP<0无解。根据Gordan定理（第一章定理8）存在非0向量，使记，则有
这就证明了(4)。
如果也可微，只要令就有改述的Fritz-John条件（5）。（5）中的第二式又称为互补松弛条件。
在Fritz-John条件中，当时，目标函数梯度消失，这不利于寻找最优点。例如问题
在最优点处，由F-J条件，有
成立，仅当（此时可以取，任意）。为了保证，需要再加一些约束条件，这样一些附加约束条件通常称为约束规格，约束规格可以不同，下面定理所加约束规格是最自然的和容易想到的。
定理3（Kuhn-Tucker必要条件） 设x*是问题（1）的可行解，在x*可微，在x*连续，再假设线性无关，如果x*是局部最优解，则存在使得
（6）
通常称（6）式为Kuhn-Tucker条件，简称K-T条件，满足这个条件的点称为K-T点，如果再假定在x*也可微，则上述K-T条件可写成
（7）
证：由定理2知，存在使
由于线性无关，故必，从而，以除上式并令，则，这说明（6）成立。
如果也可微，只要令就有改述的K-T条件（7）。称为Lagrange乘子，（7）中的第二式称为互补松弛条件。
K-T条件有明显的几何意义：对于任意一组，向量属于起作用约束函数梯度向量所张成的锥，由（6）知
即目标函数的负梯度向量属于这个锥。
若f(x)是凸函数，则K-T条件还是充分的。
定理4（K-T充分条件） 若是可微凸函数，可行点x*满足K-T条件，则x*是问题（1）的全局最优解。
证：令因为为凸函数，所以S为凸集，的凸性，有
由于在点x*满足K-T条件，则有，使得
又由于是凸函数，故又有
因当时，，从而，进而，故
即x*是全局最优解。
定理4的条件可以减弱，利用伪凸和拟凸的概念，仿定理4的证明有以下结果。
定理5 若是伪凸函数，是可微拟凸函数，可行点x*满足K-T条件，则x*是问题（1）的全局最优解。
定理条件还可以减弱为f在x*点伪凸，在点x*可微拟凸，则相应的结论成立。
对于既有等式约束又有不等式约束的一般数学规划问题（8）：
（8）
只需令，然后考虑
便会得到与定理2、3的相应结果，下面仅叙述相应的K-T条件。
定理6（K-T必要条件） 设x*是问题（8）的可行解，可微，再假设和线性无关，如果是局部最优解,则存在
，使得
（9）
若问题是凸规划则亦可证K-T条件是充分的。
可把Botsko改进条件用于(1),有结果:
定理7假定于上连续,且.如果条件
(10)
成立,其中,S是可行解域,则是问题(1)的严格局部最优解.
证明:由Taylor公式:
可有
(11)
当x,x(i) 且充分小时,由于的连续性,故有
=0,i=1,
从而(11)式右边第三项亦是的高阶无穷小,故(11)可写成
(12)
其中第二项由于假定,故其不是的高阶无穷小,且由于(10)成立,故必有
这说明是问题(1)的严格局部最优解,即在上述条件下,(10)是取极值的充分条件.
§2、可行方向法
最早的可行方向法是1960年由G、Zoutendijk提出的，现在可行方向法已发展成求解约束优化问题的一类重要方法。其基本思想是：在给定一个可行点xk之后，用某种办法确定一个改进的可行方向Sk，然后沿Sk求解一个有约束的线搜索问题，得极小点,令。若仍不是最优解，则重复上述步骤。各种不同的可行方向法的主要区别在于：选择可行方向Sk的策略不同，大体可分为三类：
1) 用求解一个线性规划问题来确定Sk，如Frank---Wolfe方法，Zoutendijk方法等。
2） 利用投影矩阵直接来构造一个改进可行方向Sk,如Rosen投影梯度法。
3） 利用既约梯度直接构造出一个改进的可行方向Sk,如Wolfe既约梯度法及其各种改进。
下面介绍其中的几种：
1°Frank—Wolfe方法
考虑非线性规划问题
（13）
其中A和B分别是阶矩阵，且B是行满秩的。
b和d分别是m和l维列向量，令
表可行域，假定在包含S的某个开集D上是连续可微的函数。
任取一初始可行点，在处以的一阶Taylor展开式作为的线性逼近函数：
求线性规划问题
的解显然等价于求解线性规划问题：
（14）
为了保证（11）有有限解，假设对于任意可行点，线性函数在S上有下界。令（14）的最优解为，下面分两种情形讨论。
1） 若，即也是（14）的最优解，则迭代停止。
2） 若，此时必有
则由第二章定理2，是在点的下降方向，又因，且S为凸集，故，从而是可行方向。因此，从出发，沿此方向进行一维搜索，即求
的最优解，令，则x1是x。与y。连线上的最小值，且，当足够小时有
得到x1之后，再于x1处线性逼近，重复上述步骤。
注意：（14）是线性的，K-T条件中不含x，但是不同的x因松紧性不同，故有别。即只有最优解xk才与（13）有相同的K-T条件。
关于F-W方法的收敛判别准则，有如下定理：
定理8 若(11)的最优解yk满足,则是原问题（13）的K-T点。
证：显然，此时是（14）的最优解，从而也必是(14)的K-T点，由（14）与（13）有相同的K-T条件，立即可知是（13）的一个K-T点。证毕。
F-W方法虽然收敛较慢，但由于迭代求解的每一线性子规划（14）都具有相同约束条件（即可行域相同），因此可用灵敏度分析的手段处理一系列子规划问题（相当于目标函数系数变化检验数变化）这样，效果还是较好的。
2° Zoutendijk可行方向法
对于问题（13）先介绍一个确定下降可行方向的充要条件：
定理9 设x。是（13）的可行解，在 x。点有，其中，
，则非0向量S0是点x。处的可行方向的充要条件是：
（15）
证明：（简单从略）
由第二章定理2知，为使S0又是下降方向，这需满足
- （16）
因此在一点x0的下降方向可通过解下列线性规划问题来求得
（17）
这里加约束是为了获得一个有限解，因若存在满足（15）和（16），则对任意亦满足这些条件，进而导致（17）目标函数无下界，无法确定有限解S.
在问题（17）中，由于S=0是可行解，故最优值必定小于或等于0；若小于0，则最优解即为下降可行方向；若等于0，则以下定理保证x0是K-T点。
定理10 在无约束问题中，设x0是可行解，且，其中，,，则x0为K-T点的充要条件是问题（17）的目标函数等于0。
证：注意到问题（13）是线性约束问题，依定义，x0为K-T点等价于存在向量和，使得
令向量于是
依Farkas定理，这个系统有解的充要条件是，，无解。即无解，这等价于问题（17）的最优目标函数值等于0。所以x0是K-T点的充要条件是（17）的最优值为0。 证毕。
求得第k步迭代的下降可行方向Sk后，其最优步长应满足
由此出发不难推出（定理9）步长可由如下有约束的一维搜索求得
其中
对于非线性约束问题（1），我们知道，如果
（18）
则S是下降可行方向。
为求满足（18）的S，可解如下线性规划问题
(19)
(19)是由Zoutendijk首先提出，后来由Topkis和Veino等加以修正的可行方向法，可证由这种算法产生的点列的任一聚点都是Frita-John点。然后再验证（10）式成立，即知其为最优解。其特点是在确定移动方向时，无论起作用约束和不起作用约束都用上了，从而不致于在达到不起作用约束边界时，会使方向发生突然的变化。
§3、Rosen投影梯度法
这是Rosen在1960年针对线性约束的优化问题（13）首先提出来的，后来他又将该法推广到非线性约束情况，现已成为求解非线性规划的一类重要的有效方法。
梯度投影法的基本思想是，当迭代点在可行域内部时，取为迭代方向，当作无约束情形处理，当点在可行域边界上而且负梯度指向可行域的外界时，就改变方向沿梯度在边界上的投影搜索，使之成为可行方向，下边就问题（13）进行讨论。
设x是问题（13）的一个可行解，且使，这里,，设f(x)在x点可微，行满秩，则
是对零空间之投影矩阵（）。这样，若是下降可行方向。事实上（），故S是下降方向。又因
即，由定理9，S又是可行方向。
定理11 设x是（13）的一个可行解，分解,，使得
，若行满秩，，f在x可微，且，令，相应地分解
① 若，则x是一个K-T点。
② 若，令，置，其中是由中去掉第j行后得到的矩阵，令
则S是一个改进的可行方向。
证,① 因 ，即
（20）
所以若，则由K-T条件知x为一个K-T点。
② 首先证明（用反证法）设，并令
，可得，由于
可写成，这里是的第j列,是去掉第j个分量后的向量，于是由（20）可得
（21）
从而
而。上式说明M的所有行向量线性相关，从而与M行满秩的假设相矛盾。这就证明了。又易见是投影矩阵，因此由，可知是一个下降方向。下面再证S是一个可行方向。首先注意到，因此，可见要证S是可行方向，只要证就够了。
用乘（21），并注意到，就有
由于是半正定的，而，所以上式成立意味着，即S为可行方向。 证毕。
从出发沿作一维搜索时，步长的确定与Zoutendijk的相同。
§4、既约梯度法
这种方法是1963年首先由Wolfe提出来的，当时是为了解决具有线性约束条件的非线性规划问题，1969年，由Abadie与Carpentier推广到解决非线性约束条件的问题，既约梯度法的基本思想是：利用约束条件将所考察问题中某些变量用其它一组独立变量来表示，如对线性约束，将非基变量当作独立变量，把基变量用非基变量表示，消去目标函数中的基变量，那么目标函数在低维（n－m维）空间中的负梯度方向便是原问题的一个下降方向，再考虑到可行性，就可确定一个下降可行方向。
线性约束情形
考察如下的线性约束优化问题
（22）
其中A为矩阵，Rank（A）＝m，，，。设连续可微，问题（22）的可行集的每一个顶点都是非退化的，即每个顶点x都有m个正分量。
定理12设x是问题（22）的一个可行解，使得，，其中，而基矩阵B是可逆矩阵，用I表示基变量指标集，令。
是按下述规则确定：
–
(23)
(24)
若，则S是一个改进的可行方向，而S＝0的充要条件是x为K－T点。
证明：先证S是可行方向，据第二章定理2知，S是一个可行方向，当且仅当AS＝0，且若，则。由（24）知：。若是基变量，则，若不是基变量，则由（23）式可知，当且仅当时可以是负的，于是若，则，所以S是一个可行方向。下面证是一个改进方向。
由（23）知，，当时，则或不全为0，再乘一个不为0的自然不为0，从而显然有，由此可知S是一个改进方向。
最后证S＝0的充要条件是x为K－T点。注意到，x为K－T点当且仅当存在向量和，使得，，。因为，且，所以当且仅当，代入上式，可得，再代回上式可得。因此K－T条件简化为和
（25）
但是由S定义（23）可知，S＝0的充要条件是及0=，由于，此即（25）。
证毕。
计算步骤
1°选定计算精度，初始点满足，，其中，B为m×m可逆矩阵，用表示对应于B中向量的指标集，令k＝0。
2°计算，有n－m个分量，称为既约梯度。对，令，若，计算结束，为K－T点，否则转3°。
3°令（保证），求解线性搜索问题，得最优解。
4°令，若，令，转2°。若。求出中使那些下标i，将它们从中除掉，换入中使值最大的那些j，得出新的及相应的B，N，令，转2°。
例1：用既约梯度法求解。
·
解：取初始可行点。。
第一次迭代，，，，，，，，，。所以，，，。
解线性搜索问题，得最优解。因此，。
第二次迭代。在点，与相应的B，N为，，而，，，，，，，，，，。
解线性搜索问题，得最优解。因此，。
第三次迭代。在点，因此，，，，，，，，故为K-T点，而最优值为。
非线性约束情形
考察如下的标准非线性约束优化问题
（26）
一般的非线性约束优化问题总可化为上述形式，因为当约束条件为不等式时，可以通过引入松弛变量变成为等式约束，当无界时，可视或为无穷。假定连续可微，与线性约束类似，对任一可行点x，假定满足如下条件：（1），（2）若用表示对应于B中向量的指标集，用表示对应于N中向量的指标集，则，（3）令，，为在x点的m×m非奇异矩阵，，，，我们称为的既约梯度。
广义既约梯度法（GRG）计算步骤如下：
1．给定计算精度，选取初始可行解，分解，使其满足条件（1）、（2）、（3），令k＝0。
2．计算既约梯度。，按下面公式计算的分量。若，或，令，；否则令，。
3．若，计算结束，为K－T点，否则转第4步。
4．解非线性方程组，其中是按下式确定的，试取步长，则
得，对选择新基B，使，满足（1）、（2）、（3），令，返回2。
由上述可见，用于非线性约束情况的广义既约梯度法（GRG），是比较复杂的，在实际计算时，还有许多细节需要很好解决，才能取得好的效果，但值得注意的是，1970年以来的实际计算说明，在非线性约束优化算法的比较性研究中，GRG是比较优秀的之一。
