最优化方法全部课件.ppt

《最优化方法全部课件.ppt》由会员分享，可在线阅读，更多相关《最优化方法全部课件.ppt（333页珍藏版）》请在金锄头文库上搜索。

1、开始开始 最优化方法（最优化课件研制组）退出退出主讲：张 京 最优化方法最优化方法 为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法是在第二次世界大战前后，在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。 最优化方法解决问题一般步骤： （1）提出需要进行最优化的问题，开始收集有关资料和数据； （2）建立求解最优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件； （3）分析模型，选择合适的最优化方法； （4）求解方程。一般通过编制程序在电子计算机上求得最优解； （5）最优解的验证和实施。 随着系统科学的发展和各个领域的需求，最优化方法不断地应用于经济、自然、军

2、事和社会研究的各个领域。 第第1 1章章 预备知识预备知识1.1 1.1 经典极值问题经典极值问题 1. 1. 例子例子， 2. 2. 数学模型数学模型 第一，第一，无约束极值问题无约束极值问题或或 解法：解方程组解法：解方程组 第二，仅含等式约束的极值问题第二，仅含等式约束的极值问题 或或 解法：解法：LagrangeLagrange乘子法乘子法1.2 1.2 实例实例 数数据据拟拟合合问问题题 原原料料切切割割问问题题 运运输输问问题题 营养配餐问题营养配餐问题 分配问题分配问题1.3 1.3 基本概念基本概念 1. 1. 最优化问题的向量表示法最优化问题的向量表示法 设设 则则（1） 以

3、向量为变量的实值函数以向量为变量的实值函数 定义向量间的序关系定义向量间的序关系(定义定义1.1)： 等于，小于等于，小于，严格小于，严格小于。由此。由此（2） 以向量为变量的实向量值函数以向量为变量的实向量值函数最优化问题的一般形式最优化问题的一般形式 （3） 2. 2. 最优化问题的分类最优化问题的分类 试验问题：用于检验、比较最优化试验问题：用于检验、比较最优化方法优劣的一方法优劣的一些最优化问题。些最优化问题。3. 术语术语目标函数目标函数等式约束等式约束 不等式约束不等式约束容许解（点）容许解（点） 容许集容许集 求解问题求解问题（3）是指：在）是指：在容许集容许集中找一点中找一点目

4、标函数目标函数在该点取极小值，即对于在该点取极小值，即对于容许集容许集中中的任的任，总有，总有 意一点意一点 最优点（极小点）最优点（极小点） 最优值最优值 最优解最优解严格极小点严格极小点局部局部 非严格极小点非严格极小点严格极小点严格极小点非严格极小点非严格极小点全局全局 ，使得使得 到目前为止，大多数最优化算法求到的都是到目前为止，大多数最优化算法求到的都是局部极小点。局部极小点。为了求得全局极小点，一种解决办法是，先求出所有的为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。局部极小点，然后再从中找出全局极小点。 4. 极大值问题与极小值问题的关系极

5、大值问题与极小值问题的关系 1.4 1.4 二维问题图解法二维问题图解法 二维二维极值极值问题有时可以用图解的方式进行求解，有问题有时可以用图解的方式进行求解，有明显的几何解释。明显的几何解释。 例例 求解求解 图解法的步骤：图解法的步骤：，显然；取取并画出相应的曲线（称之为等值线）并画出相应的曲线（称之为等值线）. . 确定极值点位置，并用以往所学方法求之。确定极值点位置，并用以往所学方法求之。 易知本题的极小值点易知本题的极小值点。 再复杂点的情形见再复杂点的情形见P13上的例上的例1.7。 虽然三维及以上的问题不便于在平面上画图，图解虽然三维及以上的问题不便于在平面上画图，图解法失效，但

6、仍有相应的等值面的概念，且等值面具有以法失效，但仍有相应的等值面的概念，且等值面具有以下性质：下性质：有不同函数值的等值面互不相交（因目标函数是单值有不同函数值的等值面互不相交（因目标函数是单值函数的缘故）；函数的缘故）；等值面不会在区域的内部中断，除了极值点所在的等等值面不会在区域的内部中断，除了极值点所在的等值面以外。这是由于目标函数是连续函数的缘故；值面以外。这是由于目标函数是连续函数的缘故；令令 等值面稠密的地方，目标函数值变化得比较快；等值等值面稠密的地方，目标函数值变化得比较快；等值 面稀疏的地方，目标函数值变化得比较慢；面稀疏的地方，目标函数值变化得比较慢；在极值点附近，等值面（

7、等值线）一般近似地呈现为在极值点附近，等值面（等值线）一般近似地呈现为同心椭球面族（椭圆线族）。同心椭球面族（椭圆线族）。1.5 1.5 梯度和梯度和HesseHesse矩阵矩阵本段讨论都基于对函数本段讨论都基于对函数以下及今后的讨论中还经常要用到以下一些向量的知识。以下及今后的讨论中还经常要用到以下一些向量的知识。可微的假定。可微的假定。 与。 记作记作。向量也常用希腊字母向量也常用希腊字母等表示。等表示。向量内积的向量内积的性质性质：) （对称性）；（对称性）；) （线性性）；（线性性）；) ,当且仅当当且仅当时时，（正定性）；（正定性）；向量的内积向量的内积 设设则则称为向量称为向量的内

8、积，的内积，其实，其实， 向量向量的长的长 单位向量单位向量 向量的夹角向量的夹角 ， 向量的向量的正交正交 （正交性正交性） 1.可微 定义定义1.7 1.7 设设. .如果存在如果存在维向量维向量对于可任意小的对于可任意小的维非零向量维非零向量，总有，总有在点在点那么称函数那么称函数处处可微。可微。 若令若令便得到（便得到（1.9）的等价形式）的等价形式 . （1.10） 2.梯度 定理定理1.1 若若在点在点处可微，则处可微，则在该点关于各个变量的一阶偏导数存在，并且在该点关于各个变量的一阶偏导数存在，并且 定义定义1.8 1.8 以函数以函数的的个偏导数为分量的向量个偏导数为分量的向量

9、称为称为在点在点处的梯度，记为处的梯度，记为。 梯度也称为函数梯度也称为函数关于变量关于变量于是，（于是，（1.10）可写为）可写为这个公式与一元函数展开到两项的这个公式与一元函数展开到两项的Taylor公式是相对的。公式是相对的。 梯度的性质梯度的性质： 当梯度当梯度连续时，连续时， 第一，若第一，若，则，则必垂直于必垂直于过过点点处的等值面；处的等值面；的一阶偏导数。 第二，梯度方向是函数具有最大变化率的方向。第二，梯度方向是函数具有最大变化率的方向。 下面以下面以为例来解释这个性质。为例来解释这个性质。 上图是该函数的等值线图。上图是该函数的等值线图。 今考虑一点今考虑一点，不妨取坐标为

10、，不妨取坐标为。设想有。设想有出发沿某个方向移动到了点出发沿某个方向移动到了点，其坐标，其坐标，那么目标函数值将产生如下变化量，那么目标函数值将产生如下变化量一动点从一动点从设为设为假定假定。试问：动点沿哪个方向移动会使。试问：动点沿哪个方向移动会使目标函数值有最多的下降或上升？目标函数值有最多的下降或上升？从图上看，这相当于问：在以点从图上看，这相当于问：在以点为圆心、以为圆心、以1 1为为半径半径的圆周上，哪一个点具有最大的或最小的目标函数值。的圆周上，哪一个点具有最大的或最小的目标函数值。 为了一般地描述函数为了一般地描述函数在点在点处沿处沿情况及变化速度，须引入上升方向和下降方向及方向

11、导数情况及变化速度，须引入上升方向和下降方向及方向导数的概念。的概念。方向的变化方向的变化函数函数在点在点处沿处沿方向的变化反映的是函数方向的变化反映的是函数在一条直线上的变化，空间中由一点在一条直线上的变化，空间中由一点和一方向和一方向所确定的直线方程为所确定的直线方程为 上升方向和下降方向上升方向和下降方向 设设是连续函数。是连续函数。 若存在若存在，对于，对于都有都有，则称，则称方向是方向是在点在点处的上升方向；若存在处的上升方向；若存在对于对于都有都有，则称，则称方向是方向是在点在点处的下降方向。处的下降方向。定义定义1.9 1.9 设设在点在点处可微，处可微，是非是非方向上的单位向量

12、。如果极限方向上的单位向量。如果极限零向量零向量存在，则称其为函数存在，则称其为函数在点在点处沿处沿方向的方向导数，方向的方向导数，。记作记作思考：思考：与的异同。的异同。 若若，则，则 方向是方向是在点在点处的上升方向；处的上升方向； 根据极限理论，根据极限理论，易见易见若若，则，则方向是方向是在点在点处的下降方向。处的下降方向。因此因此，方向导数的正负决定了函数值的升降方向导数的正负决定了函数值的升降。定理定理1.2 1.2 设设在点在点处可微，则处可微，则，其中其中是非零向量是非零向量方向上的单位向量。方向上的单位向量。定理定理1.2又表明：只要又表明：只要，则，则方向是方向是在点在点处

13、的上升方向；只要处的上升方向；只要，则，则方向是方向是在点在点处的下降方向。处的下降方向。 函数值升降的快慢则是由方向导数绝对值的大小决函数值升降的快慢则是由方向导数绝对值的大小决定的。绝对值越大，升或降的速度就越快；绝对值越小，定的。绝对值越大，升或降的速度就越快；绝对值越小，升或降的速度就越慢。这是因为升或降的速度就越慢。这是因为据此有据此有 ) 等号成立当且仅当等号成立当且仅当与与同方向或与同方向或与同方向同方向。且当。且当与同方向同方向时，时， 取到最大值取到最大值 。 当当与与同方向同方向时，时， 取到最小值取到最小值 ) 若若是锐角，则是锐角，则;若若是钝角，则是钝角，则。 因此，

14、方向导数又可以称为函数因此，方向导数又可以称为函数在点在点处沿处沿方向的变化率。方向的变化率。使函数值下降最快的方向称为最速下降方向。使函数值下降最快的方向称为最速下降方向。 最速下降方向为最速下降方向为例例1.8 P19 几个常用函数的梯度公式几个常用函数的梯度公式（1）若，则，则，即，即（2）（3）；（4）.；2. Hesse矩阵矩阵 问：函数问：函数关于变量关于变量的二阶导数又是什么？的二阶导数又是什么？ 先来看什么是向量值函数的可微。先来看什么是向量值函数的可微。 定义定义1.11 设设。 若若的所有分量的所有分量 在在点点都都可微，则称向量值函数可微，则称向量值函数在点在点处可微处可

15、微。 定义表明，定义表明，在点在点处可微，则处可微，则成立，成立， 其用向量形式可简单地表示为其用向量形式可简单地表示为其中其中称为向量值函数称为向量值函数在点在点处的导数，处的导数， 而而称为向量值函数称为向量值函数在点在点处的处的JacobiJacobi矩阵。矩阵。设设具有二阶连续偏导数，且具有二阶连续偏导数，且则矩阵则矩阵称为函数称为函数关于变量关于变量的二阶导数，简记为的二阶导数，简记为。也称为多元实值也称为多元实值函数函数的的HesseHesse矩阵。矩阵。 例例1.9 P21 几个特殊的向量值函数的导数公式：几个特殊的向量值函数的导数公式：（1）；（2）；（3）；（4）设设，其中，

16、其中。则。则利用（利用（4），可得多元函数展开到三项的），可得多元函数展开到三项的Taylor公式公式（1.29）或或（1.31） 这个公式与一元函数展开到三项的这个公式与一元函数展开到三项的Taylor公式是相对应的。公式是相对应的。 多元函数的多元函数的Taylor展开式在最优化方法中十分重要，展开式在最优化方法中十分重要，许多方法及其收敛性的证明都是从它出发的。许多方法及其收敛性的证明都是从它出发的。 1. 凸集凸集1.6 凸函数与凸规划凸函数与凸规划 直观上，凸集就是空间中内部无直观上，凸集就是空间中内部无“洞洞”，边界又不向，边界又不向内凹的一些点的集合，其基本特征是该集合中任意两点

17、内凹的一些点的集合，其基本特征是该集合中任意两点间的线段仍然属于这个集合。间的线段仍然属于这个集合。非凸集非凸集 凸集凸集 空间中两点间的线段是由点的凸组合定义的。空间中两点间的线段是由点的凸组合定义的。定义定义1.12 设设是是中的中的个已知点。个已知点。 点点，若存在满足，若存在满足的非负实数的非负实数 对于对于 使得使得 ，则称，则称是是的一个凸组合。的一个凸组合。 又若又若是满足是满足的正实数，则称的正实数，则称 是是的一个严格凸组合。的一个严格凸组合。两点两点的的凸组合凸组合恰是连接两点的恰是连接两点的的的线段。线段。 线段，而严格凸组合是不含端点线段，而严格凸组合是不含端点 定义定

18、义1.13 1.13 设集合设集合。如果。如果中任意两点的中任意两点的，那么集合，那么集合称为凸集。称为凸集。任意凸组合仍然属于任意凸组合仍然属于规定：空集是凸集。规定：空集是凸集。 思考思考：空间中三个不同点的凸组合的集合，空间中：空间中三个不同点的凸组合的集合，空间中四个不同点的凸组合的集合四个不同点的凸组合的集合. 常见的凸集有超平面，直线，球常见的凸集有超平面，直线，球. 定理定理1.5 凸集的交集是凸集。凸集的交集是凸集。2. 凸函数凸函数定义定义1.16 设设，其中，其中为凸集。若对于为凸集。若对于中的任意互异两点中的任意互异两点和任意一对满足和任意一对满足的非负实数的非负实数，

19、总有总有则称则称是定义在凸集是定义在凸集上的凸函数。又若对于任意上的凸函数。又若对于任意的正实数的正实数，总有，总有一对满足一对满足则称则称是定义在凸集是定义在凸集上的严格凸函数。上的严格凸函数。若若是凸集是凸集上的（严格）凸函数，则称上的（严格）凸函数，则称是凸集是凸集上的（严格严格）凹函数凹函数。凸函数有以下重要性质。凸函数有以下重要性质。定理定理1.6 （1）若）若是定义在凸集是定义在凸集上的凸函数，上的凸函数， 是是也是也是上的凸函数。上的凸函数。任意的非负实数，则任意的非负实数，则（2）若）若是定义在凸集是定义在凸集上的凸函数，则上的凸函数，则也是也是上的凸函数。上的凸函数。 由定理

20、由定理1.6易见，定义在凸集上的任意有限个凸函数易见，定义在凸集上的任意有限个凸函数的任意非负组合仍然是凸函数。的任意非负组合仍然是凸函数。例例1.10定理定理1.7 设，其中，其中为非空凸集，若为非空凸集，若是凸函数，则对于任意实数是凸函数，则对于任意实数， 水平集水平集是凸集。是凸集。证证 若若是空集，则是凸集。以下设是空集，则是凸集。以下设非空。任取非空。任取，则，则 。又设。又设但但，根据，根据的凸性，必有的凸性，必有即即。因此，。因此，是凸集。是凸集。 判断一个函数是否为凸函数，一般说来，是比较困判断一个函数是否为凸函数，一般说来，是比较困难的。但当函数可微时，有以下几个判定定理。难

21、的。但当函数可微时，有以下几个判定定理。定理定理1.7 设设定理定理1.8 设设是可微函数，其中是可微函数，其中为为凸集。则凸集。则) 为凸函数的充要条件是对于为凸函数的充要条件是对于中的任意两点中的任意两点，都有，都有) 为严格凸函数的充要条件是对于为严格凸函数的充要条件是对于中的任意中的任意都有都有两个互异点两个互异点 定理定理1.8有明显直观的几何解释。有明显直观的几何解释。可微函数为凸函数的充要条件是在其可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面（切定义域凸集中任一点处的切平面（切线）都不在曲面（曲线）的上方。右线）都不在曲面（曲线）的上方。右图画出了一维的情形。图画

22、出了一维的情形。 定理定理1.9 设设是二次可微函数，是二次可微函数， 为非为非空开凸集。空开凸集。 则则为为上凸函数的充要条件是上凸函数的充要条件是Hesse矩阵矩阵在在上处处半正定。上处处半正定。定理定理1.10 设设是二次可微函数，是二次可微函数， 为非为非空凸集，空凸集， 若若的的Hesse矩阵矩阵在在上处处正定，则上处处正定，则是是上的严格凸函数。上的严格凸函数。这个命题的逆命题不真这个命题的逆命题不真。 例如，例如，在在上为严格凸函数，上为严格凸函数，在在处是处是半正定的。半正定的。但是它的但是它的Hesse矩阵矩阵3. 凸规划凸规划 设设是定义在非空凸集是定义在非空凸集上的凸函数

23、，上的凸函数，则形式为则形式为（1.36）的最优化问题称为凸规划问题，简称凸规划。换言之，的最优化问题称为凸规划问题，简称凸规划。换言之，定义在凸集上的凸函数的极小化问题是凸规划问题。定义在凸集上的凸函数的极小化问题是凸规划问题。若若都是都是上的凹函数，上的凹函数，都是都是上的线性函数，容易验证集合上的线性函数，容易验证集合是凸集。在这种情况下，凸规划（是凸集。在这种情况下，凸规划（1.36）可以表示成如）可以表示成如下形式下形式（1.37） 下面的定理指出了凸规划的一些重要性质。下面的定理指出了凸规划的一些重要性质。定理定理1.11 设设是凸规划（是凸规划（1.36）的局部极小点。则）的局部

24、极小点。则i）是（是（1.36）的全局极小点；）的全局极小点；ii）当）当是严格凸函数时，是严格凸函数时， 是（是（1.36）的唯一极小点；）的唯一极小点；iii）（）（1.36）的全部极小点的集合是凸集。）的全部极小点的集合是凸集。定理定理1.12 设设是可微凸函数，是可微凸函数，是非空是非空。 凸集，凸集，则则是凸规划（是凸规划（1.36）的极小点的）的极小点的充要中任意一点中任意一点，总有，总有。条件是，对于条件是，对于 定理定理1.12表明，凸规划（表明，凸规划（1.36）在最优点处的任何）在最优点处的任何容许方向（定义容许方向（定义4.3）都不是下降方向。）都不是下降方向。 推论推论

25、1.13 设设是可微凸函数，是可微凸函数， 是非空是非空凸集，凸集，。若。若使得使得，则，则是凸规划（是凸规划（1.36）的全局极小点。）的全局极小点。4. 二次函数与二次规划二次函数与二次规划函数函数（1.38） 称为称为元二次函数，其中元二次函数，其中是对称矩阵。若是对称矩阵。若是正定的，则（是正定的，则（1.38）称为正定）称为正定二次函数二次函数。， ， 注意到注意到， 于是由定理于是由定理1.10得知：正定二次得知：正定二次函数是严格凸函数。在最优化算法构造中，正定二次函数函数是严格凸函数。在最优化算法构造中，正定二次函数起着特殊的作用，本书的许多章节都要涉及它。起着特殊的作用，本书

26、的许多章节都要涉及它。形式为形式为（1.39） 的最优化问题称为二次规划问题，简称二次规划。若的最优化问题称为二次规划问题，简称二次规划。若 是半正定的或正定的，则（是半正定的或正定的，则（1.39）称为二次凸规划。）称为二次凸规划。定理定理1.14 一个一个 对称矩阵对称矩阵 为正定矩阵的充为正定矩阵的充要条件是条件是 的各阶主子式皆大于零。的各阶主子式皆大于零。 开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京1.7 极小点的判定条件极小点的判定条件函数函数 在局部极小点满足什么条件？反之，满足在局部极小点满足什么条件？反之，满足什么条件

27、的点是什么条件的点是 的局部极小点？的局部极小点？定理定理1.15 设设具有一具有一阶连续阶连续偏偏导导数，数，是是的内点。若的内点。若是是的局部极小点，的局部极小点，则则（1.40）注意，条件式（注意，条件式（1.40）不是充分的，仅仅是必要的。）不是充分的，仅仅是必要的。例如，例如，在点在点 处的梯度是处的梯度是 但是点但是点 是这个双曲抛物面的鞍点，而是这个双曲抛物面的鞍点，而不是极小点。不是极小点。 根据定理根据定理1.15与推论与推论1.13，容易得到凸规划问题全局极小容易得到凸规划问题全局极小点的一个一阶充分且必要条件。点的一个一阶充分且必要条件。推论推论1.16 设设 是可微凸函

28、数，是可微凸函数， 是非空开凸集，是非空开凸集， 。则。则 是（是（1.36）的全局极小点的）的全局极小点的充要条件是充要条件是.定义定义1.17 设设 可微，可微， 若若，则则称称为为的的驻驻点。点。驻点包括极大值点、极小值点和鞍点。驻点包括极大值点、极小值点和鞍点。定理定理1.17 设设具有二具有二阶连续阶连续偏偏导导数，数， ，且，且。若。若正定，正定，则则是是的的严严格局部极小点。格局部极小点。 一般来一般来说说，这这个定理个定理仅仅具有理具有理论论意意义义。因。因为对为对于复于复杂杂的目的目标标函数，函数，Hesse矩矩阵阵不易求得，其正定性也很不易求得，其正定性也很难难判定。判定。

29、定理定理1.18 设设具有二具有二阶连续阶连续偏偏导导数，数，且且。 若存在若存在的的邻邻域域，使得，使得 对对于于，都半正定，都半正定，则则必是必是的局部极小点。的局部极小点。 利用上节和本节的定理不难说明下面的两个论断。利用上节和本节的定理不难说明下面的两个论断。i）对于正定二次函数）对于正定二次函数 ，是它的唯一极小点。是它的唯一极小点。 ii）若多元函数在极小点处的）若多元函数在极小点处的Hesse矩阵是正定的矩阵是正定的,则则在这个极小点附近其等值面近似地呈现为同心椭球面族。在这个极小点附近其等值面近似地呈现为同心椭球面族。推证如下：推证如下：i）首先求出二次函数的驻点。令）首先求出

30、二次函数的驻点。令因因为为是正定矩是正定矩阵阵，所以解出唯一，所以解出唯一驻驻点点为为（1.41）因此根据推论因此根据推论1.13可以断定，可以断定， 是唯一的极小点。是唯一的极小点。 ii）设设是多元函数的极小点，是多元函数的极小点， 并并设设是充分是充分的一个等的一个等值值面，面， 靠近极小点靠近极小点即即充分小。充分小。 把把在点在点处处按按Taylor公式展开，得到公式展开，得到上式右端第二上式右端第二项项因因为为是极小点而消失，再略去是极小点而消失，再略去第四第四项项，那么二次曲面，那么二次曲面（1.42）就是等就是等值值面面的近似曲面。的近似曲面。按假按假设设，是正定的，因此，是正

31、定的，因此，为为中心的中心的椭椭球面球面（1.42）是以）是以方程。方程。这这正是我正是我们们所要所要说说明的。明的。1. 下降迭代算法下降迭代算法1.8 算法及有关概念算法及有关概念在集合在集合上的迭代算法是指：开始，上的迭代算法是指：开始，选选定一个初始点定一个初始点 ，置，置。然后按某种。然后按某种规则规则，把第，把第 次迭代点次迭代点映射映射为为新的一点新的一点 ，记为记为，并置，并置这这称称为为完成了第完成了第次迭代。次迭代。 这这个个过过程无限地程无限地进进行下去，行下去，。因此，。因此，规则规则称称为为算法。算法。 就会产生一个点列就会产生一个点列若点列若点列收收敛敛于于，则则称

32、算法称算法在在上是收上是收敛敛的；的； 否否则则，称算法，称算法在在上是上是发发散的。特散的。特别别地地 ，当，当 问题（问题（1.6）的容许集时，若除满足计算终止准则的迭代点）的容许集时，若除满足计算终止准则的迭代点是最优化是最优化外，对于每个外，对于每个，都有，都有，则则称称为为下降迭代下降迭代 许多最优化方法都采用将多维问题转化为一维问题的许多最优化方法都采用将多维问题转化为一维问题的处理方式。下面以处理方式。下面以无约束问题无约束问题为例，说明采用这种方式时为例，说明采用这种方式时的下降算法的基本迭代格式。的下降算法的基本迭代格式。设设第第次迭代点次迭代点已求得。若它不已求得。若它不满

33、满足足终终止准止准则则，。对对于可微目于可微目标标函数，即函数，即那么在该点必存在下降方向那么在该点必存在下降方向是满足是满足的的。按某种。按某种规则选规则选取一个取一个，例如，例如 ，再沿，再沿这这个方向适当地前个方向适当地前进进一步，即在直一步，即在直线线 上确定一个新点上确定一个新点 ，使得，使得 这这就完成了第就完成了第迭代。上式中的迭代。上式中的称称为为搜索方向，搜索方向，称称为为步步长长因子。因子。 不不过过，计计算机只能算机只能进进行有限次迭代。因此，一般行有限次迭代。因此，一般说说来，来，数数值计值计算不能求到精确解，而只能得到近似解。当迭代点算不能求到精确解，而只能得到近似解

34、。当迭代点满满足事先足事先给给定的精度要求定的精度要求时时，就，就终终止止计计算，并把算，并把这这个迭代个迭代点当作点当作问题问题的最的最优优解。解。在上数述迭代在上数述迭代过过程中，有两个程中，有两个规则规则需要确定：一个是需要确定：一个是的的选选取取规则规则；一个是步；一个是步长长因子因子的的选选取取规则规则。下降方向下降方向不同的规则对应着不同的最优化方法。不同的规则对应着不同的最优化方法。综上所述，无约束问题下降算法的基本迭代格式如下：综上所述，无约束问题下降算法的基本迭代格式如下：选选定初始点定初始点，置，置。按某种按某种规则规则确定下降方向确定下降方向。按某种按某种规则规则确定确定

35、，使得，使得 置置。判定判定是否是否满满足足终终止准止准则则。若。若满满足，足， 则则打印打印和和；否；否则则，置，置转转。 算法流程图见算法流程图见P34图图1-18。2. 直线搜索及其性质直线搜索及其性质在搜索方向在搜索方向已已经经确定的前提下，确定的前提下，选选取步取步长长因子的因子的方法有多种。例如，取步长因子为某个常数。但在实际计方法有多种。例如，取步长因子为某个常数。但在实际计算中，最常用的方法是直线搜索（又称一维搜索），算中，最常用的方法是直线搜索（又称一维搜索）， 即即选选取取，使得，使得（1.43） 按这种方法确定的步长因子称为最优步长因子。这种按这种方法确定的步长因子称为最

36、优步长因子。这种选取方法是很自然的。既然下降方向已经确定，就应该沿选取方法是很自然的。既然下降方向已经确定，就应该沿这个方向找到使目标函数取极小值的点。这个方向找到使目标函数取极小值的点。 2. 直线搜索及其性质直线搜索及其性质在搜索方向在搜索方向已已经经确定的前提下，确定的前提下，选选取步取步长长因子的因子的方法有多种。例如，取步长因子为某个常数。但在实际计方法有多种。例如，取步长因子为某个常数。但在实际计算中，最常用的方法是直线搜索（又称一维搜索），算中，最常用的方法是直线搜索（又称一维搜索）， 即即选选取取，使得，使得（1.43） 按这种方法确定的步长因子称为最优步长因子。这种按这种方法

37、确定的步长因子称为最优步长因子。这种选取方法是很自然的。既然下降方向已经确定，就应该沿选取方法是很自然的。既然下降方向已经确定，就应该沿这个方向找到使目标函数取极小值的点。这个方向找到使目标函数取极小值的点。 同时这又是容易办到的，因为同时这又是容易办到的，因为 是以是以 为变量的一元函数。为变量的一元函数。 求一元函数极小点的迭代法称求一元函数极小点的迭代法称为为直直线线搜索或一搜索或一维维搜搜索。索。许许多最多最优优化方法都采用将多化方法都采用将多维问题转维问题转化化为为一一维问题维问题的的处处理技理技术术。因此可以。因此可以说说，一，一维维搜索是最搜索是最优优化方法的一个重化方法的一个重

38、要支柱。要支柱。这这种方法的种方法的优优点是，它使目点是，它使目标标函数函数值值在搜索方向在搜索方向上下降得最多；缺点是，上下降得最多；缺点是，计计算量算量较较大。在第大。在第3章的章的3.1节节中中将全面介将全面介绍绍直直线线搜索。搜索。为简便起见，今后用记号为简便起见，今后用记号（1.44）表示从点表示从点出出发发沿沿方向方向对对目目标标函数函数作直作直线线。在目。在目标标函数函数确定的条件下，确定的条件下， 搜索得到极小点搜索得到极小点（1.44）等价于）等价于（1.45）直线搜索的一个重要性质。直线搜索的一个重要性质。定理定理 1.19 设设目目标标函数函数具有一具有一阶连续阶连续偏偏

39、导导数。若数。若，则则证证 使用反证法。假设使用反证法。假设 ，则，则 或或（1.47）（1.48） （1.47）表明）表明是点是点处处的下降方向，（的下降方向，（1.48）表明）表明是点是点处处的下降方向，的下降方向， 这这都与都与相矛盾。相矛盾。 故必有故必有（1.46）的几何意义是明显的。）的几何意义是明显的。 若若是从点是从点出出发发沿沿方向方向对对目目标标函数函数搜索得到的极小点，搜索得到的极小点，则则（1.46）指出，梯度）指出，梯度搜索方向向量搜索方向向量正交。正交。 作直线作直线必与必与又因又因为为与目与目标标函数函数过过点点的等的等值值面（等直面（等直线线）正交，所以搜索方向

40、向量正交，所以搜索方向向量与与这这个等个等值值面（等直面（等直线线）在点）在点处处相切。相切。3. 计算终止准则计算终止准则设设某个算法某个算法产产生的点列生的点列收收敛敛于（于（1.6）的最）的最优优解解。 现现在的在的问题问题是：在是：在计计算机上算机上计计算算时时，计计算到哪一个算到哪一个迭代点才有把握地说它就是所求问题的（近似）最解？迭代点才有把握地说它就是所求问题的（近似）最解？显显然，当然，当小于小于预预先先给给定的定的误误差限差限时时就可以就可以就是所求的最就是所求的最优优解。解。 认为认为但事但事实实上上是未知的，因而是未知的，因而无法计算无法计算。不。不过过，由极限理，由极限

41、理论论知道，当知道，当 与与都很小都很小时时， 也必然很小。于是，在也必然很小。于是，在数值计算中，可以用数值计算中，可以用（1.51）作作为计为计算算终终止的一个判定条件，其中止的一个判定条件，其中是是预预先先给给定的定的计计算算终止的界限，今后称为终止限。终止的界限，今后称为终止限。但是，用（但是，用（1.51）作为终止准则是不可靠的，因为）作为终止准则是不可靠的，因为 很小并不能保证很小并不能保证 很小。很小。 下面图下面图1中画出了一条一元目标函数的曲线及其有关的点。中画出了一条一元目标函数的曲线及其有关的点。从图中可以看到，相邻两个迭代点从图中可以看到，相邻两个迭代点 和和已已经经很

42、很靠近了，靠近了， 但它但它们们距极小点距极小点却都很却都很远远，而且，而且这这两点的两点的目标函数值目标函数值和和还由极限理论知道，当还由极限理论知道，当 相差很大。相差很大。 很小时，很小时， 也必然很小。因此，如果加上也必然很小。因此，如果加上（1.52） 这个条件，那么可靠性就会加强。上图这个条件，那么可靠性就会加强。上图2指出了只采指出了只采用（用（1.52）也是不可靠的。虽然）也是不可靠的。虽然 与与 相差很小，可相差很小，可是相是相应应的两个迭代点的两个迭代点和和却相距很却相距很远远，它，它们们距距极极也很也很远远。 小点小点需要注意的是，实际应用中，由于需要注意的是，实际应用中

43、，由于 和和 所取的量所取的量 纲有时太大，这时如果仍然以（纲有时太大，这时如果仍然以（1.51）和（）和（1.52）作为终）作为终止准则就太严格了。结果要么是用更多的计算才能使得止准则就太严格了。结果要么是用更多的计算才能使得（1.51）和（）和（1.52）得到满足，而这是不划算的；要么是）得到满足，而这是不划算的；要么是永远不能满足。解决这个问题的办法是，永远不能满足。解决这个问题的办法是， 先先对对和和 作无量纲处理，然后再结合（作无量纲处理，然后再结合（1.51）和（）和（1.52），给出），给出（1.53）和和（1.54）作为终止准则。作为终止准则。 此外，有一此外，有一类类无无约约

44、束最束最优优化方法在求解化方法在求解过过程中利用了程中利用了梯度。由于梯度。由于 为极小点的必要条件是为极小点的必要条件是 。因此，。因此， 当当满满足足（1.55） 时，一般可以认为时，一般可以认为 就是所要求的最优解。由于条件不是就是所要求的最优解。由于条件不是充分的，所以单独以（充分的，所以单独以（1.55）作为终止准则也是不可靠的。）作为终止准则也是不可靠的。 最后的结论是：对于使用导数的最优化方法，可按书最后的结论是：对于使用导数的最优化方法，可按书上图所示的判别过程作为终止准则；对于不使用导数的最上图所示的判别过程作为终止准则；对于不使用导数的最优化方法，则只需把图中涉及优化方法，

45、则只需把图中涉及 的部分去掉。今后的部分去掉。今后 统称为统称为Himmelblau计算终止准则，简称计算终止准则，简称H终止准则。终止准则。例例1：已知：已知求求解：解：，例例2：用图解法求解：用图解法求解解：解： 画出目标函数画出目标函数的等值线；的等值线；画出等式约束画出等式约束的图形，它是一条抛物线；的图形，它是一条抛物线；画出不等式约束所代表的区域。画出不等式约束所代表的区域。容许集为抛物线的一段，最优解为目标函数的等容许集为抛物线的一段，最优解为目标函数的等值线与容许集的切点，即最优点满足方程值线与容许集的切点，即最优点满足方程公切线平行公切线平行轴，切点为轴，切点为代入得代入得解

46、得解得或或得切点得切点不在容许集上，最优点为不在容许集上，最优点为最优值点最优值点交点交点例例3：用图解法求解：用图解法求解画出目标函数画出目标函数的等值线；的等值线；画出等式约束画出等式约束解：解：的图形，它是一条抛物线；的图形，它是一条抛物线；画出不等式约束所代表的区域。画出不等式约束所代表的区域。容许集为抛物线的一段，最优解为抛物线的端容许集为抛物线的一段，最优解为抛物线的端点，即方程点，即方程的解的解最优值最优值目标函数的等值线与容许集的切点，即最优目标函数的等值线与容许集的切点，即最优点满足方程点满足方程切点切点点点不在容许集上不在容许集上.最优解最优解例例4：设目标函数为：设目标函

47、数为从点从点出发，沿出发，沿的方向的方向作直线搜索，试求搜索到的极小点作直线搜索，试求搜索到的极小点并验证并验证解：解：例例5：判别最优化问题是否为凸规划：判别最优化问题是否为凸规划解：解：正定正定并用图解法求出最优点。并用图解法求出最优点。 从图上可判别出容许集为淡绿色区域，此从图上可判别出容许集为淡绿色区域，此区域为凸集，故此最优化问题为凸规划。区域为凸集，故此最优化问题为凸规划。用解析方法也可证明容许集为凸集。用解析方法也可证明容许集为凸集。都为半平面，它们的交集为凸集，以下判别都为半平面，它们的交集为凸集，以下判别为凸函数。为凸函数。各阶主子式非负，各阶主子式非负，为凸函数。为凸函数。

48、为凸集。为凸集。即容许集为凸集。即容许集为凸集。用一阶导数判别用一阶导数判别 的凸性。的凸性。为凸函数。为凸函数。即容许集为凸集。即容许集为凸集。为凸集为凸集. 由图解法可求得局部极小点，它一定是此由图解法可求得局部极小点，它一定是此最优化问题的全局最优点。最优化问题的全局最优点。最优点满足条件最优点满足条件解得解得为全局最优点。为全局最优点。开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京 在最优化中，目标函数和约束函数皆为在最优化中，目标函数和约束函数皆为线性函数的优化问题称为线性规划（线性函数的优化问题称为线性规划（LP），），它是相对

49、简单的最优化问题。本章是有关线它是相对简单的最优化问题。本章是有关线性规划的理论与求解方法的内容。性规划的理论与求解方法的内容。第二章第二章 线性规划线性规划2.1 2.1 线线性性规规划的各种形式划的各种形式1. 标准形式和典范形式标准形式和典范形式 如下形式的线性规划如下形式的线性规划称为线性规划的标准形式。称为线性规划的标准形式。 其中各其中各称称为为价格系数，各价格系数，各采用向量矩阵表示法，标准形式可以简写为采用向量矩阵表示法，标准形式可以简写为。 （2.1）称为右端项。称为右端项。 （2.2） 在在进进行理行理论论分析分析时时，有，有时时需要把需要把表示成表示成这样这样，（，（2.

50、2）中的）中的又可写成又可写成若若中有中有个列向量可以合并成个列向量可以合并成为单为单位矩位矩阵阵，且，且 例如，如下线性规划例如，如下线性规划，此时（，此时（2.2）则称为线性规划的典范形式。）则称为线性规划的典范形式。 就呈就呈现为现为典范形式，因典范形式，因为为和和可合并可合并成单位矩阵。成单位矩阵。不失一般性，假定不失一般性，假定单单位矩位矩阵阵位于前位于前列，即典范列，即典范形式呈形式呈现为现为（2.3）其中其中。用向量矩阵表示法，那么（用向量矩阵表示法，那么（2.3）可简写成）可简写成（2.4）2. 2. 一般形式一般形式线性规划线性规划 （2.5） 3. 一般形式与标准形式的关系

51、一般形式与标准形式的关系（1）松弛变量）松弛变量考考虑虑“”约约束中的第束中的第个不等式个不等式（2.6） 引入非引入非负变负变量量，迫使，迫使使不等式约束（使不等式约束（2.6）变为等式约束（）变为等式约束（2.7）的非负变量）的非负变量 称为松弛变量。称为松弛变量。 （2）剩余变量）剩余变量考考虑虑“”约约束中的第束中的第个不等式个不等式（2.7） （2.8）引入非引入非负变负变量量，迫使，迫使引入非引入非负变负变量量，迫使，迫使使不等式约束（使不等式约束（2.8）变为等约束（）变为等约束（2.9）的非负变量）的非负变量（2.9）称为剩余变量。称为剩余变量。在引入在引入个松弛个松弛变变量、

52、量、 个剩余个剩余变变量后，量后，线线性性规规划划（2.5）可化成标准形式：）可化成标准形式：（2.10） 它含有它含有个个变变量、量、个等式个等式约约束。束。 注意，新引入注意，新引入变变量的价格系数全部量的价格系数全部设为设为零。因此，在零。因此，在（2.10）的目）的目标标函数中没有出函数中没有出现现新新变变量。量。 下面说明线性规划（下面说明线性规划（2.5）与其标准形式（）与其标准形式（2.10）是等）是等价的。价的。 首先，它们的容许点是一一对应的，且对应的容许点首先，它们的容许点是一一对应的，且对应的容许点的函数值相等。的函数值相等。因因为为若若 是（是（2.5）的一个容许点，那

53、么按）的一个容许点，那么按公式（公式（2.7）和（）和（2.9）引入非负的松弛变量和剩余变量）引入非负的松弛变量和剩余变量 后，显然后，显然 将是（将是（2.10）的）的容许点。反之亦然。故（容许点。反之亦然。故（2.5）的容许点）的容许点 与与（2.10）的容许点）的容许点 一一对应。一一对应。 又（又（2.5）与（）与（2.10）的目标函数相同，且都只是）的目标函数相同，且都只是 的函数，所以（的函数，所以（2.5）与（）与（2.10）所对应的容许点）所对应的容许点的函数值相等。的函数值相等。其次，若其次，若是（是（2.10）的最）的最优优点，它所点，它所对应对应的最的最优值为优值为，那么

54、，由前面的，那么，由前面的证明可知，其前证明可知，其前 个分量组成的向量个分量组成的向量 也一定也一定 （2.5）的最）的最优优点。反之亦然。点。反之亦然。 因此，线性规划（因此，线性规划（2.5）与其标准形式（）与其标准形式（2.10）是等价的。）是等价的。该结论表明，可以只讨论标准线性规划。该结论表明，可以只讨论标准线性规划。例例2.1 将线性规划将线性规划 化为标准形式，并用图解法求解原问题，给出标准形化为标准形式，并用图解法求解原问题，给出标准形式的解。式的解。解解 对对第第1个个约约束引入松弛束引入松弛变变量量，对对第第2个个约约束引入束引入。于是，。于是，该线该线性性规规划的划的标

55、标准形式准形式为为剩余剩余变变量量图解法求解原线性规划如下：图解法求解原线性规划如下：最最优优解解在直在直线线与与的交的交汇处汇处，即，即。相。相应应的的标标准形式的最准形式的最优优解解为为。（3）自由变量）自由变量 以上以上讨论讨论都考都考虑变虑变量的取量的取值值是非是非负负的（当的（当变变量的取量的取值值非正，那么它的非正，那么它的负变负变量的取量的取值值即是非即是非负负的）。的）。实际实际中，如中，如果某些果某些变变量没有量没有这这种种约约束，也就是束，也就是说说，某些，某些变变量可以任意量可以任意取取值值，那么，那么这这些些变变量称量称为为自由自由变变量。自由量。自由变变量可以通量可以

56、通过过以以下两种方法把它消除。下两种方法把它消除。例如，假若例如，假若是自由是自由变变量。量。第一种方法：引入两个第一种方法：引入两个非非负负变变量量和和，令，令（2.11） 将其代入到线性规划的目标函数和约束函数中，自由变量将其代入到线性规划的目标函数和约束函数中，自由变量 就消除了。注意，求出新线性规划的最优点后，再利用就消除了。注意，求出新线性规划的最优点后，再利用（2.11）便可以定出）便可以定出 。 第二种方法：取一个包含第二种方法：取一个包含的等式的等式约约束，例如束，例如由此解出由此解出（2.12） 将此式代入到线性规划的目标函数和其他约束函数中，将此式代入到线性规划的目标函数和

57、其他约束函数中，自由变量自由变量 也消除了。求出新也消除了。求出新线线性性规规划的最划的最优优点后，点后，。利用（利用（2.12）再定出）再定出 第一种方法将增加变量的数目，导致问题的维数增大。第一种方法将增加变量的数目，导致问题的维数增大。第二种方法正好相反。第二种方法正好相反。2.2 2.2 基本定理基本定理考虑标准线性规划（考虑标准线性规划（2.2），即），即记容许集记容许集 。不妨假定不妨假定 ， 。 1. 极点与基本容许解极点与基本容许解定义定义2.2 有限个半空间的交称为凸多面体。有限个半空间的交称为凸多面体。半空间是凸集，故凸多面体是凸集。半空间是凸集，故凸多面体是凸集。边界为直

58、线或平面是多面体的几何特征。边界为直线或平面是多面体的几何特征。多面体多面体 凸多面体凸多面体定义定义2.3 有界的的凸多面体称为凸多胞形。有界的的凸多面体称为凸多胞形。凸多面体凸多面体 凸多胞形凸多胞形定理定理2.1 线线性性规规划（划（2.2）的容）的容许许集集是是凸多面体凸多面体。(2)凸集的极点凸集的极点与凸集相关的另一个重要概念是凸集的极点。与凸集相关的另一个重要概念是凸集的极点。定定义义2.5 若凸集若凸集中的某个点中的某个点不能表示不能表示为这为这个集合个集合中另外两个不同点的中另外两个不同点的严严格凸格凸组组合，即合，即则则称称为为凸集凸集的极点的极点。(3)基本容许解基本容许

59、解当（当（2.2）的容）的容许许解又是解又是“的基本解的基本解”时时，就，就称其为（称其为（2.2）的基本容许解。）的基本容许解。方程方程组组满满足足“基本基本”条件的的解称条件的的解称为为的基本解。的基本解。的基本解是如何定的基本解是如何定义义的呢？的呢？将将表示成向量形式表示成向量形式因因为为，故，故中必含有中必含有阶阶的可逆矩的可逆矩阵阵 ，称为，称为基。基基。基的每个列向量称为基向量，的每个列向量称为基向量， 的其余列向量称为的其余列向量称为非基向量。与基向量对应的变量称为基变量，与非基向量非基向量。与基向量对应的变量称为基变量，与非基向量对应的变量称为非基变量。若基是单位矩阵，则称为

60、标准对应的变量称为非基变量。若基是单位矩阵，则称为标准基。非基变量取值皆为基。非基变量取值皆为0的的 解称为基本解。满足解称为基本解。满足 的基本解称的基本解称为线为线性性规规划（划（2.2）关于基）关于基的的基本基本容容许许解解。不失一般性，设不失一般性，设 则则 令令 。若。若 ，得基本解，得基本解 么么该该基本解是关于基基本解是关于基的基本容的基本容许许解。解。 ，那，那例例2.3 P48 定义定义2.10 基变量取值皆不为基变量取值皆不为0的的基本解基本解称为非退化的，称为非退化的，否则称为退化的；若（否则称为退化的；若（2.2）的所有基本容许解都是非退）的所有基本容许解都是非退化的，

61、则化的，则线性规划线性规划（2.2）称为非退化的，否则称为退化）称为非退化的，否则称为退化的。的。例例2.4 P49(3)(3)基本容基本容许许解与极点的关系解与极点的关系引理引理2.2 设设 ，。则。则 是基本容是基本容许许解解 的正分量所对应的的正分量所对应的 的列向量线性的列向量线性 无关。无关。定理定理2.3 设设,则则是（是（2.2）的基本容）的基本容许许解解是是的极点。的极点。从几何角度讲，例从几何角度讲，例2.3中的约束条件中的约束条件 表示空间一条直线在第一象限中的直线段部分。表示空间一条直线在第一象限中的直线段部分。如图所示：如图所示：红线部分为容许集红线部分为容许集 。有两

62、个极点有两个极点 和和 它们恰恰是两个基本容许解。它们恰恰是两个基本容许解。 例例2.4如图所示：如图所示： 有两个极点有两个极点 和和 推论推论2.4 容许集容许集 的极点个数有限。的极点个数有限。 2. 线性规划基本定理线性规划基本定理引理引理2.5 设设.不妨不妨设设 且且 线线性相关。那么一定存在最多有性相关。那么一定存在最多有个正个正分量的容分量的容许许解。解。定理定理2.7 线线性性规规划（划（2.2）若有容）若有容许许解，解，则则必有基本必有基本容容许许解。解。 定理定理2.8 线线性性规规划（划（2.2）若有最）若有最优优解，解，则则必有最必有最优优基本容基本容许许解。解。从几

63、何上看，解从几何上看，解线线性性规规划存在以下几种可能情形：划存在以下几种可能情形：唯一解唯一解 无无穷穷多解多解 解无界解无界 无解无解2.32.3 单纯单纯形法形法由前述知，（由前述知，（2.2）的容）的容许许集集 是凸多面体，是凸多面体， 中的中的 极点个数有限。（极点个数有限。（2.2）若有容许解，则必有基本容许解；）若有容许解，则必有基本容许解；若有最优解，则必有最优基本容许解。据此，对于线性规若有最优解，则必有最优基本容许解。据此，对于线性规划，我们只关心基本容许解即可。因此，一个显而易见的划，我们只关心基本容许解即可。因此，一个显而易见的求解方法是求出全部基本容许解（极点），比较

64、目标函数求解方法是求出全部基本容许解（极点），比较目标函数值就能确定最优解。可是，当值就能确定最优解。可是，当 数值较大时，这种数值较大时，这种 法的计算量相当大，逆矩阵也不易求。法的计算量相当大，逆矩阵也不易求。Dantzig给出的单给出的单纯形法基本上解决了这个问题。纯形法基本上解决了这个问题。单纯形法的基本思想单纯形法的基本思想是：是：首先找到（求出）一个极点（基本容许解）首先找到（求出）一个极点（基本容许解） ，并依据，并依据最最优性准则判断其最优性，如非最优，则沿凸多面体优性准则判断其最优性，如非最优，则沿凸多面体 条条棱找到（迭代到）棱找到（迭代到） 的一的一使目标值降低（不找比使

65、目标值降低（不找比 的）的下一个极点（基本容许解）的）的下一个极点（基本容许解） 的目标值高的目标值高数是有限的，所以在一定的条件下，总可以找到（迭代到）数是有限的，所以在一定的条件下，总可以找到（迭代到），。因为极点个。因为极点个最优极点（最优基本容许解）或者说明解无界。最优极点（最优基本容许解）或者说明解无界。 如图所示。如图所示。 Dantzig单纯形法的单纯形法的思思想涉及以下三个具体问题：想涉及以下三个具体问题：有最优点有最优点 解无界解无界一、初始基本容许解的产生；一、初始基本容许解的产生；二、最优性准则；二、最优性准则；三、基本容许解的改进。三、基本容许解的改进。1. 最优性准则

66、最优性准则考虑标准线性规划考虑标准线性规划（2.21）设设为为容容许许基。基。 并不妨设并不妨设 ,。将（将（2.21）改写为）改写为（2.22）令令，得关于，得关于的基本容的基本容许许解解 目标函数值目标函数值 设设 为任一容许解，则由（为任一容许解，则由（2.22）解出）解出代入目标函数中得代入目标函数中得令令，于是，于是（2.26）故故 .因因为为，因此，只要，因此，只要，必有，必有由此得到判断基本容由此得到判断基本容许许解是最解是最优优解的一个充分条件。解的一个充分条件。定义定义2.11 在标准线性规划（在标准线性规划（2.21）中，设）中，设 是一个是一个基，则基，则 称称为变为变量

67、量关于基关于基的的判判别别数数。判判别别数的向量形式数的向量形式为为易知易知。 定理定理2.9（线线性性规规划最划最优优性准性准则则） 在在标标准准线线性性规规划划（2.21）中，）中，设设 是容许基。若所有变量关于基是容许基。若所有变量关于基 的判别的判别数皆非正，则关于基数皆非正，则关于基 的基本容许解是最优解。的基本容许解是最优解。 定义定义2.12 在标准线性规划（在标准线性规划（2.21）中，若关于基）中，若关于基 基本容基本容许许解是最解是最优优解，解，则则称称是是最最优优基基。例例2.5 考虑标准线性规划考虑标准线性规划试分别求关于基试分别求关于基 和和 的基本解。若是的基本解。

68、若是容许解，则判别其最优性。容许解，则判别其最优性。解解 关于关于的基的基变变量取量取值值 故关于故关于的基本解的基本解 是基本容许解。计算是基本容许解。计算最最优优性准性准则则未未满满足，因此不能断定足，因此不能断定是否是最是否是最优优解。解。因此因此关于关于的基的基变变量取量取值值 故关于故关于的基本解的基本解 也是基本容许解。计算也是基本容许解。计算最最优优性准性准则满则满足，因此断定足，因此断定是最是最优优解。解。2. 基本容许解的改进基本容许解的改进（1）Gauss-Jordan方程组方程组假定假定是（是（2.21）的一个基。由）的一个基。由得等价方程组得等价方程组记记 则（则（2.

69、28）可写成）可写成 （2.28）（2.29）（2.29）称）称为为关于基关于基的的Gauss-Jordan方程方程组组（G-J方程方程组组）。）。典范线性规划的主约束即是一个典范线性规划的主约束即是一个G-J方程组。方程组。G-J方程方程组组的性的性质质： ）一个基决定）一个基决定唯一的唯一的G-J方程组；方程组；）若）若是容是容许许基，基，则则由其由其G-J方程方程组组可得出关于可得出关于的基本容的基本容许许解解 ）在）在G-J方程组中方程组中,基变量的系数向量构成单位矩阵。基变量的系数向量构成单位矩阵。 性质性质）说明求新的基本容许解的过程实质上就是不）说明求新的基本容许解的过程实质上就

70、是不同基的同基的G-J方程组间的转化过程。这个转化过程很容易实方程组间的转化过程。这个转化过程很容易实现。现。设设是新基，是用非是新基，是用非基向量基向量 替替换换中的中的得到的矩得到的矩阵阵。 这时这时G-J方程组间的方程组间的转化过程就是要将非基变量转化过程就是要将非基变量的系数向量的系数向量变为单变为单位位向量向量（性（性质质）.要要实现这实现这个个过过程，程，则则必必须须有元素有元素，称称为为主元主元。转转化化过过程程显显示如下：示如下： 关于基关于基的的Gauss-Jordan方程方程组组 关于基关于基的的Gauss-Jordan方程组方程组为为保保证证解的解的改改进进，替，替换须满

71、换须满足以下两个条件：足以下两个条件：第一，第一，容容许许性条件性条件。即保。即保证证的的G-J方程方程组组的右端的右端项项非非负负的条件。的条件。第二，第二，下降性条件下降性条件。即保。即保证证的基本容的基本容许许解的解的目标函目标函的基本容的基本容许许解的目解的目标标函数函数值值的条件。的条件。数数值值小于小于i）容许性条件）容许性条件由由 ，即，即主元主元还还必必须为须为正正。结论结论是是：为为保保证证的的G-J方程方程组组的右端的右端项项非非负负， （2.36）主元主元 必须是满足必须是满足 的正数。的正数。 如果主元不存在，如果主元不存在，则线性规划解无界（定理则线性规划解无界（定理

72、2.12）。例例2.6 考考虑虑例例2.5中的中的线线性性规规划划 关于关于的的G-J方程方程组组试试把把和和分分别别引入基，求新的基本引入基，求新的基本容容许许解。解。）下降性条件）下降性条件新解新解。 中只有中只有其余分量皆其余分量皆为为0。于是，由（。于是，由（2.26）式得）式得（2.37）由于由于，所以只要，所以只要，则则特特别别当当时时，只要，只要，必有，必有结论结论是是：引入判：引入判别别数数为为正的正的变变量，将保量，将保证证的基本的基本的基本容的基本容许许解的目解的目标标函数函数值值。容容许许解的目解的目标标函数函数值值不大于不大于引理引理2.10定理定理2.11（单纯形法基

73、本定理）（单纯形法基本定理） 在标准线性规划在标准线性规划（2.21）中，假设：）中，假设：）是容是容许许基，关于基，关于的基本容的基本容许许解解；是非退化的，即是非退化的，即）非基）非基变变量量的判的判别别数数；），是用公式（是用公式（2.36）确定的一个）确定的一个行行标标；）用）用替替换换中的中的，而其余基向量不，而其余基向量不变变，构成，构成。矩矩阵阵那么那么，是容是容许许基，且关于基，且关于的基本容的基本容许许解的解的目目标标函数函数值值小于关于小于关于的基本容的基本容许许解的目解的目标标函数函数值值。 定理定理2.12 在在标标准准线线性性规规划（划（2.21）中，假）中，假设设：

74、）是容是容许许基；基；）非基本）非基本变变量量的判的判别别数数；）。那么那么线线性性规规划（划（2.21）存在可以使目）存在可以使目标标函数函数值值任意减小的任意减小的容容许许解。解。（2）单纯形表）单纯形表 以上以上过过程都可以清晰地在一程都可以清晰地在一张张表表单纯单纯形表上形表上进进行，行，称之称之为为表上作表上作业业法。法。假假设设已知（容已知（容许许）基）基，那么关于，那么关于的信息全部反映在以下两个式子（的信息全部反映在以下两个式子（线线性性规规划的两个关划的两个关键键数学式）中，数学式）中，称之称之为为关于基关于基的的增广增广G-J方程方程组组。 增广增广G-J方程方程组组其其实

75、实可由可由线线性性规规划（划（2.21）的原始数）的原始数据据经经初等行初等行变换变换得到。原有得到。原有(2.45）式左乘）式左乘即得（即得（2.43）式，（）式，（2.43）式再左乘）式再左乘加到（加到（2.46）式上便得（）式上便得（2.44）式。）式。 隐隐去增广去增广G-J方程方程组组中的中的变变量和量和的系数向量，将的系数向量，将其余数据列成表其余数据列成表（2.51）称称为为关于基关于基的的单纯单纯形表形表。若。若是最是最优优基，基，则则称称为为最最优优表表。单纯单纯形表是增广形表是增广G-J方程方程组组的的简单简单表示。表示。表表称称为线为线性性规规划的划的准准备备表表。类类似

76、前面的推似前面的推导导，由准，由准备备表容易表容易导导出出单纯单纯形表形表 至此，至此，含有标准基的线性规划问题的求解彻底解决含有标准基的线性规划问题的求解彻底解决。归纳见（归纳见（3）。）。例例2.7 求解例求解例2.5中的中的线线性性规规划。划。P64-55（3）典范）典范线线性性规规划的解法划的解法考考虑虑典范典范线线性性规规划划是是标标准容准容许许基。基。 典范线性规划含有标准容许基，它的准备表既是单纯典范线性规划含有标准容许基，它的准备表既是单纯形表，因此单纯形法可以直接启动。形表，因此单纯形法可以直接启动。 算法算法2.1（单纯单纯形法）形法） P65单纯单纯形法本形法本质质上是求

77、解典范上是求解典范线线性性规规划的算法划的算法。 定理定理2.13 在使用单纯形法（算法在使用单纯形法（算法2.1）求解典范线性）求解典范线性规划时，若各次迭代出的基本容许解皆是非退化的，则算规划时，若各次迭代出的基本容许解皆是非退化的，则算法在有限步终止。法在有限步终止。 推推论论2.14 典范典范线线性性规规划或者存在最划或者存在最优优基本容基本容许许解，解，或者解无界。或者解无界。对于如下形式的线性规划对于如下形式的线性规划其中其中。先引入非。先引入非负变负变量量将其化将其化为为典范形式典范形式然后就可以启动单纯形法。然后就可以启动单纯形法。例例2.8 求解线性规划求解线性规划 P663

78、. 初始基本容许解的产生初始基本容许解的产生对于标准线性规划对于标准线性规划（2.54）引入引入个个人工人工变变量量 ，求解，求解辅助线性规划辅助线性规划一个典范线性规划一个典范线性规划（2.55） 其中其中。 显然显然（2.55）不可能无解）不可能无解。设设（2.55）的最）的最优值为优值为，显显然然。设设最最优优表表对应的对应的G-J方程组为方程组为（2.56）注意注意：与与等价。等价。（2.54）与（）与（2.55）的关系：）的关系： 若若，则则（2.54）无解；）无解； 若若，则则由（由（2.56）可得到（）可得到（2.54）的一个）的一个初始基本初始基本容容许许解。解。 以下以下讨论

79、讨论在在下下进进行。分两种情形：行。分两种情形： （1）在最）在最优优表中人工表中人工变变量已全部退出基量已全部退出基变变量（表量（表现为现为中不存在基向量）。中不存在基向量）。 这时这时，与，与等价的等价的中有了中有了标标准基，准基， 表明（表明（2.54）有了初始基本容许解，这时可以开始求解）有了初始基本容许解，这时可以开始求解（2.54）（见下面的）（见下面的4.（1）。）。即即（2）在最）在最优优表中表中至少至少还还有一个人工有一个人工变变量是量是基基变变量（表量（表中有基向量）。中有基向量）。 现现为为假假设设第第个人工个人工变变量量仍是基仍是基变变量，那么它的取量，那么它的取值为值

80、为 。因。因为为，所以，所以。考。考虑虑（2.56）的第）的第个方程个方程（2.58）以下分两种情形：以下分两种情形：）若）若 ，则则（2.58）实质实质上成上成为为的的第第个方程是多余方程，个方程是多余方程， 。这表明。这表明 从而从而的的第第个方程也多余。个方程也多余。 划去第划去第个方程，人工个方程，人工变变量量将将彻彻底消失。底消失。）若）若 至少有一个不至少有一个不为为0 ，不妨，不妨设设 以以为为主元在主元在最最优优表上表上进进行行换换基运算，人工基运算，人工变变量量就会从基变量中消失。就会从基变量中消失。 重复以上步骤，直到人工变量全部从基变量中消失，重复以上步骤，直到人工变量全

81、部从基变量中消失，最终的最终的G-J方程组为方程组为这时与这时与 等价的等价的 中也有了标准基，从而中也有了标准基，从而 （2.54）也有了初始基本容许解，于是可以开始求解）也有了初始基本容许解，于是可以开始求解（2.54）（见下面的）（见下面的4.（2）。）。4. 4. 标标准准线线性性规规划的解法划的解法 按按3.求出（求出（2.54）的初始基本容许解之后，接下来求）的初始基本容许解之后，接下来求解（解（2.54），与），与3.中的（中的（1）、（）、（2）对应，分别为）对应，分别为 （1）求解线性规划）求解线性规划（2）求解线性规划）求解线性规划总结：一般来说，解线性规划主要分为两大步：

82、总结：一般来说，解线性规划主要分为两大步： 第一步，化标准形（有时不需要）；第一步，化标准形（有时不需要）； 第二步，启动两阶段单纯形法（当标准形是典范线性第二步，启动两阶段单纯形法（当标准形是典范线性规划时，直接进入第二阶段）。规划时，直接进入第二阶段）。 例例 求解线性规划求解线性规划例例2.9 求解线性规划求解线性规划例例2.10 求解线性规划求解线性规划2.4 退化的处理退化的处理 在非退化假定下，单纯形法（算法在非退化假定下，单纯形法（算法2.1）具有有限终）具有有限终止性（定理止性（定理2.13）。）。取消非退化假定，情况会是怎么样取消非退化假定，情况会是怎么样？第一，算法第一，算

83、法2.1可能发生无限循环，求不到最优解；第二，可能发生无限循环，求不到最优解；第二，适当修改选主元的规则，则可以保证单纯形法仍具有有限适当修改选主元的规则，则可以保证单纯形法仍具有有限步终止性。步终止性。1. 选主元规则选主元规则 单纯形法的核心是换基运算，而换基运算的首要步骤单纯形法的核心是换基运算，而换基运算的首要步骤是选主元。选取主元列标的规则称为进基规则；选取主行是选主元。选取主元列标的规则称为进基规则；选取主行标的规则称为退基规则。进基规则和退基规则合称选主元标的规则称为退基规则。进基规则和退基规则合称选主元规则。选主元规则有多种多样，常用的进基规则有以下两规则。选主元规则有多种多样

84、，常用的进基规则有以下两种：种：）最大正判别数进基规则）最大正判别数进基规则）正判别数最小下标进基规则）正判别数最小下标进基规则 选取正判别数中最小的下标作为主元的列标。算法选取正判别数中最小的下标作为主元的列标。算法2.2和算法和算法2.3就采用这种进基规则。就采用这种进基规则。 常用的退基规则是常用的退基规则是最小行标最小行标退基规则。在使用公式退基规则。在使用公式（2.36）确定主元行标，若最小比值在多行上取得，则从）确定主元行标，若最小比值在多行上取得，则从中选取最小的行标作为主元的行标。中选取最小的行标作为主元的行标。 选取最大判别数的下标作为主元的列标。若同时有选取最大判别数的下标

85、作为主元的列标。若同时有多个等值的最大正判别数，则选取其中最小的下标为主元多个等值的最大正判别数，则选取其中最小的下标为主元的列标；的列标； 最大正判别数进基规则与最小行标退基规则合称最大正判别数进基规则与最小行标退基规则合称Dantzig规则。算法规则。算法2.1采用的就是这种规则。采用的就是这种规则。计算实践表计算实践表明明，在各种选主元规则中，在各种选主元规则中，Dantzig规则效果较好，在求规则效果较好，在求解同一线性规划问题时，迭代次数相对较少。它的缺点是，解同一线性规划问题时，迭代次数相对较少。它的缺点是，在求解退化问题时，算法可能产生无限循环，求不到最优在求解退化问题时，算法可

86、能产生无限循环，求不到最优解。解。 2. 避免循环的规则避免循环的规则这里介绍一种最简单的避免循环的规则这里介绍一种最简单的避免循环的规则Bland规则。规则。 Bland规则规则 设在单纯形法的迭代过程中，当前容许设在单纯形法的迭代过程中，当前容许基是基是 关于关于 的基容许解不是最优解，则的基容许解不是最优解，则主元列标和行标分别由如下两个规则确定：主元列标和行标分别由如下两个规则确定：）Bland进基规则进基规则 采用正判别数最小下标进基规则，即主元列标是采用正判别数最小下标进基规则，即主元列标是由此确定由此确定进进基。基。）Bland退基规则退基规则假定假定。设设又设又设则则主元行主元

87、行标标由式由式确定，由此确定确定，由此确定 退基。换句话说，在所有可能的退基。换句话说，在所有可能的退基退基 向量中，选取下标最小的向量退基。向量中，选取下标最小的向量退基。 Bland证明：使用带有证明：使用带有Bland规则的单纯形法求解典规则的单纯形法求解典范线性规划，不会发生基的循环。范线性规划，不会发生基的循环。2.5 修正单纯形法修正单纯形法修正单纯形法是计算机实现的单纯形法。修正单纯形法是计算机实现的单纯形法。注意到，包含全部信息的单纯形表注意到，包含全部信息的单纯形表中的数据中的数据完全由基完全由基 （实际实际是是）及原始数据决定。）及原始数据决定。可以可以就有一切。就有一切。

88、说有说有举例说明修正单纯形法的概貌。举例说明修正单纯形法的概貌。例如求解例如求解解解 建立单纯形表如下建立单纯形表如下开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京 第三章第三章第三章第三章 无约束最优化方法无约束最优化方法无约束最优化方法无约束最优化方法 从本章起，以后两章将讨论非线性规划问题。本章首从本章起，以后两章将讨论非线性规划问题。本章首先讨论无约束最优化问题，其一般形式为先讨论无约束最优化问题，其一般形式为（3.1） 其中其中 求解无约束问题的最优化方法可以分为两大类：一类求解无约束问题的最优化方法可以分为两大类：一类是根据目标

89、函数的梯度（即一阶导数），有时还要根据是根据目标函数的梯度（即一阶导数），有时还要根据Hesse矩阵（即二阶导数）提供的信息构造出来的方法矩阵（即二阶导数）提供的信息构造出来的方法导数方法。本章介绍其中的最速下降法、导数方法。本章介绍其中的最速下降法、Newton法、法、共轭梯度法和拟共轭梯度法和拟Newton法。另一类是不使用导数，仅仅法。另一类是不使用导数，仅仅利用目标函数值的信息构造出来的方法利用目标函数值的信息构造出来的方法直接方法。本直接方法。本章将介绍其中的步长加速法、方法加速法和单纯形替换法。章将介绍其中的步长加速法、方法加速法和单纯形替换法。两类方法各有利弊。前者收敛速度快，但

90、需要计算梯度，两类方法各有利弊。前者收敛速度快，但需要计算梯度，甚至需要计算甚至需要计算Hesse矩阵；后者不涉及导数，适应性强，矩阵；后者不涉及导数，适应性强，但收敛速度慢。一般的经验是，在可以求得目标函数导数但收敛速度慢。一般的经验是，在可以求得目标函数导数的情况下，尽可能使用导数方法。的情况下，尽可能使用导数方法。3.1 直线搜索直线搜索 直线搜索（一维搜索）是指求解如下一元函数极小化直线搜索（一维搜索）是指求解如下一元函数极小化问题问题（3.3） 的迭代方法，其中的迭代方法，其中。在微在微积积分中，解决分中，解决问题问题（3.3）的范）的范围围一般限于方程一般限于方程（3.4）可以直接

91、解出的情况。而这里介绍的直线搜索对可以直接解出的情况。而这里介绍的直线搜索对 严格的要求。当然，对于可以求出导数的情况，相应的求严格的要求。当然，对于可以求出导数的情况，相应的求解方法一般也会简单些。解方法一般也会简单些。不作不作直线搜索，理论上，分为精确的和不精确的。直线搜索，理论上，分为精确的和不精确的。 精确的直线搜索方法主要分为两类：一类为区间收缩精确的直线搜索方法主要分为两类：一类为区间收缩法，另一类为函数逼近法。本节将相应地介绍两种常用的法，另一类为函数逼近法。本节将相应地介绍两种常用的精确的直线搜索方法：适用于一般函数的黄金分割法和适精确的直线搜索方法：适用于一般函数的黄金分割法

92、和适用于一般连续函数的抛物线插值法。最后还将介绍实用的用于一般连续函数的抛物线插值法。最后还将介绍实用的不精确一维搜索技术。不精确一维搜索技术。 精确的直线搜索算法的实现通常是在所谓的搜索区间精确的直线搜索算法的实现通常是在所谓的搜索区间上进行的上进行的 1. 搜索区间的确定搜索区间的确定在以下在以下讨论讨论中，中，总总假定一元函数假定一元函数是是单单谷函数。谷函数。定定义义3.1 设设，是是 在在L上的全局上的全局极小点。如果对于极小点。如果对于L上任意的两点上任意的两点 ，当，当时时， ；当；当时时， ，那么称，那么称 是区间是区间L上的单谷函数。上的单谷函数。下图给出了单谷函数的基本图形

93、。下图给出了单谷函数的基本图形。定义定义3.2 设设 ,是是在在L上的上的全局极小点。如果能够找到全局极小点。如果能够找到 ，使得，使得 那么那么闭闭区区间间就称就称为为极小点的一个极小点的一个搜索区搜索区间间，记为记为 。搜索区。搜索区间间有有时时也也记记作作，其中，其中显然，单谷函数的定义域区间是搜索区间。显然，单谷函数的定义域区间是搜索区间。单谷函数的性质。单谷函数的性质。定理定理3.1 设设是是单单谷函数谷函数极小点的一个搜索区极小点的一个搜索区间间。 在在内任取两点内任取两点 ，若，若，则则 是是极小点的一个搜索区极小点的一个搜索区间间；若；若 ，则则是是极小点的一个搜索区极小点的一

94、个搜索区间间。 直直线线搜索算法的第一步一般得先确定搜索算法的第一步一般得先确定的一个的一个 （初始）搜索区（初始）搜索区间间。根据定理。根据定理3.1，可以，可以给给出确定搜索区出确定搜索区间间的如下算法。的如下算法。算法算法3.1（确定搜索区间）（确定搜索区间）已知：目已知：目标标函数函数。选选定初始点定初始点和步和步长长。计计算算，。若若，则则置置，。，转转； 否否则转则转。置置计计算算，。若。若，则转，则转；否则转否则转。置置，（即即为为搜索区搜索区间间），），计计算算结结束。束。上述过程开始时，必须选定初试点上述过程开始时，必须选定初试点 和步和步长长 。对于。对于 任意给定的任意给

95、定的 ，一般来说，一般来说， 无固定选取模式。无固定选取模式。但但对对于于在下降算法模式中所引入的在下降算法模式中所引入的而言，可而言，可选选取取等于等于0（理论上）或接近（理论上）或接近0（实际计算中）。（实际计算中）。而对于而对于 ，如果选得过小，那么需要迭代许多次才能找到，如果选得过小，那么需要迭代许多次才能找到一个搜索区间；如果选得太大，虽然很少几步就可能把极一个搜索区间；如果选得太大，虽然很少几步就可能把极小点包括进来，但是这又会给下一步搜索极小点的过程增小点包括进来，但是这又会给下一步搜索极小点的过程增加负担。下面是确定加负担。下面是确定 的一种比较合理而有效的方法。的一种比较合理

96、而有效的方法。第一次迭代（第一次迭代（，即从，即从到到的迭代）的迭代）时时， 的初始步长可取为的初始步长可取为1，或根据问题中出现的数据的数量级，或根据问题中出现的数据的数量级估计选定。而以后各次迭代的初始步长可按公式（估计选定。而以后各次迭代的初始步长可按公式（3.5）计算，计算， （3.5）其中其中 。这是因为从。这是因为从 到到 的距离的距离 一一般比从般比从 到到 的距离的距离 小或接近，所以把按小或接近，所以把按（3.5）算出的作为下一次迭代的初始步长是合适的。在）算出的作为下一次迭代的初始步长是合适的。在实际计算中，当实际计算中，当 较小时，相应的较小时，相应的 可取得小些，而随可

97、取得小些，而随着的着的 增大，相应的增大，相应的 可取得接近可取得接近1。2. 直线搜索的方法直线搜索的方法（1）黄金分割法）黄金分割法 黄金分割法属于区间收缩法。它适用于任何单谷函黄金分割法属于区间收缩法。它适用于任何单谷函数求极小值问题。对函数除数求极小值问题。对函数除“单谷单谷”外，不作其它要求，外，不作其它要求，甚至可以不连续。因此这种方法的适用面相当广。甚至可以不连续。因此这种方法的适用面相当广。 黄金分割法的思想是：在每次迭代中，合理地设置两黄金分割法的思想是：在每次迭代中，合理地设置两个插入点的位置，以使得在计算函数值次数同样多的条件个插入点的位置，以使得在计算函数值次数同样多的

98、条件下，将区间缩小得最快。下，将区间缩小得最快。 设区间设区间 的长为的长为1。在距点。在距点 分分别为别为 和和 的地方插入的地方插入 和和 。为了确定为了确定 和和 ，提出以下条，提出以下条件：件： 第一，希望第一，希望 和和 在在 中的位置是对称的。按这中的位置是对称的。按这一条件，有一条件，有即即 . （3.6）这样这样无无论删论删去哪一段，去哪一段，总总保留保留长为长为的区的区间间。第二，第二，删删掉一段，例如掉一段，例如删删掉掉，在保留下来的区，在保留下来的区间间，使得，使得里再插入一个点里再插入一个点在在中的位置与中的位置与在在中的位置具有相同的比例，从而保中的位置具有相同的比例

99、，从而保证证每次迭代都能每次迭代都能缩缩小区小区间间。按。按这这一条件，有一条件，有以同一比率以同一比率即即 或或 . （3.7）把（把（3.7）代入（）代入（3.6）中，得到关于）中，得到关于的一元二次方程的一元二次方程其合理的根是其合理的根是（3.8）代回（代回（3.6），得），得 在古代，人们认为按比率在古代，人们认为按比率0.618分割线段是最协调的，分割线段是最协调的，胜似黄金，故称黄金分割。因此，上述按比率胜似黄金，故称黄金分割。因此，上述按比率0.618缩小缩小搜索区间的迭代方法称为黄金分割法或搜索区间的迭代方法称为黄金分割法或0.618法。法。算法算法3.2 （黄金分割法）（黄

100、金分割法）P145（2）抛物线插值法）抛物线插值法 抛物线插值法属于函数逼近法。它适用于连续的单谷抛物线插值法属于函数逼近法。它适用于连续的单谷函数求极小值问题。函数求极小值问题。 抛物线插值法的思想是：设抛物线插值法的思想是：设 在搜索区在搜索区间间上上连续连续。记记 和和。 如果如果（3.9） 与与（3.10）（两等号不同时成立）同时成立，那么可以过（两等号不同时成立）同时成立，那么可以过 和和 三点作抛物线插值，设抛物线方程为三点作抛物线插值，设抛物线方程为（3.11）其其实实是在区是在区间间上上对对所作的一个所作的一个曲曲线拟线拟合。合。记记的极小点的极小点为为，则则根据根据 提供的信

101、息，提供的信息，我们可以将搜索区间我们可以将搜索区间 缩小，然后在缩小了的区间上缩小，然后在缩小了的区间上再作抛物线插值。如此下去，最终可以求到再作抛物线插值。如此下去，最终可以求到 在在 中的极小点中的极小点。 令令(3.12）解出解出 （3.13）根据插根据插值值条件条件和和，列出关于，列出关于 和和的的线线性方程性方程组组由此解出由此解出，并代入（并代入（3.13）中，得）中，得（3.14）这这个公式的使用条件个公式的使用条件仅仅仅仅是是和和 三点不共线。可以证明（习题三点不共线。可以证明（习题3.5），在（），在（3.9）和）和（3.10）（两等号不同时成立）同时成立的条件下，由）（两

102、等号不同时成立）同时成立的条件下，由（3.14）所确定的）所确定的 是是的极小点，并且的极小点，并且。以下讨论算法的终止准则和缩小搜索区间的方法。以下讨论算法的终止准则和缩小搜索区间的方法。按（按（3.14）计计算出算出。由极限理。由极限理论论知道，如果知道，如果 与与都很小，那么都很小，那么也必然很小，当然也必然很小，当然也也应该应该很小。很小。 计算经验指出，可以采用计算经验指出，可以采用（3.15） 作为终止准则。作为终止准则。当当终终止准止准则满则满足足时时，取，取和和中函数中函数值较值较小的点小的点提供的提供的缩缩小。小。这这个个过过程如下：程如下：作作为为极小点；当极小点；当终终止

103、准止准则则未未满满足足时时，则则需要利用需要利用信息将原来的搜索区信息将原来的搜索区间间比比较较和和的大小，有两种情况：若的大小，有两种情况：若，则则转转；否；否则则，转转。若若，则则置置，转转； 若若，则则，转转。 置置若若，则则置置，转转； 若若，则则，转转。置置转转向向计计算新的搜索区算新的搜索区间间上的插上的插值值抛物抛物线线的极小点的极小点算法流程图见书上图算法流程图见书上图3-5。 包括黄金分割法和抛物线插值法在内的许多一维问题包括黄金分割法和抛物线插值法在内的许多一维问题的迭代方法全部依赖于函数单谷性的假设。但在许多问题的迭代方法全部依赖于函数单谷性的假设。但在许多问题中，这一假

104、设不成立或难以验证。解决这一困难的办法，中，这一假设不成立或难以验证。解决这一困难的办法，尤其当初始搜索区间很大的时候，是将搜索区间分成若干尤其当初始搜索区间很大的时候，是将搜索区间分成若干个较小区间，然后在每个子区间上寻求极小，最后又在所个较小区间，然后在每个子区间上寻求极小，最后又在所有子区间的极小中选取最小的一个作为问题的最优解。有子区间的极小中选取最小的一个作为问题的最优解。（3）不精确一维搜索技术）不精确一维搜索技术 精确的一维搜索过程往往需要花费很大的计算量才有精确的一维搜索过程往往需要花费很大的计算量才有可能求到符合精度要求的最优步长因子。当多维问题的迭可能求到符合精度要求的最优

105、步长因子。当多维问题的迭代点距极小点较远时，显然精确地求解一维子问题对求解代点距极小点较远时，显然精确地求解一维子问题对求解多维问题本身没有太大的意义。另外很多最优化方法，如多维问题本身没有太大的意义。另外很多最优化方法，如Newton法和拟法和拟Newton法，其收敛速度也并不依赖于精法，其收敛速度也并不依赖于精确的一维搜索过程。因此，在实际计算中，只要选取的步确的一维搜索过程。因此，在实际计算中，只要选取的步长因子能够保证目标函数在每一步的迭代中都有长因子能够保证目标函数在每一步的迭代中都有“满意的满意的”下降就可以了。这样，既会大大地节省计算量，同时还下降就可以了。这样，既会大大地节省计

106、算量，同时还会从整体上加快计算进程。会从整体上加快计算进程。考虑由多维问题引出的一维问题考虑由多维问题引出的一维问题（3.16）其中其中具有一具有一阶连续阶连续偏偏导导数。数。 Goldstein(1965年年)和和Powell（1975年）给出了用来年）给出了用来设计（设计（3.16）不精确一维搜索过程的两个条件：）不精确一维搜索过程的两个条件： ）； （3.17） (3.18).其中其中使得使得，而，而是是给给定定的常数，通常取的常数，通常取 。条件。条件）表示）表示应应使新迭代点使新迭代点的函数的函数值值相相对对上一迭代点上一迭代点 的函数的函数值值的下降幅度的下降幅度须须不低于不低于某

107、个量，而条件某个量，而条件）则则表示目表示目标标函数函数 在新迭代点在新迭代点处处沿沿 方向的方向方向的方向导导数数应应不小于不小于 在上一迭代点在上一迭代点 处处沿沿方向的方向方向的方向导导数的数的 倍。换句话说，若倍。换句话说，若 满足满足 条件条件），则认为在点），则认为在点 处已获得处已获得“满意的满意的”函数值的下降。函数值的下降。 而若而若满满足条件足条件），这时这时有两种可能性，有两种可能性， 要么要么已是点已是点 方向方向处处的上升方向，的上升方向， 要么要么方向方向虽虽然然还还是点是点下降方向，下降方向， 处处的的但函数但函数在点在点 处处沿沿方向的下降率已低于方向的下降率已

108、低于 处处沿沿方向的下降率方向的下降率在点在点 倍，倍，这时这时若若继续继续沿沿 方向作一维搜索，只会徒增计算量，而不会再获得函数值方向作一维搜索，只会徒增计算量，而不会再获得函数值的较大下降量，因此，一旦的较大下降量，因此，一旦 满满足条件足条件）就需要确定就需要确定。新的搜索方向新的搜索方向 以上分析表明，在实际计算中，选取满足（以上分析表明，在实际计算中，选取满足（3.17）和）和（3.18）的）的 作作为为确定确定的步的步长长因子是合适的，因子是合适的， 即即。一般地，一般地， 越小，一越小，一维维搜索越精确，但搜索越精确，但计计算量也越大。算量也越大。 不精确的一不精确的一维维搜索不

109、要求搜索不要求过过小的小的而而越小，条件越小，条件）越容易越容易满满足。足。 在在实际计实际计算中，通常取算中，通常取或更小的或更小的值值值值的的选选取不太敏感），取不太敏感），。（由此得出的解通常（由此得出的解通常对对算法算法3.3（不精确一维搜索）（不精确一维搜索）已知：已知：，且，且。给给定定 （通常取（通常取），初始），初始（可取（可取1或参照（或参照（3.5）给给出）。出）。步步长长计计算算。置。置。计计算算；若（若（3.18）成立，则转）成立，则转；否则，置；否则，置，然后转，然后转； 若（若（3.17）成立，）成立，则则打印打印，计计算算结结束；否束；否则则，然后，然后转转。置置

110、 算法说明：算法说明：）第第步中若（步中若（3.18）不成立，）不成立，则则表明沿表明沿方向方向有有继续继续前前进进的必要；的必要； ）第）第步中若（步中若（3.17）不成立，这表明当前步长过）不成立，这表明当前步长过大，需缩小搜索范围。大，需缩小搜索范围。不精确一维搜索的算法流程图不精确一维搜索的算法流程图3.2 最速下降法最速下降法 最速下降法是最早的求解多元函数极值的数值方法。最速下降法是最早的求解多元函数极值的数值方法。它直观、简单。它的缺点是，收敛速度较慢、实用性差。它直观、简单。它的缺点是，收敛速度较慢、实用性差。1. 基本思想基本思想求解求解问题问题（3.1）。假）。假设设迭代已

111、得到迭代已得到。在点。在点处处，取搜索方向，取搜索方向为为（3.19）沿沿进进行直行直线线搜索，由此确定搜索，由此确定（3.20） 其中步其中步长长因子因子满满足足（3.21） （3.20）、（）、（3.21）简单地合记为）简单地合记为（3.22） 3.20）或（）或（3.22）称为最速下降迭代公式，由该公式）称为最速下降迭代公式，由该公式产生的算法称为最速下降法。产生的算法称为最速下降法。 今后记今后记2. 算法算法算法算法3.4（最速下降法）（最速下降法） P151将最速下降法应用于正定二次函数将最速下降法应用于正定二次函数（3.23） 可以推出显式迭代公式。可以推出显式迭代公式。设设第第

112、迭代点迭代点为为，求，求的表达式。由的表达式。由（3.24） （3.25）， （3.26），（直线搜索性质），（直线搜索性质）得得即即由此解出由此解出（3.27） 例例3.1 P1523. 锯齿现象锯齿现象 最速下降法的迭代点在向极小点靠近的过程中，走的最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向是曲折的路线：后一次搜索方向 与前一次搜索方向与前一次搜索方向 总是相互垂直的，称它为锯齿现象。这一点在前面的例题总是相互垂直的，称它为锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和

113、极特殊的初始点外，这种现象一般都要发生。函数）和极特殊的初始点外，这种现象一般都要发生。 从直观上可以看到，在远离极小点的地方，每次迭代从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的下降，但在接近极小点的都有可能使目标函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快。因而收敛速度不快。 已有结论表明，最速下降法对于正定二次函数关于任已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的，而且恰好是线性收敛的。意初始点都是收敛的，而且恰好是线性收敛的。

114、3.3 Newton法法如果目如果目标标函数函数在在上具有上具有连续连续的二的二阶阶偏偏导导数，数，其其Hesse矩矩阵阵 正定且可以表达成显式（今后记正定且可以表达成显式（今后记 ），那么使用），那么使用Newton法求解（法求解（3.1）会很快）会很快地得到极小点。地得到极小点。 1. 基本思想基本思想考考虑虑从从到到的迭代的迭代过过程。在点程。在点处处，对对按按Taylor级级数展开到第三数展开到第三项项，即，即（3.29） 因因为为正定，所以正定，所以是正定二次函数。令是正定二次函数。令得得（3.30） 由此解出由此解出的极小点，的极小点，记为记为，即，即（3.31） 是是极小点极小点

115、的新的近似点。的新的近似点。 （3.31）称为）称为Newton迭代公式，由该公式产生的算法称为迭代公式，由该公式产生的算法称为Newton法。法。注意到，注意到，当目当目标标函数函数是正定二次函数（是正定二次函数（3.36）时时，。这说这说明：明：对对于于正定二次函数，正定二次函数，Newton法一法一次迭代就会得到最次迭代就会得到最优优解。解。（3.31）有直）有直观观的的几何解几何解释释。函数。函数过过点点的等的等值值面方程面方程为为（3.32）在点在点处处，用一个与曲面（，用一个与曲面（3.32）最密切的二次曲面来）最密切的二次曲面来代替它，代替它，这这个二次曲面的方程即是个二次曲面的

116、方程即是当当正定正定时时，它是一个超，它是一个超椭椭球面，球面，的极小点的极小点 正是这个超椭球面的中心。我们就用正是这个超椭球面的中心。我们就用 作作为为极小点极小点 的新的近似点。下图画出了二维情况时的几何解释。的新的近似点。下图画出了二维情况时的几何解释。例例3.2 P1542. 算法算法算法算法3.5（Newton法）法） P1553. 修正修正Newton法法 Newton法的优点是收敛速度快、程序简单。特别是法的优点是收敛速度快、程序简单。特别是前一个优点，在最优化方法中尤为突出。但计算实践指出，前一个优点，在最优化方法中尤为突出。但计算实践指出，Newton算法在运行时经常失败。

117、下面将找出失败的原因，算法在运行时经常失败。下面将找出失败的原因，并给出解决办法。并给出解决办法。以下讨论仅假定以下讨论仅假定Hesse矩阵可以求到。矩阵可以求到。 ）在迭代点在迭代点处处Hesse矩矩阵阵变为变为奇异，由奇异，由线线性性方程方程组组（3.33）解不出解不出。遇有此种情况，改取。遇有此种情况，改取，然后作直，然后作直线线搜索搜索（3.34） 即用最速下降法的迭代公式代替即用最速下降法的迭代公式代替Newton法的迭代公法的迭代公式，从而完成这一次迭代。式，从而完成这一次迭代。）Hesse矩矩阵阵非奇异，即非奇异，即存在。存在。这时这时可由可由（3.33）解出）解出（称为（称为N

118、ewton方向）。方向）。按按Newton迭代公式，有迭代公式，有（3.35） （3.35）可以理解）可以理解为为从点从点出出发发沿沿方向方向进进行直行直线线搜索，搜索，步步长长因子取因子取为为1。考考虑虑到目到目标标函数可能很复函数可能很复杂杂，因而不能，因而不能总总保保证证方向是下降方向，有方向是下降方向，有时时即使是下降方向，也会由于步即使是下降方向，也会由于步长长的的因子不加因子不加选择选择地取地取为为1，而不能保，而不能保证证 。对此，。对此， 分以下两种情况处理。分以下两种情况处理。 若若，则则（3.35）的迭代有效。）的迭代有效。若若，则则又分以下两种情况又分以下两种情况处处理。

119、理。第一，当第一，当（是某一很小的正数）是某一很小的正数）时时，说说明明与与 几乎垂直，故几乎垂直，故Newton方向方向 是不利是不利方向。这时，改取方向。这时，改取 ，然后按（，然后按（3.34）再重新进行）再重新进行直线搜索。直线搜索。第二，当第二，当 时，说明时，说明Newton方向方向 是下降方向，这时按（是下降方向，这时按（3.34）重新进行）重新进行直线搜索；否则，直线搜索；否则，当当 时时（说说明明Newton为为方向是上升方向）方向是上升方向）, ,改取改取Newton方向的反方向方向的反方向搜索方向，然后按（搜索方向，然后按（3.34）再重新）再重新进进行直行直线线搜索。搜

120、索。修正修正Newton法的算法流程图见书上图法的算法流程图见书上图3-13。开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京3.4 共轭方向法与共轭梯度法共轭方向法与共轭梯度法 共轭方向法是介于最速下降法和共轭方向法是介于最速下降法和Newton法之间的一法之间的一种方法，它克服了最速下降法的锯齿现象，从而提高了收种方法，它克服了最速下降法的锯齿现象，从而提高了收敛速度；它的迭代公式也比较简单，不必计算目标函数的敛速度；它的迭代公式也比较简单，不必计算目标函数的二阶导数，与二阶导数，与Newton法相比，减少了计算量和存储量。法相比，减少了

121、计算量和存储量。它是比较实用而有效的最优化方法。它是比较实用而有效的最优化方法。 共轭方向法涉及共轭方向的概念和性质。共轭方向的共轭方向法涉及共轭方向的概念和性质。共轭方向的概念是在研究正定二次函数概念是在研究正定二次函数（3.36） 时产生的。本节和下节所介绍的方法有一个共同的特点，时产生的。本节和下节所介绍的方法有一个共同的特点，即首先以（即首先以（3.36）为目标函数给出有关的算法，然后再把）为目标函数给出有关的算法，然后再把算法用到更一般的目标函数上。算法用到更一般的目标函数上。本节内容对今后许多章节起着基础的作用。本节内容对今后许多章节起着基础的作用。1. 基本思想基本思想 现在把下

122、降法用于形式为（现在把下降法用于形式为（3.36）的二次函数。为便）的二次函数。为便于说明共轭方向法的基本思想，首先考虑二维的情形。于说明共轭方向法的基本思想，首先考虑二维的情形。（图（图314）任任选选初始点初始点，沿它的某个下降方向，例如向量，沿它的某个下降方向，例如向量的方向，作直的方向，作直线线搜索，得到搜索，得到（图图314）。）。 由（由（4.16）知）知 (3.37)一个设想是，干脆选择下一个迭代的搜索方向一个设想是，干脆选择下一个迭代的搜索方向 就从就从直指极小点直指极小点 怎样确定，它应该满足什么条件？怎样确定，它应该满足什么条件？因因为为从从直指极小点直指极小点，所以，所以

123、可以表示可以表示为为（3.38）其中其中是最是最优优步步长长因子。因子。显显然，当然，当时时，。对（对（3.36）求导数，有）求导数，有 （3.39）因因为为是极小点，所以有是极小点，所以有将（将（3.38）代入此式，并由（）代入此式，并由（3.39）可得）可得上式两上式两边边同同时时左乘左乘，并注意到，并注意到和和便得到便得到（3.40）.这这就是就是为为使使直指极小点直指极小点，所必所必须满须满足的条件。足的条件。满满足足（3.40）的两个向量的两个向量和和称称为为共共轭轭向量，向量，和和的方向是的方向是共共轭轭方向。方向。或称或称利用利用（3.40）可以）可以给给出出的表达式。的表达式。

124、设设（3.41）,上式两上式两边边同同时时左乘左乘，得，得由此解出由此解出并代回到并代回到（3.41），便得，便得（3.42）.归纳归纳一下，一下，对对于二元二次目于二元二次目标标函数，从任意初始点函数，从任意初始点出出发发，沿任意下降方向，沿任意下降方向做直做直线线搜索得到搜索得到；再从；再从出出发发，沿，沿的共的共轭轭方向方向 （可由（可由（3.42）确定）作直确定）作直线线必是极小点必是极小点。搜索，所得到的搜索，所得到的上面的上面的结结果可以推广到果可以推广到维维空空间间中，即在中，即在维维空空间间中，中，个互相共个互相共轭轭的方向，的方向，对对于于元正定二次函数，元正定二次函数，个共

125、个共轭轭方向最多作方向最多作直直线线搜索，就可以求到目搜索，就可以求到目标标函数的极小点。函数的极小点。可以找出可以找出从任意初始点出从任意初始点出发发，顺顺次沿着次沿着这这次次 对于对于 元正定二次目标函数，如果从任意初始点出发元正定二次目标函数，如果从任意初始点出发经过有限次迭代就能够求到极小点，那么称这种算法具有经过有限次迭代就能够求到极小点，那么称这种算法具有二次终止性。例如，二次终止性。例如，Newton法对于二次函数只须经过一法对于二次函数只须经过一次迭代就可以求到极小点，因此是二次终止的；而最速下次迭代就可以求到极小点，因此是二次终止的；而最速下降法就不具有二次终止性。共轭方向法

126、（如共轭梯度法、降法就不具有二次终止性。共轭方向法（如共轭梯度法、拟拟Newton法等）也是二次终止的。法等）也是二次终止的。一般说来，具有二次终止性的算法，在用于一般函数一般说来，具有二次终止性的算法，在用于一般函数时，收敛速度是较快的。时，收敛速度是较快的。2. 共轭向量及其性质共轭向量及其性质定定义义3.3 3.3 设设是是对对称正定矩称正定矩阵阵。若。若维维向量向量满满足足空空间间中的非零向量中的非零向量（3.43）则则称称是是共共轭轭向量向量或称向量或称向量是是共共轭轭的的（简简称共称共轭轭），称），称 的方向是的方向是方向方向。共共轭轭当当（单单位矩位矩阵阵）时时，（3.43）为为

127、即向量即向量 互相正交。由此看到，互相正交。由此看到，“正交正交”是是“共轭共轭”的一种特殊情形，或说，的一种特殊情形，或说，“共轭共轭”是是“正交正交”的推的推广。广。 以下各定理都是描述共轭向量的性质以及在极小化以下各定理都是描述共轭向量的性质以及在极小化正定二次函数的过程中以共轭方向作为搜索方向所得到的正定二次函数的过程中以共轭方向作为搜索方向所得到的有关结论。有关结论。定理定理3.2 3.2 若非零向量若非零向量是是共共轭轭的，的，则线则线性无关。性无关。推推论论3.3 3.3 在在维维向量空向量空间间中，非零的共中，非零的共轭轭向量的向量的。个数不超个数不超过过设设是是中的非零中的非

128、零共共轭轭向量。因向量。因为为的一个的一个维维子空子空间间，维维子空子空间间中的任意一个向量中的任意一个向量均可表示均可表示为为线线性无关，所以由它性无关，所以由它们们可以可以张张成成且且这这个个其中其中是任意是任意实实数。数。定定义义3.4 3.4 设设是是中的中的线线性无关向量，性无关向量，。那么形式。那么形式为为的向量构成的集合，的向量构成的集合，记为记为，称，称为为由点由点和向量和向量所生成的所生成的线线性流形性流形。3. 共轭方向法共轭方向法共轭方向法的理论基础是下面的定理。共轭方向法的理论基础是下面的定理。定理定理3.4 假设假设（1 1）为为对对称正定矩称正定矩阵阵；（2） 非零

129、向量非零向量是是共共轭轭向量；向量； （3 3）对对二次目二次目标标函数函数（3.36）顺顺次次进进行行次直次直线线搜索搜索其中其中是任意是任意选选定的初始点，定的初始点，则则）； （3.44）是二次函数是二次函数（3.36）在在线线性流形性流形上的极小点。上的极小点。证证 ）根据）根据（1.46），直接有，直接有证证明：明：对对于于，（，（3.44）也成立。也成立。以下。以下由条件（由条件（3），有），有其中其中是从点是从点出出发发沿沿方向作直方向作直线线搜索得到的最搜索得到的最优优步步长长因子。因子。 用用左乘上式两左乘上式两边边，然后再同，然后再同时时加上加上， 利用（利用（3.39）就

130、得到）就得到（3.45）由这个公式，可以递推得到由这个公式，可以递推得到该该式两式两边边同同时时左乘左乘，得，得.此式右边各项实际全部为零。这是因为此式右边各项实际全部为零。这是因为 故由（故由（1.46）知）知 。又由。又由 的共轭性知其余各项也全部为零。这就证明了（的共轭性知其余各项也全部为零。这就证明了（3.44）。）。 ）按条件（）按条件（3 3），必有），必有于是，存在一于是，存在一组组数数使得使得（3.46）而而对对于任意于任意给给定得定得，存在另一，存在另一组组数数使得使得（3.47）（3.47）减（）减（3.46），得），得利用（利用（3.44），由上式即得），由上式即得（3.

131、48）把二次函数把二次函数在点在点处处作作TaylorTaylor级级数展开数展开，注意到，注意到（3.48），就有，就有然后令然后令，由条件（由条件（1），当），当时时，有，有 。于是，于是，对对于任意于任意 ，但，但，总总有有 ，即，即是是（3.36）在在线线性流形性流形上的（上的（严严格）极小点。格）极小点。 这这个定理看来个定理看来较较繁，但可借用直繁，但可借用直观观的几何的几何图图形来帮助形来帮助的情形的情形为为例，如例，如图图示。示。理解。以理解。以和和是是共共轭轭向量，向量，张张成了二成了二维维空空间间，这这是是过过坐坐标标原点的一个平面。原点的一个平面。 现现在，在，过过点点沿

132、沿方向作直方向作直线线，再，再过过点点沿沿方向作直方向作直线线搜索得到搜索得到 搜索得到搜索得到点点由向量由向量和和张张成的平面就是成的平面就是线线性流形性流形， 。过过，它是，它是的平行平面。的平行平面。定理定理3.4的的论论断是，断是，处处的梯度的梯度必与必与和和并且并且 最后一个迭代点最后一个迭代点垂直，垂直，是三元二次目是三元二次目标标函数函数在在线线性流形性流形（即（即过过由由和和张张成的平面）上的极小点。成的平面）上的极小点。 当当时时，线线性流形性流形整个整个维维空空间间，因此有如下推，因此有如下推论论。就是就是推推论论3.53.5 在在定理定理3.43.4中，当中，当时时，是正

133、定是正定中的极小点。中的极小点。函数（函数（3.36）在）在二次二次 推推论论3.6 在在定理定理3.4中，中，的任意的任意线线性性组组合合（其中（其中是任意是任意实实 数）都与数）都与正交。正交。 上述上述论论断提供了求正定二次函数（断提供了求正定二次函数（3.36）极小点的一）极小点的一出出发发，顺顺次沿次沿个个共共轭轭方向作直方向作直线线搜索，最多搜索，最多经过经过次迭代就一定可以求次迭代就一定可以求种原种原则则方法。方法。这这就是，从任意初始点就是，从任意初始点到极小点。到极小点。 算法算法3.6（共轭方向法）（共轭方向法） P136 算法第算法第4步中提供共轭方向的方法有多种。不同的

134、提步中提供共轭方向的方法有多种。不同的提供方法将对应不同的共轭方法。每种方法也因产生共轭方供方法将对应不同的共轭方法。每种方法也因产生共轭方向的特点而得名，例如共轭梯度法。向的特点而得名，例如共轭梯度法。 下面将介绍几个有效的共轭方向法。下面将介绍几个有效的共轭方向法。 4. 共轭梯度法共轭梯度法 在共在共轭轭方向法中，如果初始共方向法中，如果初始共轭轭向量向量恰好取恰好取为为处处的的负负梯度梯度，而其余共，而其余共轭轭向量向量 点点初始初始由第由第个迭代点个迭代点处处的的负负梯度梯度与已与已经经得到的共得到的共轭轭向量向量 负负梯度而得名。首先梯度而得名。首先针对针对目目标标函数是（函数是（

135、3.36）形式的正定）形式的正定的的线线性性组组合来确定，那么合来确定，那么这这个共个共轭轭方向法就称方向法就称为为共共轭轭梯度法梯度法。它因每一个共。它因每一个共轭轭向量的向量的产产生都依生都依赖赖于迭代点于迭代点处处的的二次函数来二次函数来讨论讨论。（1）第）第1个迭代点的获得个迭代点的获得选选定初始点定初始点。设设（否（否则则迭代迭代终终止），因此止），因此。取。取（3.52）则第则第1个迭代点个迭代点 其中其中 显显然然。（2）第）第2个迭代点的获得个迭代点的获得设设，因此，因此。由。由知知与与线线性无关。取性无关。取（3.53）其中其中是使是使与与共共轭轭的待定系数。令的待定系数。令

136、由此解出由此解出并代回（并代回（3.53）确定）确定。并。并获获得第得第2个迭代点个迭代点其中其中 （3）第）第3个迭代点的获得个迭代点的获得设设，因此，因此。由。由知知与与线线性无关。取性无关。取其中其中是使是使与与共共轭轭的待定系数。令的待定系数。令由此解出由此解出从而确定从而确定。并。并获获得第得第3个迭代点个迭代点其中其中 上述上述过过程程仅仅表明表明与与， 与与共共轭轭。问问：与与也共也共轭吗轭吗？计计算算且由（且由（3.52）和（）和（3.53）知）知和和都是都是和和的的线线性性组组合，合，而必有而必有，因此，因此，即，即与与也共也共轭轭。如此做下去，如此做下去，设设已已经经构造出

137、共构造出共轭轭向量向量，并已并已获获得前得前个迭代点个迭代点，而且步，而且步长长因子因子均不均不为为零。零。个迭代点的个迭代点的获获得得设设（否（否则则迭代迭代终终止），此止），此时时。由。由知知是是线线性无关的，取性无关的，取（3.54）其中其中是使是使与与共共轭轭的待定系数。令的待定系数。令（4）第）第和和，且，且由此解出由此解出从而确定了从而确定了。并。并获获得第得第个迭代点个迭代点其中其中 除与除与共共轭轭外，它外，它还还与与共共轭轭。因此，在因此，在均不是极小点均不是极小点的前提下，的前提下，可以按照上述方法可以按照上述方法顺顺序构造出序构造出 个非零共个非零共轭轭向量。根据向量。根

138、据定理定理3.4，第第 个迭代点个迭代点必是（必是（3.36）的极小点）的极小点 。实际实际次迭代（次迭代（）就求）就求。计计算中，也有可能第算中，也有可能第到了极小点，此到了极小点，此时时算法算法3.7（用于正定二次函数的共轭梯度法）（用于正定二次函数的共轭梯度法） P166例例3.3 P167用共轭梯度法求解用共轭梯度法求解初始点取为初始点取为 。为使共轭梯度算法为使共轭梯度算法3.7也适用于非二次函数，最好消也适用于非二次函数，最好消。去（去（3.57）中的）中的由（由（3.45），有），有代入到（代入到（3.57）中，得）中，得（3.59）此式中已不再出此式中已不再出现现矩矩阵阵。另外

139、，此式。另外，此式还还可以有以下三种可以有以下三种不同的等价形式。不同的等价形式。将（将（3.54）两端作）两端作转转置运算，并同置运算，并同时时右乘右乘，得，得（3.60） 根据根据定理定理3.43.4知，知，；又根据直；又根据直线线搜索的性搜索的性质质知知（3.61）于是，由（于是，由（3.60）得）得（3.62）又将（又将（3.54）两端作）两端作转转置运算，并同置运算，并同时时右乘右乘，得，得（3.63） （1）把（）把（3.61）、（）、（3.62）和（）和（3.63）代入到（）代入到（3.59）中，得中，得（3.64)此式称为此式称为FletcherReeves公式公式(1964年

140、年)。（2）把（）把（3.61）和（）和（3.62）代入到（）代入到（3.59）中，得）中，得（3.65) 此式称为此式称为DixonMyers公式公式(1972年年)。（3）把（）把（3.61）和（）和（3.63）代入到（）代入到（3.59）中，得）中，得(3.66)此式称为此式称为PolakRibiere公式公式(1969年年)。 在前面给出的用于正定二次函数的共轭梯度算法在前面给出的用于正定二次函数的共轭梯度算法3.6中，分别以（中，分别以（3.59）、（）、（3.64）、（）、（3.65）和（）和（3.66）替）替换（换（3.57）就将得到四种不使用）就将得到四种不使用Hesse矩阵的

141、共轭梯度法，矩阵的共轭梯度法，它们对于正定二次目标函数和精确的直线搜索是完全等价它们对于正定二次目标函数和精确的直线搜索是完全等价的，都可以用于非二次目标函数。的，都可以用于非二次目标函数。由公式（由公式（3.63）看到，对于一般目标函数，仍有）看到，对于一般目标函数，仍有 这说明共轭梯度法对于一般目标函数仍然是下降算这说明共轭梯度法对于一般目标函数仍然是下降算法，即使迭代点距极小点很远，这种方法也可以使用。法，即使迭代点距极小点很远，这种方法也可以使用。 实际上，可以把共轭梯度法当作最速下降法的一种改实际上，可以把共轭梯度法当作最速下降法的一种改进方法，因为当令所有的时，它就变为最速下降法。

142、共轭进方法，因为当令所有的时，它就变为最速下降法。共轭梯度法的效果不低于最速下降法。共轭梯度法是收敛的算梯度法的效果不低于最速下降法。共轭梯度法是收敛的算法。法。 共轭梯度法还有一个优点，就是存储量小。因为它不共轭梯度法还有一个优点，就是存储量小。因为它不涉及矩阵，仅仅存放向量就够了，因此适用于维数较高的涉及矩阵，仅仅存放向量就够了，因此适用于维数较高的最优化问题。最优化问题。 共轭梯度不要求精确的直线搜索，这也是一个优点。共轭梯度不要求精确的直线搜索，这也是一个优点。但是，不精确的直线搜索可能导致迭代出来向量不再共轭，但是，不精确的直线搜索可能导致迭代出来向量不再共轭，从而有可能不再线性无关

143、，这将降低方法的效能。克服的从而有可能不再线性无关，这将降低方法的效能。克服的办法是，重设初始点，即把经过办法是，重设初始点，即把经过 次迭代后得到的次迭代后得到的 作为初始点，再开始新一轮的迭代。计算实践指出，作为初始点，再开始新一轮的迭代。计算实践指出，用用 比用比用 作初始点要好。作初始点要好。 理论上，共轭方向法对每一步的一维搜索有很高的理论上，共轭方向法对每一步的一维搜索有很高的精度要求。精度要求。算法算法3.8 (FletcherReeves共轭梯度法共轭梯度法) P169开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京3.5 拟

144、拟Newton法法 Newton法的优缺点都很突出。优点：高收敛速度法的优缺点都很突出。优点：高收敛速度（二阶收敛）；缺点：对初始点、目标函数要求高，计算（二阶收敛）；缺点：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储量、存储量大（需要计算、存储Hesse矩阵及其逆）。拟矩阵及其逆）。拟Newton法是模拟法是模拟Newton法给出的一个保优去劣的算法。法给出的一个保优去劣的算法。 拟拟Newton法是效果很好的一大类方法。它当中的法是效果很好的一大类方法。它当中的DFP算法和算法和BFGS算法是直到目前为止在不用算法是直到目前为止在不用Hesse矩阵矩阵的方法中的最好方法。的方

145、法中的最好方法。 本节内容是最优化方法的重点之一。本节内容是最优化方法的重点之一。1. 基本思想基本思想考虑考虑Newton迭代公式迭代公式(3.68） 这这里里搜索方向搜索方向为为，步，步长长因子因子为为1 1。我们从以下两点考虑对我们从以下两点考虑对Newton迭代公式的改进：迭代公式的改进：一、一、为为避免避免求逆矩求逆矩阵阵，设设想想用用某种某种近似矩近似矩阵阵替替换换，上式，上式则变为则变为这时这时搜索方向搜索方向为为，步，步长长因子仍因子仍为为1 1。二、为了取得更大的灵活性，考虑更一般的公式二、为了取得更大的灵活性，考虑更一般的公式(3.69）这时这时搜索方向搜索方向仍仍为为，但

146、步，但步长长因子取因子取为为最最优优步步长长。因子因子( (3.69）是代表面很广的）是代表面很广的一一类类迭代公式。例如，当迭代公式。例如，当时时，它是最速下降法公式。当，它是最速下降法公式。当时时，它是阻尼，它是阻尼NewtonNewton法公式。法公式。这样这样的的存在存在吗吗？假如存在，那么？假如存在，那么为为使使确确实实近似近似并易于并易于计计算，我算，我们们要要对对人人为为地地附加某些条件。附加某些条件。第一，第一，为为保保证证搜索方向搜索方向总总是下降方向是下降方向，都是都是对对称正定矩称正定矩阵阵。对对称，故要求称，故要求对对称；称；要求每一个要求每一个，可以可以保保证该证该式

147、成立式成立。正定正定第二，第二，为为易于易于计计算算，要求，要求到到之之间间具有具有简单简单的迭代形式。的迭代形式。最简单的迭代关系为最简单的迭代关系为. （3.70） 称称为为校正矩校正矩阵阵，（，（3.70）称）称为为校正公式校正公式。第三，第三，为为使使确确实实近似近似，要求，要求每一个每一个必必须须满满足逆足逆NewtonNewton条件。条件。设设迭代已迭代已进进行到第行到第步，步， 和和均已求出，均已求出，现现在在所必所必须满须满足的条件。足的条件。推推导导将将在点在点处处作作TaylorTaylor级级数展开，数展开，于是于是令令，则则有有所以，当所以，当正定正定时时，有，有(3

148、.72) 对对于正定二次函数（于正定二次函数（3.36），近似式（），近似式（3.72）将）将变为变为等式等式，即，即（3.73） 其中其中。因此，如果迫使因此，如果迫使满满足足类类似于（似于（3.73）的等式）的等式（3.74） ，那么那么就就有可能有可能很好地近似于很好地近似于。关系式。关系式（3.74）称）称为为逆逆NewtonNewton条件条件或或逆逆NewtonNewton方程方程。记记,.那么逆那么逆NewtonNewton条件可条件可简记为简记为（3.77） 对对于于满满足足（3.70）的）的，逆，逆NewtonNewton条件可写条件可写为为（3.78） 2. 算法算法 P1

149、72算法算法3.9（拟（拟Newton算法）算法）3. DFP算法算法 DFP法是首先由法是首先由Davidon(1959年年)提出，后由提出，后由Fletcher和和Powell（1963年）改进的算法。它是无约束年）改进的算法。它是无约束优化方法中最有效的方法之一。优化方法中最有效的方法之一。DFP法虽说比共轭梯度法法虽说比共轭梯度法有效，但它对直线搜索有很高的精度要求。有效，但它对直线搜索有很高的精度要求。（1 1）公式的推）公式的推导导考考虑虑如下校正公式如下校正公式其中其中是待定向量，是待定向量，是待定常数。是待定常数。校正矩校正矩阵阵根据根据拟拟Newton条件条件（3.78），有

150、，有如果取如果取，那么有，那么有（3.80） （2）算法）算法拟拟Newton算法算法3.9的第的第5步代入（步代入（3.80）便得到）便得到DFP法。法。考考虑虑到到计计算中有舍入算中有舍入误误差，特差，特别别是直是直线线搜索的不精确，搜索的不精确，的正定性以及搜索方向的共的正定性以及搜索方向的共轭轭性，从而性，从而导导次后重置初始点的次后重置初始点的都可能破坏都可能破坏致算法失效。致算法失效。对对此，也采取迭代此，也采取迭代 策略。策略。算法算法3.10（DFP法）法） P174例例3.4 P174（3）DFP算法的性质算法的性质定理定理3.7 3.7 在在DFPDFP算法中，若初始矩算法

151、中，若初始矩阵阵对对称正定，称正定， 中每一个都中每一个都对对称正定。称正定。则则 定理定理3.8 3.8 设设将将DFPDFP算法施用于具有算法施用于具有对对称正定矩称正定矩阵阵的二次函数（的二次函数（3.36），如果），如果）初始矩）初始矩阵阵对对称正定；称正定；）迭代点互异，）迭代点互异，产产生的搜索方向向量依次生的搜索方向向量依次为为，则则有有推推论论3.9 3.9 若定理若定理3.83.8的条件都的条件都满满足，并且足，并且经过经过次迭代才求到极小点，次迭代才求到极小点，则则。证证 由定理由定理3.83.8可知可知，即，即故故。4. BFGS算法算法 比比DFP算法更好的是算法更好的

152、是BFGS算法。这个算法是由算法。这个算法是由Broyden,Fletcher,Goldfarb和和Shanno等人给出的，其等人给出的，其校正公式为校正公式为（3.87） 只要把只要把DFP算法中涉及算法中涉及DFP校正公式的部分改为校正公式的部分改为BFGS校正公式便得到校正公式便得到BFGS算法。算法。BFGS算法具有与算法具有与DFP算法完全相同的性质，但是因为它的算法完全相同的性质，但是因为它的 不易变为奇异，不易变为奇异， 所以所以BFGS算法要比算法要比DFP算法具有更好的数值稳定性。算法具有更好的数值稳定性。BFGS算法是直到目前为止所公认的最好的拟算法是直到目前为止所公认的最

153、好的拟Newton算算法。法。 采用不精确直线搜索技术的采用不精确直线搜索技术的BFGS算法的全局收敛性算法的全局收敛性已得到证明。已得到证明。5. Broyden算法族算法族 前面讨论了三个拟前面讨论了三个拟Newton算法。它们是作为算法。它们是作为Newton法的推广而导出的。它们具有较好的性质。这种拟法的推广而导出的。它们具有较好的性质。这种拟Newton算法有一族，其中最有实用价值的几个算法都包算法有一族，其中最有实用价值的几个算法都包含在所谓的含在所谓的Broyden算法族中，其校正公式为算法族中，其校正公式为（3.88） 其中其中。 这个公式由这个公式由Broyden(1967年

154、年)给出。公式中有一个参给出。公式中有一个参数数 ，它可以取任何实数，每取一个实数，就对应一种拟，它可以取任何实数，每取一个实数，就对应一种拟Newton算法，因此称为算法族。算法，因此称为算法族。Broyden证证明了，当明了，当选选取取 和选取和选取 为对称为对称正定矩阵，则矩阵序列正定矩阵，则矩阵序列中的每一个都将是正定的，中的每一个都将是正定的，这将保证算法是下降算法。这将保证算法是下降算法。当取当取时时，BroydenBroyden校正公式既是校正公式既是DFPDFP校正公式。校正公式。时时，由，由BroydenBroyden校正公式，校正公式，经过经过整理，整理，而当取而当取即会得

155、到即会得到BFGSBFGS校正公式。校正公式。3.6 步长加速法步长加速法 步长加速法是由步长加速法是由Hooke和和Jeeves（1961年）给出的年）给出的一种直接方法。对于变量数目较少的无约束极小化问题，一种直接方法。对于变量数目较少的无约束极小化问题，这是一个程序简单又比较有效的方法。这是一个程序简单又比较有效的方法。1. 基本思想基本思想 步长加速法主要由交替进行的步长加速法主要由交替进行的“探测搜索探测搜索”和和“模式模式移动移动”组成。前者是为了寻找当前迭代点的下降方向，而组成。前者是为了寻找当前迭代点的下降方向，而后者则是沿着这个有利的方向寻求新的迭代点。后者则是沿着这个有利的

156、方向寻求新的迭代点。给给出初始点出初始点，以它作，以它作为为探探测测搜索的出搜索的出发发点（称点（称为为表示，即表示，即），在其周），在其周围寻围寻找比它更好找比它更好参考点参考点，用，用的点的点 （称（称为为基点基点），即），即，以得到下降方向，以得到下降方向 （称（称为为模式模式）。然后从）。然后从出出发发沿模式沿模式做直做直线线搜索（称搜索（称为为模式移模式移动动）(3.89) 其中其中（一般取（一般取或用或用直直线线搜索技搜索技术术来确定），来确定）， 以获得新的参考点（新的迭代点）。然后再开始探测搜索，以获得新的参考点（新的迭代点）。然后再开始探测搜索，模式移动，模式移动，。交替进行

157、的。交替进行的“探测搜索探测搜索”和和“模式移动模式移动”将使得迭代点逐渐地向极小点靠近。将使得迭代点逐渐地向极小点靠近。2. 算法算法算法算法3.11a（探测搜索）（探测搜索）已知：目已知：目标标函数函数，步，步长长向量向量参考点参考点。计计算算；置；置. .依次沿第依次沿第个坐个坐标轴标轴方向作直方向作直线线搜索：搜索：计计算算则有以下三种情况：则有以下三种情况：）若）若，则则置置；）若）若，则则置置；）若）若，则则与与不不变变。依次依次对对计计算后，最算后，最终终的的是从是从出出发发以以为为步步长长向量向量探探测测搜索的搜索的终终点。当点。当 时时，探探测测搜索称搜索称为为成功，此成功，

158、此时时必有必有，即得到模式，即得到模式；否；否则则，探探测测搜索称搜索称为为失失败败，此，此时时未未得到模式得到模式。算法算法3.11b(步长加速法步长加速法)已知：已知：目目标标函数函数，步，步长长收收缩缩系数的系数的终终止限止限。选选定初始点定初始点，初始步，初始步长长量量，置，置. .置置. .在点在点处处，以，以为为步步长长向量按算法向量按算法3.11a3.11a做探做探测测. .搜索得搜索得若若，则转则转；否否则则，转转. .做做模式移模式移动动，并，并置置. .在点在点 处处，以，以为为步步长长向量按算法向量按算法3.11a3.11a做探做探测测. .搜索得搜索得若若，则转则转；否

159、否则则，置置转转. .若若，则输则输出出，停止，停止计计算；算；否否则则，置置，转转. .192218注注* 22点模移动失败点模移动失败重置重置18点为点为探测初始点探测初始点注意注意：算法中的模式：算法中的模式为为。当由。当由3 3产产生生时时，模式模式；但；但当由当由6 6产产生生时时，模式才模式才为为，这这是加速是加速既既为为模式。模式。例例3.5 用步长加速法求解用步长加速法求解已知已知，收，收缩缩系数系数要求一直迭代到步要求一直迭代到步长长向量向量满满足足为为止。止。解解 令令，计计算算开始开始型探型探测测 ，记记，接着，接着计计算算，得得及及。因。因为为于是于是进进行第一次行第一

160、次模式移模式移动动 ，并，并计计算算。开始。开始 型探测型探测 ， ，记记，接着，接着计计算算，得得及及。因。因为为第二次第二次模式移模式移动动 ，于是，于是进进行行，并，并计计算算。开始。开始 型探测型探测 得得及及。因。因为为可以可以进进行行第三次第三次模式模式移移动动 ，于是又，于是又，并并计计算算。又开始。又开始型型探探测测 记记，接着，接着计计算算得得及及。因。因为为上次上次模式模式移移动动作作废废。 ，所以，所以重令重令，则则，并又开始，并又开始型探型探测测 探探测测失失败败，需，需缩缩小步小步长长，新的步，新的步长长向量向量计计算算终终止。止。，以上过程的路径如下图所示。以上过程

161、的路径如下图所示。开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京第 4 章 约束最优化方法 在第在第2章中已讨论过带有约束的线性规划问题，而本章中已讨论过带有约束的线性规划问题，而本章要讨论的则是带有约束的非线性规划问题，其一般形式章要讨论的则是带有约束的非线性规划问题，其一般形式为为（4.1） 其中其中 。这个问题的。这个问题的求解是指，在容许集求解是指，在容许集内找一点内找一点，使得，使得对对于任意的于任意的，都有，都有点点 称称为问题为问题（4.1）的最）的最优优解。由于解。由于带带有了有了约约束，使得束，使得对约对约束最束最优优化化

162、问题问题（4.1）的求解）的求解变变得比得比对对无无约约束最束最优优化化问题问题（3.1）的求解复）的求解复杂杂得多，也困得多，也困难难得多。本章将得多。本章将讨论讨论求解求解约约束最束最优优化化问题问题常用的两常用的两类类最最优优化方法。一化方法。一类类是所是所谓谓的的容容许许方向法方向法。它是一种直接它是一种直接处处理理约约束的方法。另一束的方法。另一类类是是所所谓谓的的罚罚函数法函数法。相。相对对前者而言，它是一种直接前者而言，它是一种直接处处理理约约束束问题问题本身的方法，其主要特点是用一系列无本身的方法，其主要特点是用一系列无约约束束问题问题的极的极小点去逼近小点去逼近约约束束问题问

163、题的最的最优优点。在点。在4.1节节中将首先中将首先讨论约讨论约束束问题问题的最的最优优性条件，性条件，为为后面算法的后面算法的终终止准止准则则提供理提供理论论依依据；在据；在4.2-4.3节节中将中将讨论讨论二种容二种容许许方向法，包括方向法，包括Zoutendijk容容许许方向法、方向法、Rosen梯度投影法；在梯度投影法；在4.6-4.8节节中将中将讨论讨论三种三种罚罚函数法，它函数法，它们们是外部是外部罚罚函数法、内部函数法、内部罚罚函函数法和乘子法。数法和乘子法。 4.1 最最优优性条件性条件 所所谓谓最最优优性性条条件件，就就是是最最优优化化问问题题的的目目标标函函数数与与约约束束

164、函函数数在在最最优优点点所所满满足足的的充充分分条条件件和和必必要要条条件件。最最优优性性必必要要条条件件是是指指，最最优优点点应应该该满满足足的的条条件件；最最优优性性充充分分条条件件是是指指，可可使使得得某某个个容容许许点点成成为为最最优优点点的的条条件件。最最优优性性条条件件对对于于最最优优化化算算法法的的终终止止判判定定和和最最优优化化理理论论的的推推证证都都是是至至关关重重要要的的。本本节仅讲节仅讲述最基本的述最基本的结论结论。 在在第第2 2章章和和第第1章章中中，已已经经分分别别讨讨论论过过线线性性规规划划问问题题和和无无约约束束问问题题的的最最优优性性条条件件。定定理理2.9是

165、是线线性性规规划划问问题题的的最最优优性性充充分分条条件件。定定理理1.15、定定理理1.17和和定定理理1.18以以及及推推论论1.16分分别别是是无无约约束束问问题题的的最最优优性性必必要要条条件件、充充分分条条件件以以及及充充分分且且必必要要条条件件。本本节节主主要要讨讨论论一一般般约约束束问问题题的的最最优优性性条条件件。我我们们将将先先从从仅仅含含等等式式约约束束或或不不等等式式约约束束的的问问题题入入手手，然后自然然后自然过过渡到一般渡到一般约约束束问题问题。1. 等式约束问题的最优性条件等式约束问题的最优性条件考考虑仅虑仅含等式含等式约约束的束的问题问题 （4.2） 这个问题的最

166、优性条件与求解方法在微积分中已从理这个问题的最优性条件与求解方法在微积分中已从理论上得到了解决，这就是论上得到了解决，这就是Lagrange定理和定理和Lagrange乘子乘子法。法。定理定理4.1（Lagrange定理）定理） P217Lagrange乘子法乘子法 定定义义函数函数称称为为Lagrange函数函数，其中，其中称称为为Lagrange乘子乘子，则则求解等式求解等式约约束束问题问题（4.2）等价于求解无）等价于求解无约约束束问题问题(4.4) Lagrange 函数（函数（4.4)的梯度是的梯度是其中其中最优性必要条件最优性必要条件及及下面的定理下面的定理给给出了（出了（4.2）

167、的最）的最优优性二性二阶阶充分条件。充分条件。定理定理4.2 P2182. 2. 不等式不等式约约束束问题问题的最的最优优性条件性条件（1 1）几何最）几何最优优性条件性条件下面将下面将给给出出约约束束问题问题 （4.7） 的最的最优优性条件。性条件。设设容容许许集仍用集仍用表示，即表示，即以下几个概念是以下几个概念是讨论讨论的基的基础础。定定义义4.1 对对于于约约束束问题问题（4.7），），设设 。若。若使得使得某个不等式某个不等式约约束有束有 ，则该则该不等式不等式约约束束称称为为是关于是关于容容许许点点 的的起作用起作用约约束束；否；否则则，若，若 则该则该不等式不等式约约束称束称为为

168、是关于是关于容容许许点点的的不起作用不起作用约约束束。 ，例如，例如， 不等式不等式约约束关于容束关于容许许集的任意内点都是不起作用集的任意内点都是不起作用约约束。束。只有容只有容许许集的集的边边界点才能使某个或某些不等式界点才能使某个或某些不等式约约束束变为变为起起作用作用约约束。束。定定义义4.2 设设是是中的非空集，且中的非空集，且 。对对于于，若当，若当 时时，对对于于，必有，必有 ，则则集合集合称称为为以以为顶为顶点的点的锥锥。若。若锥锥是凸集，是凸集，则则称称为为凸凸锥锥。 显显然，由然，由维维向量向量的全部非的全部非负组负组合构成合构成的集合的集合是一个以原点是一个以原点为顶为顶

169、点的点的凸凸锥锥。由于。由于这样这样的凸的凸锥锥的的边边界是界是（超）平面或直（超）平面或直线线，所以也称，所以也称为为由由 凸多面凸多面锥锥。张张成的成的定定义义4.3 设设是是中的非空集，且中的非空集，且 。对对于非零于非零 向量向量，若存在，若存在，当，当时时，必有，必有 ，则则称称为为点点 的容的容许许方向向量，其方向方向向量，其方向 称称为为点点的容许方向。由点的容许方向。由点 的全部容的全部容许许方向向量构成的方向向量构成的的的容容许许方向方向锥锥，记记作作集合称集合称为为点点引理引理4.3 设设 ；并；并设设当当时时，在点在点 处处可微，当可微，当时时， 在点在点处连续处连续。若

170、。若对对于所有于所有的的，向量，向量使得使得，则则是点是点的一个的一个容容许许方向向量。方向向量。证证 考考虑虑某个某个 。因。因为为，所以，所以是是在点在点处处的上升方向。根据定的上升方向。根据定义义1.10，存在，存在 ,例如，例如，当当时时，。 再考再考虑虑某个某个。因。因为为 ，且，且在点在点 处处连续连续，故存在，故存在，当，当时时，。取取，则则当当 时时，对对于所有的于所有的必有必有 ，即，即。根据定。根据定义义4.3，即，即是点是点的容的容许许方向向量。方向向量。 记记，则则依引理依引理4.3可知，可知，。由由这这个引理看到一个事个引理看到一个事实实，若，若仅仅使某个使某个约约束

171、，例如束，例如 ，变变成起作用成起作用约约束，且束，且，而其它，而其它约约束束是不起作用是不起作用约约束，束，则则 就是点就是点的一个容的一个容许许 方向向量。方向向量。换换句句话说话说，约约束曲面束曲面 把整个空把整个空间间分成分成总总是指向包含容是指向包含容许许集的那一集的那一侧侧。两部分，梯度两部分，梯度，由点由点的所有下降方向向量构成的集合称的所有下降方向向量构成的集合称为为点点下降方向下降方向锥锥。的的定理定理4.4 设设在点在点处处可微，可微，则则点点下降方向向量下降方向向量必必满满足足的的记记，则则定理定理4.4表明，表明，既是点既是点的下降方向的下降方向锥锥。显显然然是是中的半

172、空中的半空间间。 下面的定理下面的定理给给出的出的约约束束问题问题（4.7）的最）的最优优性条件是性条件是仅仅借助点集的概念借助点集的概念给给出的，所以称出的，所以称为为几何最几何最优优性条件性条件。定理定理4.5 在在约约束束问题问题（4.7）中，若）中，若是局部最是局部最优优点，点，处处的容的容许许方向方向锥锥和下降方向和下降方向锥锥的交集是空集。的交集是空集。则则点点这这个定理表明：个定理表明：在最在最优优点点处处，一定不存在下降容，一定不存在下降容许许方向。方向。 换换句句话说话说，在最，在最优优点点处处，或者不存在下降方向，或者，或者不存在下降方向，或者任何下降方向都不是容任何下降方

173、向都不是容许许方向。方向。定理定理4.6 在在问题问题（4.7）中，假）中，假设设：i）是局部最是局部最优优点，点，ii）在点在点处处可微；当可微；当时时，在点在点 可微，当可微，当时时，在点在点处连续处连续。那么，。那么，处处证证 根据引理根据引理4.3，若，若 ，则则， 从而从而。又根据定理。又根据定理4.5，有，有故必有故必有。 例例4.1 P222 定理定理4.5和定理和定理4.6给给出的最出的最优优性条件性条件仅仅仅仅是必要的，是必要的，而不是充分的。而不是充分的。习题习题4.6和和习题习题4.7可以可以说说明明这这一点。几何一点。几何最最优优性条件直性条件直观观易懂，但在易懂，但在

174、实际计实际计算中使用起来并不算中使用起来并不简简便。便。以下以下讨论讨论的的Fritz-John条件和条件和Kuhn-Tucker条件是条件是经经常用常用到的最到的最优优性条件。性条件。（2 2）Fritz-John条件条件 首先介首先介绍绍两个引理，两个引理，这这两个引理本身在最两个引理本身在最优优化理化理论论中中处处于很重要的地位。于很重要的地位。引理引理4.7（Farkas） 设设和和是是维维向量，向量，则满则满足足的向量的向量也也满满足足的充要条件是，存在非的充要条件是，存在非负负数数，使得，使得Farkas引理的几何解引理的几何解释释：Farkas引理指出，引理指出，向量向量与凸多面

175、与凸多面锥锥（个半空个半空间间的交集）中任意向量的交集）中任意向量都交成都交成锐锐角或直角的充要条件是，向量角或直角的充要条件是，向量 位于凸多面位于凸多面锥锥 之中。例如，之中。例如，见见上上图图， 位于位于中，它与中，它与中的任意向量中的任意向量都交成都交成锐锐角；角； 不在不在中，它就不与中，它就不与中的所有向量交成中的所有向量交成与与交成交成钝钝角。角。锐锐角或直角，如角或直角，如引理引理4.8（Gordan） 设设是是维维向量，向量，使得使得则则不存在向量不存在向量成立的必要条件是，存在不全成立的必要条件是，存在不全为为零的非零的非负负数数使得使得Gordan引理的几何意引理的几何意

176、义义：不存在向量不存在向量使得使得在几何上表示向量在几何上表示向量 的某一非的某一非负线负线性性组组合合为为零向量。例如，在左下零向量。例如，在左下图图中，取中，取 ，可使，可使 右下右下图图中，中，则则找不到不全找不到不全为为零的非零的非负负数数使得使得。 ；在；在定理定理4.9（Fritz-John） 在在问题问题（4.7）中，）中，设设是是在点在点处处可微。可微。，使得，使得局部最局部最优优解，解，那么，存在不全那么，存在不全为为零的零的实实数数（4.9） 其中其中称称为为互互补补松弛条件松弛条件。它表明：。它表明： 若若，即，即，则则必有必有；若；若，则则，即，即。必有必有 这个定理给

177、出了问题（这个定理给出了问题（4.7）的一个最优性必要条件。）的一个最优性必要条件。（4.9）称为问题（）称为问题（4.7）的）的Fritz-John条件，条件，满满足足Fritz-John条件的点称条件的点称为为Fritz-John点点。（。（4.9）中的）中的也称也称为为Lagrange乘子乘子。 例例4.2 考考虑约虑约束束问题问题试验证试验证是是Fritz-John点，点，不是不是Fritz-John点。点。解解 参看例参看例4.1，在点，在点处处，。计计算算取取，则则有有这这表明表明是是Fritz-John点。点。再考再考虑虑点点，这时这时。计计算算根据（根据（4.11），只），只须

178、说须说明不存在不全明不存在不全为为零的非零的非负负数数，使得，使得事事实实上，（上，（4.12）式可写）式可写为为（4.12） （4.13a） （4.13b） 由（由（4.13a）得）得，而由（，而由（4.13b）有）有 ，这这若取非零若取非零值值，则则必异号。必异号。 一关系表明，一关系表明，这这就是就是说说， 不可能存在不全不可能存在不全为为零的非零的非负负数数使得（使得（4.12）成立，）成立， 即即不是不是Fritz-John点。点。 Fritz-John条件条件仅仅是判断容是判断容许许点是否点是否为为最最优优点的必要点的必要条件，而不是充分条件。看下面的例条件，而不是充分条件。看下面

179、的例题题。例例4.3 考考虑约虑约束束问题问题解解 显显然然是此是此问题问题的唯一最的唯一最优优点。点。因因为为在直在直线线上，上，约约束束 关于所有容关于所有容许许点的梯度都等于零，所以当取点的梯度都等于零，所以当取时时，总总有有（4.14） 如果除去点如果除去点和点和点（这这两点的起作用两点的起作用约约束不止束不止） ，那么（，那么（4.14）说说明在直明在直线线其余的容其余的容许许点都点都满满足足Fritz-John条件。但除了条件。但除了其它的点全不是最其它的点全不是最优优点。点。上，上，外，外，（3）Kuhn-Tucker条件条件首先首先讨论讨论一个例一个例题题。例例4.4 P227

180、 总结总结：Fritz-John条件失效的一个原因是，起作用条件失效的一个原因是，起作用约约束函数的梯度束函数的梯度线线性相关。性相关。为为保保证证 一定在一定在Fritz-John条件条件中出中出现现，即必，即必须须保保证证 ，这这可以通可以通过过附加上起作用附加上起作用约约束函数的梯度束函数的梯度线线性无关的条件性无关的条件Kuhn和和Tucker提出提出的条件。的条件。实际实际上，上，为为了保了保证证 ，还还可以可以对对起作用起作用约约束函数束函数的梯度附加其它形式的条件，这样的一些条件在最优化理的梯度附加其它形式的条件，这样的一些条件在最优化理论中称为约束品性。论中称为约束品性。定理定

181、理4.10（Kuhn-Tucker） P227 在起作用在起作用约约束函数的梯度束函数的梯度线线性无关的前提下，公式性无关的前提下，公式（4.15）称）称为为Kuhn-Tucker条条件，而件，而满满足此条件的点称足此条件的点称为为Kuhn-Tucker点点。 Kuhn-Tucker条件的几何意条件的几何意义义：在公式（在公式（4.15）中，）中，删删去不起作用去不起作用约约束束项项（注意，它（注意，它们们的系数是的系数是 Kuhn-Tucker条件可条件可简简写写为为：存在：存在 ）,，使得，使得 （4.17） 该式在几何上表示：若该式在几何上表示：若 是问题（是问题（4.7）的最优点，则根

182、据）的最优点，则根据Farkas引理可知，目引理可知，目标标函数在函数在该该点的梯度必位于由起作用点的梯度必位于由起作用约约束函数的梯度所束函数的梯度所张张成的凸成的凸锥锥之中。例如，之中。例如，书书上上图图4-9显显示，在点示，在点 处处处处于由于由和和张张成的成的凸凸锥锥之中，因此之中，因此 满满足足Kuhn-Tucker条件，所以它有可能条件，所以它有可能是最是最优优点。如点。如图图所示，所示， 确确实实是最是最优优点。但在点。但在 处处，不在由不在由 和和所所张张成的凸成的凸锥锥之中，之中， Kuhn-Tucker条件，因此肯定不是最条件，因此肯定不是最优优点。点。就不就不满满足足例例

183、4.5 说说明例明例4.2中的中的是是KuhnTucker点。点。解解 由例由例4.2中的求解知中的求解知是是Fritz-John点，且点，且。又。又是是线线性无关的，所以由性无关的，所以由是是Kuhn-Tucker点。点。定理定理4.10可知，可知，3. 3. 一般一般约约束束问题问题的最的最优优性条件性条件 现现在在给给出一般出一般约约束束问题问题（4.1）的最）的最优优性条件。它也性条件。它也分分Fritz-John条件和条件和Kuhn-Tucker条件。条件。定理定理4.11（Fritz-John） P229定理定理4.12（Kuhn-Tucker） P229例例4.6 P229定理定

184、理4.13 在凸在凸规规划划问题问题（1.37）中，假）中，假设设是可微是可微是可微凹函数，是可微凹函数，是是线线性函数。性函数。是（是（1.37）的）的KuhnTucker点，点，则则是（是（1.37）的）的凸函数，凸函数，全局最全局最优优点。点。若若开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京4.6 外部罚函数法外部罚函数法 4.2-4.5节节介介绍绍的容的容许许方向法方向法对对于于带带有非有非线线性性约约束的最束的最优优化化问题问题的求解效果不甚理想。以下三的求解效果不甚理想。以下三节节将将针对针对一般一般约约束束最最优优化化问题问

185、题，给给出一种有效的求解方法出一种有效的求解方法罚罚函数法函数法。它。它的特点是根据的特点是根据问题问题的的约约束函数和目束函数和目标标函数，构造一个具有函数，构造一个具有“惩罚惩罚”效果的目效果的目标标函数序列，从而把函数序列，从而把对约对约束最束最优优化化问题问题的的求解求解转转化化为对为对一系列无一系列无约约束束问题问题的求解。的求解。这这种种“惩罚惩罚”策略，策略，对对在无在无约约束束问题问题求解求解过过程中企程中企图违图违反反约约束的那些迭代点束的那些迭代点给给予很大的目予很大的目标标函数函数值值，迫使，迫使这这一系列无一系列无约约束束问题问题的极小点的极小点（即迭代点）或者无限地向

186、容（即迭代点）或者无限地向容许许集靠近，或者一直保持在集靠近，或者一直保持在容容许许集内，直到收集内，直到收敛敛到到约约束束问题问题的极小点。的极小点。考考虑虑一般一般约约束最束最优优化化问题问题（4.67） 4.6-4.8节节将分将分别别介介绍绍三个三个罚罚函数方法。一是函数方法。一是外部外部罚罚函函数法数法（又称（又称外点法外点法）。其）。其惩罚惩罚方式是方式是对对那些那些违违反反约约束的点束的点在目在目标标函数中加入相函数中加入相应应的的“惩罚惩罚”，而，而对对容容许许点不予点不予惩罚惩罚。特点是迭代点一般在容特点是迭代点一般在容许许集外移集外移动动。二是。二是内部内部罚罚函数法函数法（

187、又称（又称内点法内点法）。它）。它仅仅适用于具有不等式适用于具有不等式约约束的最束的最优优化化问问题题。其。其惩罚惩罚方式是方式是对对那些企那些企图图从内部穿越容从内部穿越容许许集集边边界的点界的点（容（容许许集的内点）在目集的内点）在目标标函数中加入相函数中加入相应应的的“障碍障碍”，而且，而且点距点距边边界越近，障碍也越大，界越近，障碍也越大，对对于于边边界上的点界上的点给给予无予无穷穷大大的障碍，从而保的障碍，从而保证证迭代点一直在容迭代点一直在容许许集内移集内移动动。三是。三是乘子乘子法法，它是外部，它是外部罚罚函数法的一种改函数法的一种改进进方法。其方法。其惩罚惩罚方式是在方式是在约

188、约束束问题问题的的Lagrange函数中加入相函数中加入相应应的的惩罚惩罚，这样这样既能保既能保证证迭代点会收迭代点会收敛敛到到约约束束问题问题的极小点，更重要的是能保的极小点，更重要的是能保证证数数值计值计算的算的稳稳定性。定性。本本节节首先首先讨论讨论外部外部罚罚函数法。函数法。1. 算法的构成算法的构成首先讨论一个例子。求解首先讨论一个例子。求解（4.68） 如如图图所示。此所示。此问题问题的容的容许许集集是直是直线线图图解法或解法或Lagrange乘子法不乘子法不难难求出它的极小点是求出它的极小点是.。用。用 根据前面提出的根据前面提出的惩罚惩罚策略，即策略，即对对容容许许点不予点不予

189、“惩罚惩罚”，而，而对对非容非容许许点点则给则给予正无予正无穷穷大的大的“惩罚惩罚”，设设法法将将约约束束问题问题（4.68）转转化化为为无无约约束束问问题题。 （4.69） 那么无那么无约约束束问题问题与（与（4.68）等价。）等价。问题问题是是的特性太坏，无法用的特性太坏，无法用第第3章章讲过讲过的任何一种无的任何一种无约约束方法求解它。考束方法求解它。考虑虑“相近相近”函数函数（4.70）其中其中是任意是任意给给定的正数。定的正数。是可微函数，所以是可微函数，所以可以用第可以用第3章章讲讲的无的无约约束方法求解它。求解以（束方法求解它。求解以（4.70）为为目目标标函数的无函数的无约约束

190、束问题问题，其（解析）最，其（解析）最优优解解 虽虽然不是（然不是（4.68）的容）的容许许点，但随着点，但随着的增大，有的增大，有。 综综上所述，上所述，为为了求解了求解约约束束问题问题（4.67），可以采用取），可以采用取如下的如下的惩罚惩罚策略：策略：给给目目标标函数加上由函数加上由约约束函数构造的束函数构造的惩罚惩罚项项。惩罚项惩罚项要具要具备备两个特点：两个特点：）包含有取包含有取值值越来越大的正因子越来越大的正因子； ）对对于容于容许许点，点，惩罚项惩罚项取取值为值为零；零；对对于非容于非容许许点，点，惩罚项惩罚项取取值为值为正。正。以下讨论一般情况。对于仅含有等式约束的问题以下讨

191、论一般情况。对于仅含有等式约束的问题（4.71） 可以采取如下的可以采取如下的惩罚惩罚策略策略（4.72） 仿照上述分析，对于仅含有不等式约束的问题仿照上述分析，对于仅含有不等式约束的问题（4.73） 可采取的惩罚策略为可采取的惩罚策略为（4.74） 其中其中是是阶跃阶跃函数，即函数，即（4.75） 于是于是 进而进而 是（是（4.73）的容）的容许许集。此式集。此式说说明（明（4.74）符合前面）符合前面拟订拟订的的惩罚惩罚策略。策略。 其中其中 最后，最后，对对于同于同时时具有等式具有等式约约束和不等式束和不等式约约束的一般束的一般约约束束问题问题（4.67），可采取如下的），可采取如下的

192、惩罚惩罚策略策略（4.76 )其中其中（4.77） 称称为约为约束束问题问题(4.67)的的罚罚函数函数。显显然有然有（4.78） 这这里的里的是（是（4.67）的容）的容许许集。集。此外，把此外，把称称为约为约束束问题问题（4.67）的）的增广目增广目标标称称为为罚罚因子因子， 称称为为惩罚项惩罚项。函数函数 ，其中的，其中的 于是，由于是，由约约束最束最优优化化问题问题（4.67）引出如下的无）引出如下的无约约束束最最优优化化问题问题（4.79） 定理定理4.22将指出，当将指出，当 固定固定时时，无，无约约束束问题问题（4.79）的极小点的极小点有可能有可能是是约约束束问题问题（4.67

193、）的极小点。）的极小点。 定理定理4.22 对对于某个于某个给给定的定的，若，若是无是无约约束束问题问题也是也是约约束束问题问题（4.67）的极小点）的极小点恰是（恰是（4.67）的容）的容许许点。点。（4.79）的极小点，）的极小点，则则的充要条件是的充要条件是证证 必要性是必要性是显显然的。因然的。因为为极小点是容极小点是容许许点。点。充分性充分性 设设，这这里的里的是是约约束束问题问题（4.67）的容的容许许集。那么集。那么对对于于，总总有有所以所以也是也是约约束束问题问题（4.67）的极小点。）的极小点。 在在实际实际的算法中，的算法中，取取为为一个一个趋趋于正无于正无穷穷大的正数大的

194、正数，并，并对对依次求解无依次求解无约约束束问题问题把把该该定理定理说说明明,若由无若由无约约束束问题问题(4.79)解出的极小点解出的极小点属于（属于（4.67）的容）的容许许集集，则则它就是它就是约约束束问题问题（4.67）的）的一般不属于一般不属于。而若。而若则则就一定不是就一定不是约约束束问题问题（4.67）的极小点。）的极小点。这时这时，应该应该，再重新求解无，再重新求解无约约束束问题问题（4.79），新的极小点），新的极小点极小点。极小点。这时这时只需求解一次无只需求解一次无约约束束问题问题。但。但实际实际上，上，这这种种有利的情况很少有利的情况很少发发生，即生，即，增大增大向容向

195、容许许集集进进一步靠近，即向（一步靠近，即向（4.67）的极小点）的极小点进进一步靠近。一步靠近。将将 序列序列即即（4.80 )由此得到极小点序列由此得到极小点序列 。在。在4.6.2中将中将证证明，如果明，如果这这个个序列收序列收敛敛，则则必收必收敛敛于于约约束束问题问题（4.67）的极小点）的极小点 约束约束问题问题（4.67）的方法称）的方法称为为外部外部罚罚函数法函数法或或外点法外点法。这种这种通通过过求解一系列无求解一系列无约约束束问题问题（4.80）而达到求解无）而达到求解无 像像这样这样，通，通过过求解一系列无求解一系列无约约束最束最优优化化问题问题来求解来求解约约束最束最优问

196、题优问题的方法称的方法称为为序列无序列无约约束极小化技束极小化技术术（Sequential Unconstrained Minimization Technique，简简记为记为SUMT）。算法算法4.6( (外部外部罚罚函数法函数法) ) P269算法算法说说明：明：例例4.12 用外部用外部罚罚函数法求解函数法求解(1) (1) (2)(2) 2. 收收敛敛性性引理引理4.23 对对于由算法于由算法4.6所所产产生的序列生的序列，总总有有（4.82） （4.83） （4.84） 定理定理4.24 设设和和 都是都是 上的上的连续连续函数，函数，则则由算法由算法4.6所所产产生的序列生的序列

197、的任一聚点必是的任一聚点必是约约束束问题问题（4.67）的极小点。）的极小点。4.7 内部罚函数法内部罚函数法 外部外部罚罚函数法所函数法所产产生的迭代点一般不是容生的迭代点一般不是容许许点，所以点，所以往往只是近似地往往只是近似地满满足足约约束条件，束条件，这样这样的的结结果果对对于那些要求于那些要求严严格格满满足足约约束条件的束条件的实际问题实际问题是无法接受的。此外，是无法接受的。此外，对对于于有些有些约约束束问题问题，其目，其目标标函数在容函数在容许许集外可能无定集外可能无定义义，因此，因此也无法使用外部也无法使用外部罚罚函数法。函数法。为为保保证证迭代点迭代点总总是容是容许许点，可点

198、，可以采用如下的内部以采用如下的内部罚罚函数法。函数法。1. 算法的构成算法的构成 内部罚函数法的初始点必须是容许点，迭代点在容许内部罚函数法的初始点必须是容许点，迭代点在容许集的内部移动。基本想法是，对越接近容许集边界的（容集的内部移动。基本想法是，对越接近容许集边界的（容许）点施加越大的惩罚，对边界上的点干脆施加无穷大的许）点施加越大的惩罚，对边界上的点干脆施加无穷大的惩罚。这好比在容许集的边界上筑就了一道高墙，阻碍迭惩罚。这好比在容许集的边界上筑就了一道高墙，阻碍迭代点穿越边界，把迭代点封闭在容许集内。根据这个想法，代点穿越边界，把迭代点封闭在容许集内。根据这个想法，内部罚函数法就仅适用

199、于具有不等式约束的问题，内部罚函数法就仅适用于具有不等式约束的问题，而且容许集的内点集合必须是非空集合；否则，会因为容而且容许集的内点集合必须是非空集合；否则，会因为容许点全被加上无穷大的惩罚而失去惩罚的意义。许点全被加上无穷大的惩罚而失去惩罚的意义。考考虑虑不等式不等式约约束束问题问题（4.94） 构造如下的增广目构造如下的增广目标标函数就可以函数就可以实现实现上面的想法。上面的想法。设设（4.95） 其中其中（4.96） 称称为为障碍函数障碍函数；仍称仍称为为罚罚因子因子；惩罚项惩罚项。若。若 称称为为是（是（4.94）的容）的容许许集集的内点，的内点，则惩罚则惩罚函数函数的的值值是有限的

200、正数；当是有限的正数；当由内部接近由内部接近边边界界时时，则则至少有一个至少有一个约约束函数，束函数， 例如第例如第个，个，将将趋趋于零，于零， 于是于是必将必将趋趋于正无于正无穷穷大。大。这这正符合上述的正符合上述的惩罚惩罚思想。思想。 现现在固定在固定,求解以求解以(4.95)为为目目标标函数的无函数的无约约束束问题问题（4.97） 如果把初始点取如果把初始点取为为容容许许集集的内点，按照的内点，按照的的结结构和无构和无内，内，。约约束下降迭代算法的特性，那么迭代点必将都在束下降迭代算法的特性，那么迭代点必将都在因此最后求得的极小点也必将属于因此最后求得的极小点也必将属于例如，例如，对对于

201、于约约束束问题问题构造如下的增广目标函数构造如下的增广目标函数书书上上图图4-21画出了在容画出了在容许许集上目集上目标标函数函数 和和惩罚项惩罚项以及由以及由这这两者合成的增广目两者合成的增广目标标函数函数 的曲线的曲线 。这这里，里，（在容（在容许许集内）的极小点我集内）的极小点我们们通通过过求求导导数的数的方法方法获获得。令得。令由此解出最由此解出最优优解解从从书书上上图图4-21容易看出，原容易看出，原约约束束问题问题的极小点是的极小点是而增广目而增广目标标函数的极小点是函数的极小点是。这这个例子个例子说说明，明，对对于固定的于固定的 ，无，无约约束束问题问题（4.97）的极小点一般不

202、是）的极小点一般不是约约束束则则。这这个个结论结论具有一般性具有一般性。 问题问题（4.94）的极小点。但是）的极小点。但是这这个例子个例子显显示，若令示，若令，在在实际实际的算法中，把的算法中，把取取为为一个一个趋趋于零的正数序列于零的正数序列,求解一系列无求解一系列无约约束束问题问题,即即对对,依次依次求解求解（4.98） 由此得到极小点序列由此得到极小点序列 。在。在4.7.2中将中将证证明，明，这这个序个序列若收列若收敛敛，则则必收必收敛敛于于约约束束问题问题（4.94）的极小点）的极小点 。这这种通种通过过求解一系列无求解一系列无约约束束问题问题（4.98）而达到求解）而达到求解约约

203、束束问问题题（4.94）的方法称）的方法称为为内部内部罚罚函数法函数法或或内点法内点法。障碍函数除（障碍函数除（4.96）外）外还还可以取可以取为为其中其中由（由（4.75）定）定义义。算法算法4.7（内部（内部罚罚函数法）函数法） P277几点几点说说明：明：例例 4.14 用内部用内部罚罚函数法求解函数法求解其中其中是非是非负负常数。常数。例例 4.15 用内部用内部罚罚函数法求解函数法求解解解 增广目增广目标标函数函数为为令令于是，于是，问题问题的最的最优优解解为为2. 收敛性收敛性引理引理4.25 对对于由算法于由算法4.7所所产产生的序列生的序列，总总有有（4.99） （4.100）

204、 （4.101） 其中其中。定理定理4.26 设设都是都是上的上的连续连续函数，函数，的任一聚点必是的任一聚点必是约约束束问题问题则则由算法由算法4.7所所产产生的序列生的序列（4.94）的极小点。）的极小点。 由于内部由于内部罚罚函数法不能函数法不能处处理等式理等式约约束，且束，且寻寻求初始容求初始容许许点的点的计计算量往往太大。因此在算量往往太大。因此在实际计实际计算中，人算中，人们们往往将往往将内部内部罚罚函数与外部函数与外部罚罚函数法函数法结结合起来，形成所合起来，形成所谓谓的的混合混合罚罚函数法函数法。4.8 乘子法乘子法 乘子法是乘子法是针对针对外部外部罚罚函数法的一种改函数法的一

205、种改进进方法。由于外方法。由于外部部罚罚函数法随着函数法随着罚罚因子的增大，增广目因子的增大，增广目标标函数的函数的Hesse矩矩阵阵条件数条件数变变得越来越坏，从而得越来越坏，从而导导致在致在实际计实际计算中，数算中，数值计值计算的算的稳稳定性定性变变得越来越差，得越来越差，难难以精确求解。乘子法是在以精确求解。乘子法是在约约束束问题问题的的lagrange函数中加入相函数中加入相应应的的惩罚惩罚，使得在求解系，使得在求解系列无列无约约束束问题时问题时，罚罚因子不必因子不必趋趋于无于无穷穷大就能求到大就能求到约约束束问问题题的最的最优优解，而且数解，而且数值计值计算的算的稳稳定性也能得到很好

206、的保定性也能得到很好的保证证。理理论论与与计计算算实实践皆表明，乘子法践皆表明，乘子法优优于外部于外部罚罚函数法。函数法。1. 等式等式约约束的情形束的情形首先介首先介绍绍Hesternes（1969）乘子法乘子法，简简称称H乘子法。乘子法。考考虑虑等式等式约约束束问题问题（4.71），将其写成向量形式），将其写成向量形式为为（4.109） 其中其中都是二次都是二次连续连续可微函数。可微函数。设设。（4.109）的）的Lagrange函数是函数是（4.110） 设设是（是（4.109）的极小点，）的极小点，是相是相应应的的Lagrange乘子。乘子。根据定理根据定理4.1，则则有有（4.111

207、） （4.112） 注意到，注意到，对对于于，都有，都有，因此，因此由此可由此可见见，（，（4.109）与如下）与如下约约束束问题问题等价等价（4.113） 这说这说明可以通明可以通过过求解（求解（4.113）达到求解（）达到求解（4.109）的目的。）的目的。对对（4.113）使用外部）使用外部罚罚函数法，其增广目函数法，其增广目标标函数函数为为（4.114） 应该应该注意到，注意到，其其实实是未知向量，所以是未知向量，所以实际实际上不能求出上不能求出的极小点。下面将指出，在求的极小点。下面将指出，在求的同的同时时，采用，采用.这这就是乘子法的基本思想。就是乘子法的基本思想。 迭代的方法也可

208、以同迭代的方法也可以同时时求出求出该该法也因此而得名。法也因此而得名。实际实际上，用乘子法求解（上，用乘子法求解（4.109）时时的增广目的增广目标标函数是函数是（4.115） 这这个函数比（个函数比（4.72）具有更好的性）具有更好的性质质。首先。首先证证明一个引理。明一个引理。引理引理4.27 设设是是对对称矩称矩阵阵， 是是矩矩阵阵。的非零向量的非零向量都使得都使得那么必存在非那么必存在非负负数数，当，当时时，使得矩，使得矩阵阵在在上皆正定。上皆正定。如果所有如果所有满满足足，定理定理4.28 在在约约束束问题问题(4.109)中，如果最中，如果最优优解解和和Lagrange乘子乘子满满

209、足由定理足由定理4.2给给出的出的，当，当时时，使得，使得也是也是的的严严格局部格局部 极小点。极小点。件，那么就存在非件，那么就存在非负负数数二二阶阶充分条充分条 该该定理表明定理表明，对对（4.113）使用外部）使用外部罚罚函数法函数法时时，只要，只要罚罚因子不小于某个潜在的非因子不小于某个潜在的非负负数，那么数，那么 （局部）极小点就（局部）极小点就有可能有可能是（是（4.109）的（局部）极小点。）的（局部）极小点。的的现现在来求解以（在来求解以（4.115）为为目目标标函数的无函数的无约约束极小化束极小化问题问题（4.121） 下面的定理将指出（下面的定理将指出（4.109）与（）与

210、（4.121）的关系。）的关系。定理定理4.29 设对设对于于给给定的参数定的参数和和，是是(4.121)的的是（是（4.109）的最）的最优优解，且解，且为为相相应应的的的充要条件是的充要条件是，即，即。最最优优解。那么解。那么Lagrange乘子向量乘子向量定理定理4.29结结合定理合定理4.28说说明：明：如果参数如果参数恰好取恰好取为为了了，又取了，又取了，然后求解（，然后求解（4.121）得出的最）得出的最优优解解有恰好是（有恰好是（4.109）的容）的容许许点，那么点，那么就必是（就必是（4.109）的）的最最优优解。解。在在实际计实际计算中，算中，是通是通过过迭代的方式迭代的方式

211、获获得的。其迭代得的。其迭代公式推公式推导导如下：如下：对对于于给给定的定的，设设是（是（4.121），即），即（4.123 ）的极小点，那么利用（的极小点，那么利用（4.119），），应应有有（4.124） 另一方面，在（另一方面，在（4.109）的最）的最优优点点处处，根据（，根据（4.111），），应应有有（4.125） 若若设设是列是列满满秩矩秩矩阵阵，则则使用最小二乘法，由上式使用最小二乘法，由上式可求出可求出（参看推参看推论论3.17）。若。若，则则当当充分大充分大时时，也将是列也将是列满满秩矩秩矩阵阵。于是，再次使用最小二乘法，。于是，再次使用最小二乘法，由（由（4.124）又可

212、得）又可得比比较较以上两式可知，当以上两式可知，当时时，。因此，有理由采用如下的迭代公式求因此，有理由采用如下的迭代公式求，即，即定理定理4.29实际实际上上还给还给出了出了H乘子法的乘子法的终终止准止准则则，即当，即当充分小充分小时时，迭代，迭代终终止。而一旦在迭代中止。而一旦在迭代中 不收不收敛敛不不够够大，大，后，再迭代。收后，再迭代。收敛敛的快慢可用比的快慢可用比值值或收或收敛敛的太慢，根据定理的太慢，根据定理4.28可知，可知，这这表明表明因此增大因此增大来度量。来度量。 算法算法4.8( (等式等式约约束束问题问题的的H乘子法乘子法) ) P285例例4.16 用用H乘子法求解等式

213、乘子法求解等式约约束束问题问题（4.68）。）。解解 增广目增广目标标函数函数为为令令由此解出由此解出（4.126） 把把换为换为，再把，再把和和的表达式代入下式，得到乘子的表达式代入下式，得到乘子迭代公式迭代公式由此看到，只要由此看到，只要，序列，序列就收就收敛敛，而且，而且越大，越大，上式两，上式两边边取取的极限，就有的极限，就有收收敛敛越快。因此，越快。因此，对对于任意于任意给给定的正数定的正数由此解出由此解出。把。把代到（代到（4.126），即得最），即得最优优解解。从（从（4.127）的）的计计算算结结果可以看出，果可以看出， 与与的取的取值值无无的取的取值值保保证证收收敛敛。这这很

214、容易理解。很容易理解。关，只要求关，只要求因因为为若不然的若不然的话话，就会有无数个，就会有无数个Lagrange乘子，而乘子，而这显这显然然是不可能的。是不可能的。下面再下面再简单简单介介绍绍Powell(1969)乘子法，乘子法，简简称称P乘子法。乘子法。 Powell乘子法与乘子法与H乘子法相比，唯一的差乘子法相比，唯一的差别别在于它在于它对对每一个每一个约约束使用了不同的束使用了不同的罚罚因子，亦即因子，亦即处罚处罚因因“人人”而异。而异。理理论论推推导过导过程与程与H乘子法的相似，乘子法的相似，这这里从略。里从略。Powell乘子乘子法的增广目法的增广目标标函数函数为为（4.128）

215、 算法算法4.9（等式等式约约束束问题问题的的P乘子法乘子法） P286计计算算实实践表明，践表明，P乘子法比乘子法比H乘子法效果好。乘子法效果好。2. 不等式不等式约约束的情形束的情形 这这里将要介里将要介绍绍的是的是Rockafellar（1973）乘子法乘子法，它是，它是把把H乘子法巧妙地用到不等式乘子法巧妙地用到不等式约约束束问题问题上去而得到的求解上去而得到的求解仅仅含不等式含不等式约约束束问题问题（4.73）的一种方法。）的一种方法。考虑不等式约束问题考虑不等式约束问题（4.129） 引入引入辅辅助助变变量量，把（，把（4.129）转转化化为为与其等价与其等价的等式的等式约约束束问

216、题问题（4.130） 这时这时，可使用前述，可使用前述H乘子法求解（乘子法求解（4.130），其增广目），其增广目标标函函数数为为（4.131) 求求的极小。由于的极小。由于变变量量独立，所以求独立，所以求的极的极小可分步小可分步进进行，即行，即实际实际上，上， 关于关于的极小可以用的极小可以用显显示表出。因此，示表出。因此，将（将（4.129）的增广目）的增广目标标函数定函数定义为义为（4.132） 用解析法求解（用解析法求解（4.132）。令）。令即即经整理，得经整理，得（4.133） 由（由（4.133），），对对，必有，必有因此，因此， （4.134)进而进而 代回到（代回到（4.13

217、2）中，即得）中，即得对对于于给给定的参数定的参数和和，设设是是的极小点，并定的极小点，并定义义则则乘子迭代公式乘子迭代公式为为 即即终止准则为终止准则为3. 一般一般约约束的情形束的情形对于一般约束问题对于一般约束问题 仿照前面的推仿照前面的推导导，可得增广目，可得增广目标标函数函数为为（4.135） 乘子迭代公式为乘子迭代公式为其中其中代表的是第代表的是第个等式个等式约约束所束所对应对应的的Lagrange乘子，乘子，代表的是第代表的是第个不等式个不等式约约束束对应对应的的Lagrange乘子，乘子，显显然然。算法算法4.10（一般约束问题的（一般约束问题的H乘子法）乘子法） P289 例

218、例4.17 用用H乘子法求解乘子法求解约约束束问题问题 罚罚函数法由于原理易懂、程序函数法由于原理易懂、程序简单简单，人，人们乐们乐于使用。于使用。尤其是乘子法克服了因尤其是乘子法克服了因罚罚因子因子趋趋于无于无穷穷而引起的增广目而引起的增广目标标函数形函数形态变态变坏的缺点，成坏的缺点，成为为求解求解约约束束问题问题的的较较好的方法之好的方法之一。一。开始开始 最优化方法最优化方法（最优化课件研制组）（最优化课件研制组）退出退出主讲：张主讲：张 京京4.2 Zoutendijk容容许许方向法方向法 容容许许方向法是求解方向法是求解约约束最束最优优化化问题问题得一得一类类基本方法。基本方法。这

219、类这类方法一般先从方法一般先从线线性性约约束束问题问题开始开始讨论讨论，然后再推广到，然后再推广到非非线线性性约约束束问题问题。它的基本迭代格式是。它的基本迭代格式是从从容容许许点点开始迭代，开始迭代，设设已迭代到已迭代到容容许许点点;在点在点用用某种方法某种方法确定一个确定一个下降容下降容许许方向方向 ;从点从点出出发发，在，在方向上方向上寻寻找找满满足足的新的的新的容容许许迭代点迭代点；判断判断的最的最优优性。若性。若满满足足终终止条件，止条件，则则打印打印，计计算算终终止；否止；否则则，置，置，然后，然后转转。 简单简单地地说说，容，容许许方向法是沿下降容方向法是沿下降容许许方向搜索并保

220、持方向搜索并保持新迭代点新迭代点为为容容许许点的一种迭代方法。下降容点的一种迭代方法。下降容许许方向确定方方向确定方法的不同法的不同对应对应着不同的容着不同的容许许方向法。以下两方向法。以下两节节将介将介绍绍2个个容容许许方向法。方向法。 第一，第一，Zoutendijk容容许许方向法。方向法。这这种方法通种方法通过过在迭代在迭代点点处处的容的容许许方向方向锥锥中中寻寻找最速下降方向的找最速下降方向的线线性性规规划来确定划来确定下降容下降容许许方向。方向。 第二，第二，Rosen梯度投影法。梯度投影法。该该法通法通过过把在迭代点把在迭代点处处的的目目标标函数的函数的负负梯度向起作用梯度向起作用

221、约约束超平面的交集投影来确定束超平面的交集投影来确定下降容下降容许许方向。方向。首先首先讨论讨论Zoutendijk容容许许方向法。方向法。1. 线线性性约约束的情形束的情形考考虑线虑线性性约约束最束最优优化化问题问题（4.25） 其中其中是是矩矩阵阵， 是是矩矩阵阵， 是是维维向量，向量，是是维维向量，而向量，而是可微函数。是可微函数。（1）下降容）下降容许许方向的确定方向的确定下面的定理给出了确定容许方向的理论基础。下面的定理给出了确定容许方向的理论基础。 定理定理4.14 在在约约束束问题问题（4.25）中，假）中，假设设：）是容是容许许点；点；）适当适当调换调换的行向量与的行向量与的相

222、的相应应分量（分量（设设所得所得与与表示）表示）,然后分解然后分解，相，相应应，使得，使得。矩矩阵阵和向量仍用和向量仍用地分解地分解那么，非零向量那么，非零向量为为点点的容的容许许方向向量的充要条件是方向向量的充要条件是满满足足定理定理4.14表明表明，若，若 是容是容许许点，点，则满则满足足的非零向量的非零向量就是点就是点的容的容许许方向向量。方向向量。 若若还满还满足足，那么，那么就是下降容就是下降容许许方向向量。方向向量。因此，因此，为为确定点确定点的下降容的下降容许许方向向量方向向量，一个很，一个很自然的想法是，在自然的想法是，在满满足足的条件下，使的条件下，使取极小取极小值值。但是，

223、必。但是，必须对须对 的的“长长度度”加上某种加上某种满满足足且且 限制。限制。这这是因是因为为若若则对则对于任意正数于任意正数，也也满满足足这这些式子，且些式子，且，导导致无法确定致无法确定。 ，综综上，我上，我们现们现在可以考在可以考虑虑如下极小化如下极小化问题问题 注意到注意到这这是具有非是具有非线线性性约约束的束的问题问题，求解，求解难难度度远远比比（4.25）还还大。大。为为此，考此，考虑虑用相近的用相近的线线性性规规划划（4.28) 来确定（来确定（4.25）在点）在点处处的下降容的下降容许许方向向量，其中方向向量，其中是分量全是分量全为为1的的维维向量，即向量，即 。因。因为为

224、是（是（4.28）的容）的容许许解，且其函数解，且其函数值为值为0，所以（，所以（4.28）的最）的最优值优值非正。非正。若最若最优值为负优值为负，则则最最优优解解 就是点就是点 的一个的一个下降容下降容许许方向向量方向向量。最。最优值为优值为0的情形的情形见见后面的内容（后面的内容（3）。）。（2）直线搜索）直线搜索为为求新的迭代点求新的迭代点 ，以从点，以从点出出发发沿下降容沿下降容许许方向方向作直作直线线搜索，即搜索，即由于容由于容许许方向法本身要求新迭代点方向法本身要求新迭代点也必也必须须是容是容许许点，点， 所以最所以最优优步步长长因子因子必必须须受（受（4.25）约约束的限制。因此

225、，束的限制。因此，该该直直线线搜索搜索实际实际上上是是如下如下有有约约束的一元函数极小化束的一元函数极小化问题问题 （4.29） （4.29）可以化）可以化简简。首先，由。首先，由和和得知，得知，总总有有 对对于任意的于任意的，这说这说明（明（4.29）的第）的第和和 2个个约约束是多余的；其次，由束是多余的；其次，由得知，得知，,总总有有对对于，于，又，又说说明（明（4.29）的）的第第1个个约约束中的束中的这这一部分也是多余的。于是，（一部分也是多余的。于是，（4.29）可）可化化简为简为 （4.30） 现现在来求（在来求（4.30）的容）的容许许区区间间。设设其中其中和和都是与都是与维维

226、数（数（设为设为）相等的向量。于是，）相等的向量。于是，可将（可将（4.30）中的第）中的第1个个约约束改写束改写为为（4.31） 注意到注意到，便知，便知。当。当时时，对对于于（4.31）显显然然总总成立，在成立，在这这种情况下，种情况下，； 而当而当 时时（此（此时时至少有一个至少有一个），取，取，对对于于，（，（4.31）也）也总总成立。成立。 综综上所述，最上所述，最优优步步长长因子因子是如下一元函数极小化是如下一元函数极小化问题问题的最的最优优解，其中解，其中（4.32） （3）终终止准止准则则计算的终止准则由下面的定理给出。计算的终止准则由下面的定理给出。定理定理4.15 在在约约

227、束束问题问题（4.25）中，假）中，假设设：）是容是容许许点；点；） 分解分解，相，相应应地分解地分解，使得，使得；）和和的行向量的行向量线线性无关；性无关；）是是线线性性规规划（划（4.28）的最）的最优优解。解。那么，那么， 为为Kuhn-Tucker点的充要条件是点的充要条件是。（4）算法）算法算法算法4.1（Zoutendijk法法） P235（5）例）例题题 P2352. 非线性约束的情形非线性约束的情形考虑仅带有非线性不等式约束的最优化问题考虑仅带有非线性不等式约束的最优化问题（4.34） （1）下降容许方向的确定）下降容许方向的确定设设是容是容许许点。根据定理点。根据定理4.4可

228、知，可知，满满足足（4.35） 的的是点是点的下降方向向量。的下降方向向量。设设。根据引理。根据引理4.3可知，可知，满满足足（4.36） 的的是点是点的容的容许许方向向量。因此，同方向向量。因此，同时满时满足（足（4.35）和）和就是点就是点的下降容的下降容许许方向向量。方向向量。（4.36）的点）的点对对如果附加限制：如果附加限制：，并，并对对和和（对对于所有的于所有的）的上界的上界( (设设用用 表示表示) )取极小取极小，即，即（4.38） 来确定下降容来确定下降容许许方向向量。若用方向向量。若用表示（表示（4.38）的最）的最优优时时， 是点是点的一个下降容的一个下降容许许解，解，则

229、则容易容易证证明，当明，当方向向量。方向向量。（2）直线搜索）直线搜索 为为了确定新迭代点了确定新迭代点 ，可以从点，可以从点 出出发发，沿，沿 方向方向作作受非受非线线性性约约束束的直的直线线搜索。搜索。这这里的步里的步长长因子因子 的上界的上界 已不具有已不具有线线性性约约束情形束情形时时的的显显示示计计算公式，它需要根据新算公式，它需要根据新迭代点的容迭代点的容许许性，通性，通过过直直线线搜索技搜索技术术来确定，即来确定，即 然后求解然后求解得最得最优优解解，从而得到新迭代点，从而得到新迭代点。（3）终终止准止准则则计算的终止准则可由下面的定理给出。计算的终止准则可由下面的定理给出。定理

230、定理4.16 在在约约束束问题问题（4.34）中，假）中，假设设：）是容是容许许点；点；）是是线线性性规规划（划（4.38）的最）的最优优解。解。那么，那么， 为为Fritz-John点的充要条件是点的充要条件是。（4）算法）算法算法算法4.2（Topkis-Veinott法）法） P424 需要注意的是，由于需要注意的是，由于约约束函数的非束函数的非线线性，使得性，使得该该方法方法在具体在具体实现实现上要比上要比线线性性约约束情形束情形时时复复杂杂的多。如，受的多。如，受计计算算误误差的影响，可能不能保差的影响，可能不能保证证迭代点迭代点还还是容是容许许点。算法的有点。算法的有效性因此会打折

231、扣。效性因此会打折扣。（5）例）例题题例例4.8 P243开始开始 最优化方法（最优化课件研制组）退出退出主讲：张 京 第第2第第4章章讨论讨论的都是具有的都是具有单单一目一目标标函数的最函数的最优优化化问问题题。实际实际中，中，还还会遇到同会遇到同时时追求多个目追求多个目标标的最的最优优化化问题问题。例如，例如，对对于一个生于一个生产过产过程，程，总总是期望高是期望高产产出，同出，同时还时还要求要求少用料、省工少用料、省工时时等等。像等等。像这样这样有多个目有多个目标标的最的最优优化化问题问题称称为为多目多目标规标规划划。自二十世。自二十世纪纪70年代以来，年代以来，对对多目多目标规标规划的

232、划的研究开始广泛起来，所研究开始广泛起来，所获获成果已成果已对现对现代代经济经济、政治、科技、政治、科技和和军军事等方面事等方面产产生重要影响。生重要影响。这这里将介里将介绍绍多目多目标规标规划的数划的数学模型、有关概念，以及基本的求解方法。学模型、有关概念，以及基本的求解方法。第五章 多目标规划5.1 数学模型数学模型例例5.1 P298例例5.2 P298多目多目标标最最优优化化问题问题的数学模型的数学模型的一般形式的一般形式为为（5.1） 如设如设则则（5.1）将可）将可简单简单地表示成地表示成（5.3） （5.3）是多目）是多目标问题标问题的的向量极小化模型向量极小化模型，其中，其中v

233、是是vector为为容容许许集。集。称称为为向量目向量目标标函数函数；称称为为分量目分量目标标函数函数。（向量）的字（向量）的字头头， 如果（如果（5.1）中的所有函数都是）中的所有函数都是线线性的，那么通性的，那么通过变换过变换，（5.1）可写成如下形式）可写成如下形式（5.4） 这这是多目是多目标线标线性性规规划的划的标标准形式，其中准形式，其中是矩矩阵阵。5.2 解的概念与性解的概念与性质质 与与单单目目标标最最优优化化问题问题相比，由于目相比，由于目标标函数不再是函数不再是单单一一的，因此多目的，因此多目标标最最优优化化问题问题的最的最优优解概念解概念变变得复得复杂杂起来，起来，并并产

234、产生了各种意生了各种意义义下的下的“最最优优”概念。概念。定定义义5.1 考考虑问题虑问题（5.3）。若存在）。若存在，使得，使得对对于于，都有，都有（5.5） 则称称为为（5.3）的）的绝对绝对最最优优解解。所有。所有绝对绝对最最优优解的集合解的集合或。称称为为绝对绝对最最优优解集解集，记记作作注意，（注意，（5.5）等价于）等价于例例5.3 P300 在在实际实际中，多目中，多目标标最最优优化化问题问题存在存在绝对绝对最最优优解的情况解的情况不多不多见见。因此，必需。因此，必需扩扩充最充最优优解的概念。解的概念。为为此需要建立向此需要建立向量量间间的自然序关系。除在定的自然序关系。除在定义

235、义1.1中定中定义义的序关系外，的序关系外，还还要用到下面的序关系。要用到下面的序关系。定定义义5.2 设设和和都是都是维维向量。若向量。若 ,并且至少有一个等号并且至少有一个等号小于向量小于向量，记记作作或称或称向量向量大于向量大于向量，记记作作。是是严严格小于号，格小于号，则则称称向量向量，例如，向量例如，向量和和之之间间有有，（参看定（参看定义义1.1），而），而和和之之间间不存在自然序关系。不存在自然序关系。如下的序关系：如下的序关系：需要注意的是，由关系式需要注意的是，由关系式可以可以导导出出但反但反过过来不成立。例如来不成立。例如和的序关系可以写成的序关系可以写成但不能写成但不能写

236、成。定定义义5.3 考考虑问题虑问题（5.3），），设设。若不存在。若不存在，使得，使得，则则称称 是（是（5.3）的）的有效解有效解， 又称又称Pareto解解（这这个概念是个概念是经济经济学家学家V.Pareto于于1896年引年引入的）。所有有效解的集合称入的）。所有有效解的集合称为为有效解集有效解集，记记作作 或或。 ， 绝对绝对最最优优解是从正面定解是从正面定义义的，而有效解是从反面定的，而有效解是从反面定义义的。的。 为为有效解的含有效解的含义义是，在容是，在容许许集内找不到比集内找不到比 在在“ ”意意义义下更好的解。下更好的解。 一般一般说说来，有效解不是来，有效解不是“最最优

237、优的的”，但可以，但可以说说它是它是“不坏的不坏的”，因此有效解又称，因此有效解又称为为非劣解非劣解。在多目。在多目标标最最优优化理化理论论中，中，这这是一个最基本的概念。比有效解是一个最基本的概念。比有效解还还差的差的“非劣非劣”解是弱有效解是弱有效解。解。定定义义5.4 考考虑问题虑问题（5.3），），设设。若不存在。若不存在，使得，使得，则则称称是（是（5.3）的）的弱有弱有或或。效解效解。所有弱有效解的集合称。所有弱有效解的集合称为为弱有效解集弱有效解集，记记作作 弱有效解也是从反面定弱有效解也是从反面定义义的。的。 为为弱有效解的含弱有效解的含义义是，是，在容在容许许集内找不到比集内

238、找不到比 在在“ ”意意义义下更好的解，也就是下更好的解，也就是在在 中找不到中找不到 ，使得，使得 。下面的几个定理描述了各种解之下面的几个定理描述了各种解之间间的关系。的关系。定理定理5.1 设设 表示（表示（5.3）中第）中第 分量目分量目标标函数函数在在 上的最优解集，则（上的最优解集，则（5.3）的绝对最优解集）的绝对最优解集定理定理5.2 绝对最优解必是有效解。绝对最优解必是有效解。证证 设设，则对则对，都有，都有这这表明表明对对于于，即不存在，即不存在使得使得，故，故。，定理定理5.2表明表明。定理定理5.3 有效解必是弱有效解。有效解必是弱有效解。证证 设设，则则不存在不存在，

239、使得，使得换换句句话说话说，对对于于，都有，都有 。这这，更有，更有，即不存在，即不存在使得使得，故，故。表明表明对对，定理定理5.3表明表明。 定理定理5.4 各分量目各分量目标标函数在函数在上的最上的最优优解必是弱有效解。解必是弱有效解。证证 对对于于，设设，则对则对，都，都。从而不存在。从而不存在，使得，使得故故。有有，定理定理5.4表明表明。推推论论5.5 综综上所述，各种解集之上所述，各种解集之间间有如下关系：有如下关系：定理定理5.6 若（若（5.3）的）的绝对绝对最最优优解集解集，则则它的它的。有效解集有效解集定理定理5.7 若（若（5.3）的容）的容许许集集是凸集，且每个分量是

240、凸集，且每个分量在在上均是上均是严严格凸函数，格凸函数，则则它的有效解集它的有效解集目目标标函数函数与弱有效解集相等。与弱有效解集相等。例例5.3 考虑多目标最优化问题考虑多目标最优化问题试验证试验证：。解解 容易容易验证验证， 和和都是容都是容许许集上的凸函数，它集上的凸函数，它们们的的和和。因。因为为根据定理根据定理5.1，绝对绝对最最优优解集解集。最最优优解集分解集分别为别为， 由于由于 和和 在各自最在各自最优优解集的左解集的左侧侧和右和右侧侧分分别别都是都是严严格格递递减函数和减函数和严严格格递递增函数（增函数（见图见图），），5.4，不存在弱有效解。，不存在弱有效解。所以在所以在

241、和和 中，根据定中，根据定义义 在在 中，中， 是是严严格格递递增的，而增的，而 是是严严格格递递减减的，因此，根据定的，因此，根据定义义5.3 可可以判断以判断 中的点都是有效中的点都是有效解。又在解。又在 中，中， 是是严严格格递递增的，而增的，而 是常数，根据是常数，根据定定义义5.3可以判断可以判断 中不中不存在有效解。因此，有效解存在有效解。因此，有效解集集 。综综上所述，并依据推上所述，并依据推论论5.5可知，弱有效解集可知，弱有效解集。5.3 5.3 评评价函数法价函数法 求解多目求解多目标标最最优优化化问题问题，最好求出，最好求出绝对绝对最最优优解。如果解。如果绝对绝对最最优优

242、解不存在，解不存在，则应该则应该求出有效解，最差也要求出弱求出有效解，最差也要求出弱有效解（如果存在的有效解（如果存在的话话）。）。 有效解和弱有效解通常可以构成解集，但要想求出有效解和弱有效解通常可以构成解集，但要想求出这这个解集是比个解集是比较较困困难难的。的。对对于于实际问题实际问题，能求出，能求出满满足要求的足要求的有效解或弱有效解就可以了。求解多目有效解或弱有效解就可以了。求解多目标标最最优优化化问题问题有多有多种方法，包括主要目种方法，包括主要目标标法、分法、分层层排序法、重点目排序法、重点目标标法、法、评评价函数法以及分价函数法以及分组组排序法等。最基本有效的方法是下面要排序法等

243、。最基本有效的方法是下面要介介绍绍的的评评价函数法。价函数法。1. 1. 基本定理基本定理定定义义5.55.5 设，。）若当）若当时时，总总有有，则则称称是是的的严严格格单调单调增函数增函数。）若当）若当时时，总总有有，则则称称是的的单调单调增函数增函数。定理定理5.8 设设，又，又设设是如下是如下问题问题（5.7） 的极小点，那么的极小点，那么）若）若是的的严严格格单调单调增函数，增函数，则则；）若）若是是的的单调单调增函数，增函数，则则。证证 ）使用反）使用反证证法。假法。假设设。根据。根据 定定义义5.3，则则必存在必存在，使得，使得。由。由的的严严格格单调单调性，性，则则必有必有。这这

244、与与是（是（5.7）的极小点相矛盾。）的极小点相矛盾。）证证明与明与）类类似（似（习题习题5.11）。）。2. 2. 几个常用的几个常用的评评价函数价函数（1）线性加权函数）线性加权函数设设满满足足和和如取如取，称，称为为线线性加性加权权和函数和函数，则则有如下有如下结论结论：。）当）当时时，是是的的严严格格单调单调增函数；增函数；）当）当时时，是是的的单调单调增函数。增函数。根据定理根据定理5.8，只要取，只要取（或或），那么求解），那么求解多目多目标标最最优优化化问题问题（5.3）就可以）就可以转转化化为为求解求解单单目目标标最最优优化化问题问题即即这个单目标最优化问题的极小点就是（这个单

245、目标最优化问题的极小点就是（5.3）的有效解）的有效解（或弱有效解）。（或弱有效解）。 该该方法因方法因称称为为线线性加性加权权和法和法。这这里的里的分分别别称称为为分量目分量目标标函数函数的的权权系数系数， 称称为权为权系数向量。系数向量。权权系数的系数的相相对对大小表征各分量目大小表征各分量目标标的相的相对对重要程度。重要的目重要程度。重要的目标应标应赋赋予予较较大的大的权权系数，不重要的目系数，不重要的目标应赋标应赋予予较较小的小的权权系数。系数。因此，特因此，特别别是在是在对实际问题对实际问题的求解中，的求解中，权权系数的系数的选选取就成取就成为为求到合理的有效解的关求到合理的有效解的

246、关键键。的具体。的具体选选取方法将在取方法将在3.3.中中讨讨论论。例例5.5 用线性加权和法求解例用线性加权和法求解例5.1。解解 把例把例5.1中第二分量目标函数的求极大转化为求极中第二分量目标函数的求极大转化为求极小，问题变成小，问题变成如果第一和第二分量目如果第一和第二分量目标标函数的函数的权权系数分系数分别别取取为为0.3和和0.7，那么上述，那么上述问题问题就就转转化化为为如下如下单单目目标标最最优优化化问题问题用第用第4章中的方法可以解出章中的方法可以解出这这个个问题问题的极小点的极小点 它是原问题（例它是原问题（例5.1）的有效解。其实际含义是，当宽为）的有效解。其实际含义是，

247、当宽为0.5013而高为而高为0.8653时，可使木梁的重量最轻且强度最大。时，可使木梁的重量最轻且强度最大。需要指出的是，这是在重量和强度的权系数分别取需要指出的是，这是在重量和强度的权系数分别取0.3和和0.7时得出的有效解。时得出的有效解。，（2）理想点函数）理想点函数 假假设设（5.3）的各分量目）的各分量目标标函数在函数在上都存在极小点。上都存在极小点。因此可因此可设设极小极小值值称称为为第第分量目分量目标标函数的函数的理想理想值值，点，点 称称为为向量目向量目标标函数函数在其在其值值域域空空间间中的的中的的理想点理想点。 的的值值域域是是而而值值域空域空间间是指是指所在的所在的维维

248、空空间间。 ，当当时时，因，因为对为对于于，均有，均有 ，因此，因此是是(5.3)的的绝对绝对 最最优优解解。又因为。又因为，此，此时时因此，当因此，当彼此相等彼此相等时时， 的理想点在其的理想点在其不完全相等不完全相等时时， 值值域中。但是，当域中。但是，当的理想点的理想点就很可能就很可能 不在其不在其值值域中了。域中了。对对此，有一个很自然的想法：找一点此，有一个很自然的想法：找一点，使得，使得与理想点与理想点的的“距离距离”在某种在某种应该应该是（是（5.3）的一个最）的一个最优优解。解。这这个个意义下最小，那么意义下最小，那么想法想法导导致致产产生如下的生如下的评评价函数价函数称称为为

249、理想点函数理想点函数，其中，其中是是中的某种模。中的某种模。例如，采用例如，采用模的模的评评价函数价函数为为。而其中最常用的是。而其中最常用的是2模模评评价函数价函数（5.9） （5.8） 容易容易验证验证，（，（5.8）是）是严严格格单调单调增函数。事增函数。事实实上，上，设设，则则。于是，。于是，这样，求解（这样，求解（5.3）就转化为求解）就转化为求解即即这这个个问题问题的极小点就是（的极小点就是（5.3）的有效解（定理）的有效解（定理5.8）。）。该该方法称方法称为为理想点法理想点法。（3）平方加权函数）平方加权函数 对对形如（形如（5.9）的）的评评价函数从两个方面加以改造：第价函数

250、从两个方面加以改造：第一，把一，把 换换 为为在在 上极小上极小值值的一个尽可能好的估的一个尽可能好的估计计 。这样这样可以避免可以避免对对每个分量目每个分量目标标函数求极小函数求极小值值的的计计算；第算；第二，二，对对平方和的各平方和的各项赋项赋予予权权系数。此外，去除（系数。此外，去除（5.9）中）中的开平方运算。的开平方运算。这样这样既考既考虑虑了各分量目了各分量目标标函数的不同重要函数的不同重要程度，又避免了不利于数程度，又避免了不利于数值计值计算的开平方算的开平方计计算。因此，算。因此，获获得得评评价函数价函数（5.10） 容易容易验证验证，当，当时时，是是的的严严格格单单调调增函数

251、（增函数（习题习题5.13）。于是，求解（）。于是，求解（5.3）就）就转转化化为为求解求解这这个个单单目目标标最最优优化化问题问题的极小点即是（的极小点即是（5.3）的有效解。）的有效解。该该方法称方法称为为平方和加平方和加权权法法。（4 4）极大函数）极大函数取极大函数取极大函数（5.11） 作为评价函数。作为评价函数。更一般地，也可以更一般地，也可以对对依次依次赋赋予予权权系数系数，取，取（5.12） 作作为评为评价函数。容易价函数。容易验证验证，当，当时时，是是的的单调单调增函数。增函数。这这是因是因为为：若：若，则则有有 。因此，。因此， 在在选选取（取（5.12）作）作为评为评价函

252、数价函数时时，求解（，求解（5.3）就）就转转化化为为求解求解单单目目标标最最优优化化问题问题（5.13） 根据定理根据定理5.85.8，这这个个问题问题的最的最优优解是（解是（5.3）的弱有效解。）的弱有效解。该该方法称方法称为为极大极小法极大极小法。（5.13）可以解）可以解释为释为在最不利的情况下求最好的在最不利的情况下求最好的结结果。果。在在实际计实际计算中，直接求解算中，直接求解( (5.13) )是不是不简简便的。考便的。考虑对虑对在在上的共同上界上的共同上界求极小，即求极小，即（5.14） 定理定理5.9将将说说明（明（5.14）和（）和（5.13）是等价）是等价问题问题。定理定

253、理5.9 设设，则则为为（5.13）最）最优优使得使得是（是（5.14）的）的解的充要条件是，存在数解的充要条件是，存在数最最优优解。解。证证 必要性必要性 设设是（是（5.13）的最）的最优优解，并取解，并取显显然然是（是（5.14）的容）的容许许解。又解。又设设是（是（5.14）的任意一个容的任意一个容许许解，解，则则这这表明表明是（是（5.14）的最）的最优优解。解。充分性充分性 设设是（是（5.14）的最）的最优优解。解。显显然然对对于于，取，取，易，易见见是（是（5.14）的容的容许许解。解。 于是于是上式表明，上式表明，是（是（5.13）的最）的最优优解。解。 如果如果选选取（取（

254、5.11）作）作为评为评价函数，那么求解（价函数，那么求解（5.3）就）就转转化化为为求解求解单单目目标标最最优优化化问题问题即即其最优解即是（其最优解即是（5.3）的弱有效解。）的弱有效解。3. 权权系数的确定方法系数的确定方法 在上述几个在上述几个评评价函数中，一般都可以价函数中，一般都可以赋赋予予权权函数。不函数。不同的同的权权系数通常系数通常对应对应不同的有效解或弱有效解。不同的有效解或弱有效解。对对于于实际实际中的多目中的多目标标最最优优化化问题问题，并不是所有的有效解或弱有效解，并不是所有的有效解或弱有效解都有都有实实用意用意义义。例如，例。例如，例5.1中有效解中有效解 和和 无

255、无实际实际意意义义。因此，。因此，选选取合适的取合适的权权系数有系数有时时就就显显得至关重要。得至关重要。 在确定在确定权权系数之前，一般要系数之前，一般要对对各分量目各分量目标标函数函数值值做做统统一量一量纲纲的的处处理。不然的理。不然的话话，可能会由于各分量目，可能会由于各分量目标标函数函数值值存在数量存在数量级级上的上的较较大差大差别别，而，而导导致致权权系数作用的失效。例系数作用的失效。例如，数量如，数量级较级较小的目小的目标标函数即使函数即使赋赋予予较较大的大的权权系数。在系数。在变变换换后的后的单单目目标标最最优优化化问题问题中它也不起太大的作用。中它也不起太大的作用。 统统一量一

256、量纲纲的的处处理一般分理一般分为为两步：第一，各分量目两步：第一，各分量目标标函函数都加上同一个正数，使得新的各分量目数都加上同一个正数，使得新的各分量目标标函数函数 在在上的取上的取值值都大于零；都大于零； 第二，求 在在上的极小上的极小值值，依次，依次设为设为 ，然后把，然后把 作作为为最最终终的的分量目分量目标标函数。函数。下面介下面介绍绍两种常用的确定两种常用的确定权权系数的方法。系数的方法。（1）老手法）老手法 如果如果问题问题的目的目标仅标仅有少数几个，而且有少数几个，而且计计算者算者对问题对问题有有深入的了解，能深入的了解，能够够从从专业专业理理论论和和实实践践经验经验中找到根据

257、，那中找到根据，那么么计计算者可以直接确定各目算者可以直接确定各目标标的的权权系数。但是，当目系数。但是，当目标较标较多多时时，单单凭一个人的凭一个人的经验经验估估计计就那么不科学了。就那么不科学了。这时这时，可，可使用使用老手法老手法：通：通过汇过汇集多位老手的集多位老手的经验经验估估计计来确定来确定权权系数系数的一种方法。而的一种方法。而老手老手是指有关是指有关专专家和有家和有实实践践经验经验的工作者。的工作者。下面介绍老手法。下面介绍老手法。设设有有个目个目标标，请请了了位老手。在老手位老手。在老手们对问题们对问题了解之后，他了解之后，他们们独自地独自地对对各目各目标标的重要程度的重要程

258、度进进行行评评估。估。充分充分设设第第位老手位老手对对第第个目个目标赋标赋予的予的权权系数是系数是，要求，要求，。计计算各目算各目标标权权系数的算系数的算术术平均平均值值显显然然。再。再计计算各位老手所提供的算各位老手所提供的权权系数系数与其平均与其平均值值的最大偏差的最大偏差（也可以使用均方差）。（也可以使用均方差）。设设用用表示事先表示事先选选定的定的,偏差。于是，若偏差。于是，若最大允最大允许许则则表明老手表明老手们们的的经验经验是可接受的。是可接受的。 估估计计没有没有显显著差著差别别，权权系数系数否否则则，需要与有，需要与有较较大偏差的老手大偏差的老手讨论讨论、协协商，商，让让其其对

259、权对权系系数数给给出新的估出新的估计计。然后再。然后再计计算偏差。重复上述算偏差。重复上述过过程，直到程，直到所有偏差不超所有偏差不超过过 为为止。止。（2） 法法法法是借助各分量目是借助各分量目标标函数在容函数在容许许集上的极小点所集上的极小点所求解求解单单目目标标函数极小化函数极小化问题问题提供的信息来确定权系数的一种方法。提供的信息来确定权系数的一种方法。对于，设设各分量目各分量目标标函数在容函数在容许许集上的极小点分集上的极小点分别为别为 。如果如果这这些极小点彼此相同，那么就求到了（些极小点彼此相同，那么就求到了（5.3）的的绝对绝对最最优优解解(参看理想点法参看理想点法)。否。否则

260、则，利用，利用这这些点一般可确定出些点一般可确定出 值值域空域空间间中的中的个点：个点：。假假设这设这 个点彼此不相同，那么由它个点彼此不相同，那么由它们们可以确定可以确定 中的一中的一个超平面。个超平面。设设用用 表示表示这这个超平面的法向量。如果个超平面的法向量。如果 满满足足 且且 （或或 ），其中，其中 表示所有分量表示所有分量为为1的的 维维向量，那么向量，那么 就可以被就可以被选选作作权权系数向量。系数向量。 事事实实上，以上，以 为为法向量的超平面方程法向量的超平面方程为为，中中是任意常数。是任意常数。现现在要在要选选取取以以满满足足，这这就是就是该该法法法的法的缘缘由。由。被命名被命名为为把把个点个点代入超平面方程代入超平面方程，然后与，然后与联联立，立刻得到如下具有立，立刻得到如下具有个未知数的个未知数的线线性代数性代数方程方程组组若设若设则方程组可简写为则方程组可简写为由此解出由此解出若若（或或），则则就可以作就可以作为权为权系数向量。系数向量。