第七章非线性规划.doc

《第七章非线性规划.doc》由会员分享，可在线阅读，更多相关《第七章非线性规划.doc（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、+第七章 非线性规划非线性规划(Nonlinear Programming，简记为NP)研究的对象是非线性函数的数值最优化问题，是运筹学的最重要分支之一，20世纪50年代形成一门学科，其理论和应用发展十分迅猛，随着计算机的发展，非线性规划应用越来越广泛，针对不同的问题提出了特别的算法，到目前为止还没有适合于各种非线性规划问题的一般算法，有待人们进一步研究.1 非线性规划基本概念一、引例例7.1 一容器由圆锥面和圆柱面围成. 表面积为，圆锥部分高为，和圆柱部分高之比为,为圆柱底圆半径.求使面积最大.解： 由条件 所以，数学模型为：s.t. 例7.2 某高校学生食堂用餐，拟购三种食品，馒头0.3元

2、/个，肉丸子1元/个，青菜0.6/碗.该学生的一顿饭支出不能够超过5元.问如何花费达到最满意？解： 设该学生买入馒头，肉丸子，青菜的数量分别为；个人的满意度函数即为效用函数为.于是数学模型为 s.t.为非负整数二、数学模型 称如下形式的数学模型为数学规划（Mathematical Programming 简称MP） （7.1）（MP） （7.2） （7.3）其中是维欧几里得空间中的向量（点），为目标函数，为约束条件.称满足约束条件的向量为（MP）问题的一个可行解，全体可行点组成的集合称为可行域.=如果均为线性函数，就是前面所学的线性规划问题(LP).如果至少有一个为非线性函数称为非线性规划问题

3、.由于等式约束等价于下列两个不等式约束 所以(MP)问题又可表示为 s.t. （7.4）三、数学基础1、线性代数知识考虑二次型，为维向量正定的二次型：若对于任意，有；半正定的二次型：若对于任意，有；负定的二次型：若对于任意，有；半负定的二次型：若对于任意，有；不定二次型：，有，又，有.二次型为正定的充要条件是它的矩阵的左上角各阶主子式都大于零.二次型为负定的充要条件是它的矩阵的左上角各阶主子式负正相间.2、分析数学知识（1）方向导数和梯度(二维为例)考虑函数，及方向梯度：；方向导数： 考虑等值线上一点梯度方向 即为法线方向.如果二次可微，称 为在点 处的Hesse矩阵.（2）多元函数泰勒公式：

4、若在点处的某个领域具有二阶连续偏导数，则有 四、最优解的类型 定义7.1 (MP)问题的一个可行点被称为整体极小点，如果对于任意的可行点，都有不等式成立.如果对于任意可行点均有，称点是的可行解集上的严格整体极小点.定义7.2 问题(MP)的一个可行点被称为一个局部极小点，如果存在一个正数使得对于所有满足关系式的可行点都有成立.如果对任意的可行点，存在一个正数使得对于所有满足关系式的可行点都有成立.则称是在上的一个局部严格极小点.显然整体极小点一定是局部极小点，反之不然.五、凸规划 定义7.3 集合被称为中的一个凸集，如果对于中任意两点和任一实数，点.几何解释：当一个集合是凸集时，连接此集合中任

5、意两点的线段也一定包含在此集合内，规定空集是凸集.定义7.4 凸函数：是凸集上的实值函数，如果对于中任意两点和任意实数有不等式成立.严格凸函数：是凸集上的实值函数，如果对于中任意两点，和任意实数，有不等式成立.定义7.5 是定义在凸集上的实值函数，如果是上凸函数，称是凹函数.定理7.1 设是凸集上的凸函数，则在中的任一局部极小点都是它的整体极小点.证明： 设是一局部极小点而非整体极小点，则必存在可行点(可行域).对任一，由于的凸性，有 当时，与充分接近，与是局部极小矛盾. 证毕.定义7.6 设有(MP)问题，若可行域是凸集，是上的凸函数，则称此规划问题为凸规划.定理7.2 凸规划的任一局部极小

6、解为整体极小解.六、非线性规划问题的求解方法 考虑(MP)问题： （7.5） 一般来说，MP问题难以求得整体极小点，只能求得局部极小点.以后我们说求(MP)问题，指的是求局部极小点.1、无约束极小化问题 （UMP） （7.6）这里是定义在上的一个实值函数定理7.3（一阶必要条件）如果是可微函数.是上述无约束问题（UMP）的一个局部极小点或局部极大点的必要条件是：.满足的点称为平稳点或驻点.定理7.4 设为定义在上的二阶连续可微函数，如果是的一个局部极小点，必有 这里表示在处的Hesse矩阵.证明：，根据在点处的展开式有 若，当充分小时，有 有.这和是的极小矛盾.定理7.5 设是定义在上的二阶连

7、续可微函数，如果点满足，而且存在 的一个邻域，则是的一个局部极小点.在高等数学中求解极值点方法先求出满足的点及不可导点.在这些点判断是否取得极小值.2、等式约束的极小化问题考虑 （7.7）定义7.7 如果在点处线性无关，则称点是此约束条件的一个正则点. Langrange乘子法：引进拉格朗日函数 其中被称为拉格朗日乘子向量.定理7.6 设是连续可微函数，是在可行集中的一个局部极小点.在是正则点的假定下必存在一个拉格朗日乘子向量，使得满足方程组 对等式约束，用拉格朗日乘子法求解出平稳点，判断是否极值点.用上述解析法求解无约束和等式约束极值问题的平稳点，再判断是否为极值点.该方法有一定的局限性：（

8、1）它们要求函数是连续的，可微的，实际问题中不一定满足这一条件； （2）上述求平稳点的方程组求解比较困难，有些解不出来； （3）实际问题中有大量的不等式约束.因此求解非线性规划应有更好的新方法.实际应用中一般用迭代法来求解非线性规划问题，即求近似最优解的方法.3、非线性规划问题的求解方法迭代法迭代法一般过程为：在(MP)问题的可行域内选择初始点，确定某一方向，使目标函数从出发，沿方向使目标函数值下降，即，有，进一步确定，使，令.如果已满足某终止条件，为近似最优解.否则，从出发找一个方向，确定步长，使，有.如此继续，将得到点列.显然有,即点列相对应的目标函数是一个单调下降的数列.当是有穷点列时，

9、希望最后一个点是(MP)问题的某种意义下的最优解.当为无穷点列时，它有极限点，其极限点是(MP)的某种意义下的最优解（此时称该方法是收敛的）.迭代法求解(MP)的注意点：该方法构造的点列，其极限点应是近似最优解，即该算法必须是收敛的.迭代法一般步骤：. 选取初始点，. 构造搜索方向. 根据方向确定. 令. 若已满足某终止条件，停止迭代，输出近似最优解.否则令，转向第步.计算终止条件在上述迭代中有：若满足某终止条件则停止计算，输出近似最优解.这里满足某终止条件即到达某精确度要求.常用的计算终止条件有以下几个：（1）自变量的改变量充分小时，或，停止计算.（2）当函数值的下降量充分小时，或，停止计算

10、.（3）在无约束最优化中，当函数梯度的模充分小时，停止计算.迭代法的关键： 如何构造每一轮的搜索方向 确定步长关于，前面是以产生的，也有些算法取为一个固定值，这要根据具体问题来确定.关于的选择，在无约束极值问题中只要是使目标函数值下降的方向就可以了，对于约束极值问题则必需为可行下降方向.定义7.8 设，若存在使， 则称向量是函数在点处的下降方向.定义7.9 设，若存在使得，称向量是点处关于的可行方向. 若一个向量既是目标函数在点处的下降方向，又是该点处关于可行域的可行方向，则称为函数在点处关于区域的可行下降方向.根据不同原理产生了不同的和的选择方法，就产生了各种算法.在以后的讨论中，一维极值的

11、优化问题是讨论求解步长.无约束极值中讨论的最速下降法，共轭方向法，坐标轮换法，牛顿法，变尺度法及有约束极值中讨论的可行方向法都是根据不同的原理选择得到的迭代算法.七、迭代算法的收敛性定义7.10 设有一算法A，若对任一初始点（可行点），通过A进行迭代时，或在有限步后停止得到满足要求的点；或得到一个无穷点列，它的任何一个聚点均是满足要求的点，则称此算法A具有全局收敛性.定义7.11 设（UMP）问题的目标函数，为对称半正定矩阵，若由算法A进行迭代时，不论初始点如何选择，必能在有限步后停止迭代，得到所要求的点，则称此算法A有二次有限终止性.定义7.12 设序列收敛于，定义满足的非负数的上确界为的收

12、敛级. 若序列的收敛级为，就称序列是级收敛的.若且就称序列是以收敛比线性收敛的.若或且就称序列是超线性收敛的.如何判别算法的收敛性和收敛速度问题本书不讨论.本书给出的算法中，最速下降法具有全局收敛性、是线性收敛的；改进牛顿法具有全局收敛性、二次有限终止性、是二阶线性收敛的；变尺度法和共轭方向法具有全局收敛性和二次有限终止性、是超线性收敛的；Zoutenddijk法不具有全局收敛性、改进的T-V 法具有全局收敛性；制约函数法具有全局收敛性.关于这些算法的收敛性的讨论和证明有兴趣的读者可参考其他文献.2 一维极值问题的优化方法前面讨论迭代算法时,从出发确定沿方向的步长是这样求解的这里,已知.所以,

13、若记,则为求解的过程.于是我们考虑如下形式的极值问题. (7.8) 为任意实数很显然可应用高等数学中学过的解析法,即令求出平稳点,但如前面所述如果该方程解不出来,怎么办?可用下述迭代算法0.618法.定义7.13 定义在上,若存在点当,有,当时,称在中为单峰函数(单谷函数).显然满足定义要求的点是在中的极小点.在中任选两点,且,根据的单峰性,若,则必然位于内,如果,则必然位于内.如果,则必然位于,记此区间为.如此继续,得闭区间套.显然，又.由闭区间套性质, 为极小值点.闭区间套的选择方法不同,求得的的快慢及求解过程的计算量是不一样的，有一个常用的方法是0.618法. 0.618法： 取 在中选

14、取和,求出和进入. 若,取,若已足够小,停止,否则进入.若,取,若已足够小,停止,否则进入.若,取,若已足够小,停止,否则进入. 取上一步中的为,显然有,令,求出,返回. 取上一步的为,则有,令,求出返回.设初始区间为，用0.618法，经过次迭代后的长度，只要充分大可以小于任何给定的正数.例7.3 用0.618法求解单峰区间为-3，5，解：，=-3，5=-3+0.3828=0.056 =0.115=-3+0.6188=1.944 =7.667由于 所以新的不定区间为， =-3，1.944由于-=4.9440.2:=0.056 :=0.115=-3+0.3824.944=-1.112 =-0.9

15、87如此反复得下表7-1：表7-1迭代换换1-350.0561.9440.1157.6672-31.944-1.1120.056-0.987-0.9874-1.8320.056-1.112-0.664-0.987-0.9876-1.832-0.664-1.1120.936-0.987-0.9967-1.112-0.664-0.936-0.840-0.996-0.9748-1.112-0.840-1.016-0.936-1.000-0.9969-1.112-0.936在进行8次迭代后,取中间值或作为近似最优解.显然真正极小点是-1.0.一维收索方法很多，如函数逼近法、牛顿法等可参考其他文献.3

16、无约束极值的优化方法考虑无约束最优化问题（） (7.9)前面已经讨论过,求解此无约束优化问题,可以求出平稳点及不可导点的方法.令,求出平稳点.如果是正定的,则是的严格局部最优解.若在上是凸函数,则是整体最优解.在求解这维方程组比较困难时，就用最优化算法迭代法.本节将介绍最速下降法,牛顿法,共轭方向法,坐标轮换法,变尺度法.这些算法就是用不同的方法来选择搜索方向而得到的.当然必须是下降方向.定理7.7 设，在点处可微,若存在,使,则向量是在处的下降方向.证明:可微(在处)，由泰勒展开式,有 时,有 是在点的下降方向. 证毕.一、最速下降法 最速下降法又称梯度法,选择负梯度方向作为目标函数值下降的

17、方向,是比较古老的一种算法，其它的方法是它的变形或受它的启发而得到的，因此它是最优化方法的基础. 基本思想:迭代法求解无约束最优化(5.9)问题的关键是求下降方向.显然最容易想到的是使目标函数值下降速度最快的方向.从当前点出发,什么方向是使下降速度最快呢? 由泰勒展开知: 略去的高阶无穷小项,取时,函数值下降最多.而为在处的梯度，所以下降方向取为负梯度方向时,目标函数值下降最快. 最速下降法:. 取初始点,允许误差,令. 计算. 若,停止，点为近似最优解.否则进入. 求 ,使. 令，返回例7.4 用最速下降法求解下列无约束优化问题 取初始点 终止误差 解：很显然，该问题的整体最优解为，令易验证

18、是正定的， 是整体最优解.下面用最速下降法求解 取由得 重复上述过程得 图7-1 从图7-1可知，随着迭代次数的增加，越来越接近与最优解，同时也看到，随着迭代次数的增加，收敛速度越来越慢.极小点附近沿着一种锯齿形前进，即产生“拉锯”现象：沿相互正交的方向小步拐进，趋于最优解的过程非常缓慢.这种现象怎样解释？如何克服？在求时，由于，求导得，是的极小点.故有，即，又 ，即或.也就是最速下降法相邻两个搜索方向是彼此正交的.因此最速下降法是局部下降最快，但不一定是整体下降最快的.在实际应用中一般开始几步用最速下降法，后来用下面介绍的牛顿法.这样两个算法结合起来，求解速度较快.二、牛顿法基本思想：考虑无

19、约束优化问题(5.9) 由前面的讨论知，若能解出方程组，求出平稳点，则可验证是否为极值点.由于难以求解.如果具有连续的二阶偏导数,则考虑用在点二阶泰勒展开式条件替代，即由 令即从出发，搜索方向为，步长恒为1，得到下一个迭代点.牛顿法： 选取初始点，精度 计算，如果，计算终止.否则计算，求出搜索方向. 令，返回.例7.5 考虑无约束问题试分别取初始点（1），（2）（3），取精度要求，用牛顿法求解.解： (1) 取 有 重复计算结果得表7-2. 为近似最优解.实际上，该问题最优解为表7-2迭代次数04.00006.082814.51568.449520.12731.338830.00030.329

20、8400 (2) 取,同上计算,得有，这一迭代结果收敛到的鞍点.(3) 取 , 即不可逆，所以无法求得点.牛顿法的主要缺点:（1） 该法的某次迭代反而使目标函数值增大(见上例).（2） 初始点距极小点较远时,产生的点列可能不收敛,还会出现的奇异情况.（3） 的逆矩阵计算量大.牛顿迭代法的主要优点: 当目标函数满足一定条件,初始点充分接近极小点时,由牛顿法产生的点列不仅能够收敛到,而且收敛速度非常快. 实际应用中常将最速下降法和牛顿法结合起来使用.牛顿法的改进: 上面介绍的牛顿法中,处的搜索方向为,步长恒为1.若通过一维搜索来取最优步长,可防止在迭代中步长恒为1时标目标函数值增大的可能. 改进的

21、牛顿法:. 取初始点,允许误差. 检验是否满足,若是,迭代停止,得到为近似最优解.否则进入. 令. 求,使. 令,令转.三、坐标轮换法既然求解非线性规划问题的迭代法是给出初始点,求出一个方向,根据确定步长,使，如果满足某精度要求则停止，否则继续找方向.显然构造出搜索方向有一定的困难，能否按既定的搜索方向寻找最优解,省去找搜索方向呢?在最速下降法中我们看到相邻两个搜索方向和是正交的.我们知道在维欧氏空间中坐标轴向量是正交的，可否选坐标轴向量为搜索方向为呢?回答是肯定的，这样我们得到了坐标轮换法.基本思想:从出发,取,沿进行一维搜索得到.若满足精度要求,则停止.否则取,.如此继续, 取，若满足精度

22、要求,则停止.否则令,如此反复连续,可以求出近似最优解.坐标轮换法的缺点是收敛速度较慢,搜索效率较低,但基本思想简单,沿坐标轴的方向进行搜索.四、共轭方向法和共轭梯度法共轭方向法是一类方法的总称,它原来是为求解目标函数为二次函数的问题而设计的.这类方法的特点是:方法中的搜索方向是与二次函数的系数矩阵有关的所谓共轭方向，用这类方法求解元二次函数的极小化问题最多进行次一维搜索便可以得到极小点.由于可微的非二次函数在极小点附近的性态近似于二次函数,因此这类方法也用于求可微的非二次函数的问题.定义7.14 设为对称正定矩阵,如果称维向量和关于共轭.定义7.15 设为中一组向量, 是一个对称正定矩阵.如

23、果,称为共轭向量组,也称它们为一组共轭方向.当(单位矩阵)时,为正交方向.定理7.8 若为矩阵共轭向量组,则它们必线性无关.证明: 若存在,使,则对任一,由 又, 线性无关. 证毕.由高等代数知识可知, 共轭向量组中最多包含个向量, 是向量的维数.反之,可以证明,由维空间的任一组基出发可以构造出一组共轭方向.前面我们已经讲述了坐标轮换法，在维欧几里德空间中, 是一组线性无关的正交向量.从出发,依次使用作为下降方向进行一维精确搜索来确定,重复进行得点列,最终求得满足精度要求的最优解.刚才我们引进了共轭向量组,又证明了它们的线性无关性,那么是否可以用这共轭向量组像坐标轮换法一样,从出发依次用作为下

24、降方向来确定,最终求得近似最优解?回答是肯定的.这个方法称为共轭方向法.共轭方向法适合任何可微凸函数,且对于二次函数极值特别有效.下面的定理告诉我们用共轭方向法求解二次函数的极值，经过次迭代就能求得最优解.定理7.9 设为对称正定矩阵,函数,又设为一组共轭向量组,且每个是(下面形成的)点处的下降方向.则由任一点出发,按如下迭代至多步后收敛,这里满足. 证明: 欲证至多步收敛,即证. 下证和正交. 又 和正交， 又线性无关. 是问题的最优解. 证毕. 共轭方向法具有二次有限终止性. 由于共轭方向组的取法有很大的随意性,用不同方式产生一组共轭方向就得到不同的共轭方向法.如果利用迭代点处的负梯度向量

25、为基础产生一组共轭方向,这样的方法叫共轭梯度法. 下面对二次函数讨论形成共轭梯度方向的一般方法,然后引到求解无约束化问题上. 任取初始点,若,取,从点沿方向进行一维搜索 ,求得. 令,若,则已获得最优解.否则，取,其中的选择要使和关于共轭，由,得 一般地,若已获得共轭方向和依次沿它们进行一维搜索的得到的点列,若,则最优解为,否则 为使和是共轭,可证 所以有 又和是共轭的.有，得 进一步可得 综合起来得 Fletcher-Reeves公式 （7.10）共轭梯度法： 选取初始点，给定终止误差. 计算，若,停止迭代，输出.否则进行. 取，令 求，令 计算，若，停止迭代，为最优解.否则转. 若，令，转

26、(已经完成一组共轭方向的迭代,进入下一轮)否则转 取,其中,令,转当是二次函数时上述共轭梯度法至多进行步可求得最优解.当不是二次函数,共轭梯度法也可以构造,但已不具有有限步收敛的性质，于是和坐标轮换法一样经过一轮迭代后,采用重新开始的技巧.上述共轭梯度法就是带有再开始技巧的F-R法.例7.6 用F-R法求下面问题 取初始点,终止误差为解:在例7.4中已得 , 最优解.五、变尺度法当初始点为的其极值点附近时牛顿法收敛速度很快，但缺点是需计算的逆矩阵，在实际问题中目标函数往往相当复杂，计算二阶导数的工作量或者太大或者不可能，在的维数很高时，计算逆矩阵也相当费事.如果能设法构造另一个矩阵，用它来逼近

27、二阶导数矩阵的逆矩阵则可避免上述问题.下面就来研究如何构造的近似矩阵.我们希望：每一步都能以现有的信息来确定下一个搜索方向，每做一次迭代，目标函数值均有所下降，这些近似矩阵最后应收敛于最优解处的海赛矩阵的逆矩阵.于是 当是非二次函数时，令 （7.11）称为拟牛顿条件.显然，我们构造出来的近似矩阵必须满足上述拟牛顿条件及递推性：，这里称为矫正矩阵.记有 .变尺度法即DEP法是由Davidon首先提出，后来又被Fletcher和Powell改进的算法.记 （7.12）容易验证满足拟牛顿条件，称上式为DEP公式.变尺度方法计算步骤：（） 给出初始点，允许误差.（） 若，停止，为近似最优解；否则转下一

28、步.（） 取（单位矩阵），.（）（） 求，使.（） 令（） 若，为最优解，停止；否则当时，令转（）.（即迭代一轮n次仍没求得最优解，以新的为起点重新开始一轮新的迭代）. .计算，令，转（）.4 约束极值的最优化方法考虑(MP)问题： （7.13）其中是向量函数.显然 于是（MP）问题可以写为： （7.14）一、积极约束设是（MP）问题（5.14）的一个可行解.对来说，在点有两种情况：或者，或者.时，则不在形成的边界上，称这一约束为的非积极约束；时，处于由这个约束条件形成的可行域边界上，当有变化时就不满足的条件，所以称为积极约束，记为：.定义7.16 设满足约束条件，如果，线性无关，则称点是约束

29、条件的一个正则点.二、可行方向、下降方向的代数条件前面我们已经给出可行方向和下降方向的定义，下面给出其代数条件.可行方向：设是（MP）问题（5.14）的可行域，,.若存在使得时有，称为点处的一个可行方向.由泰勒公式： 当为的积极约束时，有.只要足够小，和同号，于是当时有.当为的非积极约束时，有.由的连续性，当足够小时，由保号性知.所以只要，就可保证，于是为点处的一个可行方向.称， 为在点处是可行方向的代数条件.下降方向：设是（MP）问题的可行域，,.若存在使得时，有，称为点处的一个下降方向.由泰勒公式： .当足够小时，只要，有.称为在点处的一个下降方向的代数条件.三、可行下降方向设为（MP）问

30、题（5.14）的可行域，若存在，既是点处的下降方向又是可行方向，则称为点处的可行下降方向.定理7.10考虑非线性规划问题（5.14），在点处可微，若是局部极小点，则点处必不存在可行下降方向，即不存在同时满足： 证明：反证法，设局部极小点处存在可行下降方向，于是，当时有，又为可行方向当时，这与是局部极小点矛盾. 证毕.可行下降方向代数条件的几何意义：对于，由 ，即与该点处目标函数负梯度向量之间夹角为锐角.同理说明与该点处积极约束的梯度向量之间的夹角成锐角.因此，若，使得和及均为锐角，则为可行下降方向.四、KuhnTucker条件考虑： （7.15）一阶连续可微.设为上述（MP）问题的极小点，若是

31、可行域的内点，则约束条件为非积极约束，必满足.若是可行域的边界点：设是位于一个约束条件形成的边界上，设有，是局部极小点，则必有与同处一条直线上且方向相反.因为不然的话，在点处必可找一方向，它与及的夹角为锐角，于是为可行下降方向，于是不是极小点，矛盾.若与同处一条直线上且方向相反，则有，即： 成立.即：若是局部最优解，在处一阶连续可微，则必存在实数使 成立.若位于两个约束条件所形成的边界面上，即有,，此时必位于和所形成的夹角内，否则在点处必存在一个可行下降方向.即：若是局部最优解且和线性无关，则必可由和的正线性组合.上述分析进一步有：为处的积极约束，为正则点.增加松紧条件可得： 于是有 （5.1

32、6）五、KuhnTucker条件的证明Gordan引理：设是个维向量，则下面每个问题有且仅有一个有解. KuhnTucker定理：设是非线性规划问题（5.15）的局部极小点，都是一阶连续可微函数，为正则点，则必存在使： 成立.证明： 是非线性规划的局部极小点，由定理5.10知该点不存在可行下降方向，即不存在同时满足 由引理知必存在不全为零的数使.由于为正则点，线性无关必有.于是有.对，令有考虑模型(7.13)： KuhnTucker一阶必要条件：设都是连续可微函数，是（MP）问题（5.13）的一个局部极小点，且为正则点，则必有满足 （7.17）例5.7 求下面问题的KuhnTucker点 解：

33、写出问题的KT条件若，由（1）（2）（4）（5）得.与矛盾， .若有 显然是KT点六、Zoutendijk可行方向法前面我们讨论了（MP）问题(7.13)的KT必要条件，求解KT条件得到平稳点有较大的困难，和无约束问题一样用迭代法求解（MP）问题是必然的选择.由于无约束问题的可行域是，所以只要讨论下降方向就行了.在有约束问题中不仅要使为下降方向，还必须是可行方向.于是从一个可行点出发，沿任何可行下降方向得到下一个可行点的迭代法就是求解有约束问题的方法.Zoutendijk可行方向法最能够说明这类方法的思想.本书仅介绍zoutendijk可行方向法，另外还有既约梯度法、投影速度法、 Frank-

34、wolfe方法等读者可参考其他文献1、仅带线性约束的Zoutendijk可行方向法考虑非线性规划问题： （7.18）这里为一阶连续可微函数，是矩阵，是矩阵.和分别为m维和维向量，记的行向量为，设为可行点，非零向量为可行下降方向代数条件： 于是有Zoutendijk方法的思想就是求出满足上述不等式组的非零向量，他巧妙地将上述不等式组变成如下的线性规划问题： （7.19）显然，若是（5.19）的可行解，则（为正实数）也是可行解，从而求解出的可能是无界的.上述问题改进为： （5.20）显然=0是上述线性规划问题的可行解.于是其最优目标值必小于等于零.若目标函数值等于零，则无解，即不存在可行下降方向.

35、由Farkas定理知为KT点.如最优解使目标函数值为负，即，即满足可行下降方向的代数条件.于是为可行下降方向 .设为可行点，记x处不等式约束中的积极约束系数组成的矩阵为，余下的不等式约束系数矩阵为，有.于是，相应的代数条件变为： （5.21）Zoutendijk方法：（）给出初始可行点，令；（）对，找出的分解，.使；（）求解令为求得的最优解.若，则是KT点，否则为可行下降方向，转（）；（）记为的第i个行向量，；令.求，令，以令k=k+1转（）例7.8 求下列非线性规划问题 初始点.解：取，于是求解线性规划： 不是KT点，于是是可行下降方向.又，得 .对求解如此继续得表7-3： 表7-3迭代k0

36、12(0,0)0-6.94-7.16(-4，-6)3,422(1,1)-100所以是最优解.2、非线性约束的情况考虑： （7.22）为可行点x处的积极约束指标集，若非零向量满足： ，则是可行点x处的可行下降方向.等价于求不等式组中向量和实数 （7.23）使和的最大值极小化.求解该问题等价于： （7.24）求出线性规划问题的最优解，若，说明在点处不存在可行下降方向.在为正则点时，为KT点（利用Gordan引理证明）.若，则为可行下降方向.Zountendijk可行方向法：（） 非线性规划问题的每个可行点为正则点，取为初始点，.（），求解问题最优解为.若，为KT点；若，则为可行下降方向，转（）.（

37、） 求最优步长 令，转（）.Zoutendijk可行方向法简洁明了，但此方法不具有全局收敛性，由此方法产生的无穷点列，它的聚点可能不是问题的KT点.1972年Wolfe给出了如下一个反例： 这是一个凸规则，唯一最优解为.从初始点出发，用Zountendijk方法求解，得到的不收敛于.3、TopkisVeinoff的改进方法设是可行点，TopkisVeinoff用下式求解.七、制约函数法这类方法是将约束条件随同一个参数并入到目标函数而形成一个新的无约束问题.当参数变化时就得到了一系列无约束问题，用求解这一系列无约束问题而得到的解来逼近原有约束问题的解，也称这类方法为序列无约束极小化方法.1罚函数法它是将约束条件变成目标函数中的“惩罚项”，“惩罚”那些不在可行域中的点，所以又称为外点法.考虑：（7.25）其中是上的连续函数定义惩罚函数：,令 从函数的构造可看出：当是可行点时，.当不是可行点时，.当时，是一个很大的数，就不可能在处取得极小值.于是将原问题化为如下无约束极值问题： 考虑数列，.对每一个求上述无约束极小化问题，得到.显然，当很小时，就很大.要使取得极小值就必须使p(x)很小，这时就需和.即此时为可行域中的边界点，或接近可行域的边界点.这样就求出了原问题的近似解，.惩罚函数法迭代步骤：给出数列，.任取一初始点，令，允许误差. 以为初始点，求