最优化方法全部课件.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.极大值问题与极小值问题的关系极大值问题与极小值问题的关系 1.4 1.4 二维问题

5、图解法二维问题图解法 二维二维极值极值问题有时可以用图解的方式进行求解，有问题有时可以用图解的方式进行求解，有明显的几何解释。明显的几何解释。例例 求解求解 图解法的步骤：图解法的步骤：，显然；取取并画出相应的曲线（称之为等值线）并画出相应的曲线（称之为等值线）.确定极值点位置，并用以往所学方法求之。确定极值点位置，并用以往所学方法求之。易知本题的极小值点易知本题的极小值点。再复杂点的情形见再复杂点的情形见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）设设，其中，其中。则。则利用（利用（4），可得多元函数展开到三项的），可得多元函数展开到三项的Taylor公式公式（1.29）或或（1.31）这个公式与一元函数展开到

16、三项的这个公式与一元函数展开到三项的Taylor公式是相对应的。公式是相对应的。多元函数的多元函数的Taylor展开式在最优化方法中十分重要，展开式在最优化方法中十分重要，许多方法及其收敛性的证明都是从它出发的。许多方法及其收敛性的证明都是从它出发的。1.凸集凸集1.6 凸函数与凸规划凸函数与凸规划 直观上，凸集就是空间中内部无直观上，凸集就是空间中内部无“洞洞”，边界又不向，边界又不向内凹的一些点的集合，其基本特征是该集合中任意两点内凹的一些点的集合，其基本特征是该集合中任意两点间的线段仍然属于这个集合。间的线段仍然属于这个集合。非凸集非凸集 凸集凸集 空间中两点间的线段是由点的凸组合定义的

17、空间中两点间的线段是由点的凸组合定义的。定义定义1.12 设设是是中的中的个已知点。个已知点。点点，若存在满足，若存在满足的非负实数的非负实数 对于对于 使得使得，则称，则称是是的一个凸组合。的一个凸组合。又若又若是满足是满足的正实数，则称的正实数，则称 是是的一个严格凸组合。的一个严格凸组合。两点两点的的凸组合凸组合恰是连接两点的恰是连接两点的的的线段。线段。线段，而严格凸组合是不含端点线段，而严格凸组合是不含端点 定义定义1.13 1.13 设集合设集合。如果。如果中任意两点的中任意两点的，那么集合，那么集合称为凸集。称为凸集。任意凸组合仍然属于任意凸组合仍然属于规定：空集是凸集。规定：

18、空集是凸集。思考思考：空间中三个不同点的凸组合的集合，空间中：空间中三个不同点的凸组合的集合，空间中四个不同点的凸组合的集合四个不同点的凸组合的集合.常见的凸集有超平面，直线，球常见的凸集有超平面，直线，球.定理定理1.5 凸集的交集是凸集。凸集的交集是凸集。2.凸函数凸函数定义定义1.16 设设，其中，其中为凸集。若对于为凸集。若对于中的任意互异两点中的任意互异两点和任意一对满足和任意一对满足的非负实数的非负实数，总有总有则称则称是定义在凸集是定义在凸集上的凸函数。又若对于任意上的凸函数。又若对于任意的正实数的正实数，总有，总有一对满足一对满足则称则称是定义在凸集是定义在凸集上的严格凸函数。

19、上的严格凸函数。若若是凸集是凸集上的（严格）凸函数，则称上的（严格）凸函数，则称是凸集是凸集上的（严格严格）凹函数凹函数。凸函数有以下重要性质。凸函数有以下重要性质。定理定理1.6 （1）若）若是定义在凸集是定义在凸集上的凸函数，上的凸函数，是是也是也是上的凸函数。上的凸函数。任意的非负实数，则任意的非负实数，则（2）若）若是定义在凸集是定义在凸集上的凸函数，则上的凸函数，则也是也是上的凸函数。上的凸函数。由定理由定理1.6易见，定义在凸集上的任意有限个凸函数易见，定义在凸集上的任意有限个凸函数的任意非负组合仍然是凸函数。的任意非负组合仍然是凸函数。例例1.10定理定理1.7 设，其中，其中为

20、非空凸集，若为非空凸集，若是凸函数，则对于任意实数是凸函数，则对于任意实数，水平集水平集是凸集。是凸集。证证 若若是空集，则是凸集。以下设是空集，则是凸集。以下设非空。任取非空。任取，则，则。又设。又设但但，根据，根据的凸性，必有的凸性，必有即即。因此，。因此，是凸集。是凸集。判断一个函数是否为凸函数，一般说来，是比较困判断一个函数是否为凸函数，一般说来，是比较困难的。但当函数可微时，有以下几个判定定理。难的。但当函数可微时，有以下几个判定定理。定理定理1.7 设设定理定理1.8 设设是可微函数，其中是可微函数，其中为为凸集。则凸集。则)为凸函数的充要条件是对于为凸函数的充要条件是对于中的任意

21、两点中的任意两点，都有，都有)为严格凸函数的充要条件是对于为严格凸函数的充要条件是对于中的任意中的任意都有都有两个互异点两个互异点 定理定理1.8有明显直观的几何解释。有明显直观的几何解释。可微函数为凸函数的充要条件是在其可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面（切定义域凸集中任一点处的切平面（切线）都不在曲面（曲线）的上方。右线）都不在曲面（曲线）的上方。右图画出了一维的情形。图画出了一维的情形。定理定理1.9 设设是二次可微函数，是二次可微函数，为非为非空开凸集。空开凸集。则则为为上凸函数的充要条件是上凸函数的充要条件是Hesse矩阵矩阵在在上处处半正定。上处处半正定。

22、定理定理1.10 设设是二次可微函数，是二次可微函数，为非为非空凸集，空凸集，若若的的Hesse矩阵矩阵在在上处处正定，则上处处正定，则是是上的严格凸函数。上的严格凸函数。这个命题的逆命题不真这个命题的逆命题不真。例如，例如，在在上为严格凸函数，上为严格凸函数，在在处是处是半正定的。半正定的。但是它的但是它的Hesse矩阵矩阵3.凸规划凸规划 设设是定义在非空凸集是定义在非空凸集上的凸函数，上的凸函数，则形式为则形式为（1.36）的最优化问题称为凸规划问题，简称凸规划。换言之，的最优化问题称为凸规划问题，简称凸规划。换言之，定义在凸集上的凸函数的极小化问题是凸规划问题。定义在凸集上的凸函数的极

23、小化问题是凸规划问题。若若都是都是上的凹函数，上的凹函数，都是都是上的线性函数，容易验证集合上的线性函数，容易验证集合是凸集。在这种情况下，凸规划（是凸集。在这种情况下，凸规划（1.36）可以表示成如）可以表示成如下形式下形式（1.37）下面的定理指出了凸规划的一些重要性质。下面的定理指出了凸规划的一些重要性质。定理定理1.11 设设是凸规划（是凸规划（1.36）的局部极小点。则）的局部极小点。则i）是（是（1.36）的全局极小点；）的全局极小点；ii）当）当是严格凸函数时，是严格凸函数时，是（是（1.36）的唯一极小点；）的唯一极小点；iii）（）（1.36）的全部极小点的集合是凸集。）的全

24、部极小点的集合是凸集。定理定理1.12 设设是可微凸函数，是可微凸函数，是非空是非空。凸集，凸集，则则是凸规划（是凸规划（1.36）的极小点的）的极小点的充要中任意一点中任意一点，总有，总有。条件是，对于条件是，对于 定理定理1.12表明，凸规划（表明，凸规划（1.36）在最优点处的任何）在最优点处的任何容许方向（定义容许方向（定义4.3）都不是下降方向。）都不是下降方向。推论推论1.13 设设是可微凸函数，是可微凸函数，是非空是非空凸集，凸集，。若。若使得使得，则，则是凸规划（是凸规划（1.36）的全局极小点。）的全局极小点。4.二次函数与二次规划二次函数与二次规划函数函数（1.38）称为称

25、为元二次函数，其中元二次函数，其中是对称矩阵。若是对称矩阵。若是正定的，则（是正定的，则（1.38）称为正定）称为正定二次函数二次函数。，注意到注意到，于是由定理于是由定理1.10得知：正定二次得知：正定二次函数是严格凸函数。在最优化算法构造中，正定二次函数函数是严格凸函数。在最优化算法构造中，正定二次函数起着特殊的作用，本书的许多章节都要涉及它。起着特殊的作用，本书的许多章节都要涉及它。形式为形式为（1.39）的最优化问题称为二次规划问题，简称二次规划。若的最优化问题称为二次规划问题，简称二次规划。若 是半正定的或正定的，则（是半正定的或正定的，则（1.39）称为二次凸规划。）称为二次凸规划

26、定理定理1.14 一个一个 对称矩阵对称矩阵 为正定矩阵的充为正定矩阵的充要条件是条件是 的各阶主子式皆大于零。的各阶主子式皆大于零。开始开始 最最优化方法化方法（最（最优化化课件件研制制组）退出退出主讲：张主讲：张 京京1.7 极小点的判定条件极小点的判定条件函数函数 在局部极小点满足什么条件？反之，满足在局部极小点满足什么条件？反之，满足什么条件的点是什么条件的点是 的局部极小点？的局部极小点？定理定理1.15 设具有一具有一阶连续偏偏导数，数，是是的内点。若的内点。若是是的局部极小点，的局部极小点，则（1.40）注意，条件式（注意，条件式（1.40）不是充分的，仅仅是必要的。）不是充分

27、的，仅仅是必要的。例如，例如，在点在点 处的梯度是处的梯度是 但是点但是点 是这个双曲抛物面的鞍点，而是这个双曲抛物面的鞍点，而不是极小点。不是极小点。根据定理根据定理1.15与推论与推论1.13，容易得到凸规划问题全局极小容易得到凸规划问题全局极小点的一个一阶充分且必要条件。点的一个一阶充分且必要条件。推论推论1.16 设设 是可微凸函数，是可微凸函数，是非空开凸集，是非空开凸集，。则。则 是（是（1.36）的全局极小点的）的全局极小点的充要条件是充要条件是.定义定义1.17 设设 可微，可微，若若，则称称为的的驻点。点。驻点包括极大值点、极小值点和鞍点。驻点包括极大值点、极小值点和鞍点。定

28、理定理1.17 设具有二具有二阶连续偏偏导数，数，且，且。若。若正定，正定，则是是的的严格局部极小点。格局部极小点。一般来一般来说，这个定理个定理仅具有理具有理论意意义。因。因为对于复于复杂的目的目标函数，函数，Hesse矩矩阵不易求得，其正定性也很不易求得，其正定性也很难判定。判定。定理定理1.18 设具有二具有二阶连续偏偏导数，数，且且。若存在若存在的的邻域域，使得，使得 对于于，都半正定，都半正定，则必是必是的局部极小点。的局部极小点。利用上节和本节的定理不难说明下面的两个论断。利用上节和本节的定理不难说明下面的两个论断。i）对于正定二次函数）对于正定二次函数，是它的唯一极小点。是它的唯

29、一极小点。ii）若多元函数在极小点处的）若多元函数在极小点处的Hesse矩阵是正定的矩阵是正定的,则则在这个极小点附近其等值面近似地呈现为同心椭球面族。在这个极小点附近其等值面近似地呈现为同心椭球面族。推证如下：推证如下：i）首先求出二次函数的驻点。令）首先求出二次函数的驻点。令因因为是正定矩是正定矩阵，所以解出唯一，所以解出唯一驻点点为（1.41）因此根据推论因此根据推论1.13可以断定，可以断定，是唯一的极小点。是唯一的极小点。ii）设是多元函数的极小点，是多元函数的极小点，并并设是充分是充分的一个等的一个等值面，面，靠近极小点靠近极小点即即充分小。充分小。把把在点在点处按按Taylor公

30、式展开，得到公式展开，得到上式右端第二上式右端第二项因因为是极小点而消失，再略去是极小点而消失，再略去第四第四项，那么二次曲面，那么二次曲面（1.42）就是等就是等值面面的近似曲面。的近似曲面。按假按假设，是正定的，因此，是正定的，因此，为中心的中心的椭球面球面（1.42）是以）是以方程。方程。这正是我正是我们所要所要说明的。明的。1.下降迭代算法下降迭代算法1.8 算法及有关概念算法及有关概念在集合在集合上的迭代算法是指：开始，上的迭代算法是指：开始，选定一个初始点定一个初始点，置，置。然后按某种。然后按某种规则，把第，把第 次迭代点次迭代点映射映射为新的一点新的一点，记为，并置，并置这称称

31、为完成了第完成了第次迭代。次迭代。这个个过程无限地程无限地进行下去，行下去，。因此，。因此，规则称称为算法。算法。就会产生一个点列就会产生一个点列若点列若点列收收敛于于，则称算法称算法在在上是收上是收敛的；的；否否则，称算法，称算法在在上是上是发散的。特散的。特别地地，当，当 问题（问题（1.6）的容许集时，若除满足计算终止准则的迭代点）的容许集时，若除满足计算终止准则的迭代点是最优化是最优化外，对于每个外，对于每个，都有，都有，则称称为下降迭代下降迭代 许多最优化方法都采用将多维问题转化为一维问题的许多最优化方法都采用将多维问题转化为一维问题的处理方式。下面以处理方式。下面以无约束问题无约束

32、问题为例，说明采用这种方式时为例，说明采用这种方式时的下降算法的基本迭代格式。的下降算法的基本迭代格式。设第第次迭代点次迭代点已求得。若它不已求得。若它不满足足终止准止准则，。对于可微目于可微目标函数，即函数，即那么在该点必存在下降方向那么在该点必存在下降方向是满足是满足的的。按某种。按某种规则选取一个取一个，例如，例如，再沿，再沿这个方向适当地前个方向适当地前进一步，即在直一步，即在直线 上确定一个新点上确定一个新点，使得，使得 这就完成了第就完成了第迭代。上式中的迭代。上式中的称称为搜索方向，搜索方向，称称为步步长因子。因子。不不过，计算机只能算机只能进行有限次迭代。因此，一般行有限次迭代

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

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

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

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

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

38、或（1.47）（1.48）（1.47）表明）表明是点是点处的下降方向，（的下降方向，（1.48）表明）表明是点是点处的下降方向，的下降方向，这都与都与相矛盾。相矛盾。故必有故必有（1.46）的几何意义是明显的。）的几何意义是明显的。若若是从点是从点出出发沿沿方向方向对目目标函数函数搜索得到的极小点，搜索得到的极小点，则（1.46）指出，梯度）指出，梯度搜索方向向量搜索方向向量正交。正交。作直线作直线必与必与又因又因为与目与目标函数函数过点点的等的等值面（等直面（等直线）正交，所以搜索方向向量正交，所以搜索方向向量与与这个等个等值面（等直面（等直线）在点）在点处相切。相切。3.计算终止准则计算终

39、止准则设某个算法某个算法产生的点列生的点列收收敛于（于（1.6）的最）的最优解解。现在的在的问题是：在是：在计算机上算机上计算算时，计算到哪一个算到哪一个迭代点才有把握地说它就是所求问题的（近似）最解？迭代点才有把握地说它就是所求问题的（近似）最解？显然，当然，当小于小于预先先给定的定的误差限差限时就可以就可以就是所求的最就是所求的最优解。解。认为但事但事实上上是未知的，因而是未知的，因而无法计算无法计算。不。不过，由极限理，由极限理论知道，当知道，当 与与都很小都很小时，也必然很小。于是，在也必然很小。于是，在数值计算中，可以用数值计算中，可以用（1.51）作作为计算算终止的一个判定条件，其

40、中止的一个判定条件，其中是是预先先给定的定的计算算终止的界限，今后称为终止限。终止的界限，今后称为终止限。但是，用（但是，用（1.51）作为终止准则是不可靠的，因为）作为终止准则是不可靠的，因为 很小并不能保证很小并不能保证 很小。很小。下面图下面图1中画出了一条一元目标函数的曲线及其有关的点。中画出了一条一元目标函数的曲线及其有关的点。从图中可以看到，相邻两个迭代点从图中可以看到，相邻两个迭代点 和和已已经很很靠近了，靠近了，但它但它们距极小点距极小点却都很却都很远，而且，而且这两点的两点的目标函数值目标函数值和和还由极限理论知道，当还由极限理论知道，当 相差很大。相差很大。很小时，很小时，

41、也必然很小。因此，如果加上也必然很小。因此，如果加上（1.52）这个条件，那么可靠性就会加强。上图这个条件，那么可靠性就会加强。上图2指出了只采指出了只采用（用（1.52）也是不可靠的。虽然）也是不可靠的。虽然 与与 相差很小，可相差很小，可是相是相应的两个迭代点的两个迭代点和和却相距很却相距很远，它，它们距距极极也很也很远。小点小点需要注意的是，实际应用中，由于需要注意的是，实际应用中，由于 和和 所取的量所取的量 纲有时太大，这时如果仍然以（纲有时太大，这时如果仍然以（1.51）和（）和（1.52）作为终）作为终止准则就太严格了。结果要么是用更多的计算才能使得止准则就太严格了。结果要么是用

42、更多的计算才能使得（1.51）和（）和（1.52）得到满足，而这是不划算的；要么是）得到满足，而这是不划算的；要么是永远不能满足。解决这个问题的办法是，永远不能满足。解决这个问题的办法是，先先对和和 作无量纲处理，然后再结合（作无量纲处理，然后再结合（1.51）和（）和（1.52），给出），给出（1.53）和和（1.54）作为终止准则。作为终止准则。此外，有一此外，有一类无无约束最束最优化方法在求解化方法在求解过程中利用了程中利用了梯度。由于梯度。由于 为极小点的必要条件是为极小点的必要条件是。因此，。因此，当当满足足（1.55）时，一般可以认为时，一般可以认为 就是所要求的最优解。由于条件不

43、是就是所要求的最优解。由于条件不是充分的，所以单独以（充分的，所以单独以（1.55）作为终止准则也是不可靠的。）作为终止准则也是不可靠的。最后的结论是：对于使用导数的最优化方法，可按书最后的结论是：对于使用导数的最优化方法，可按书上图所示的判别过程作为终止准则；对于不使用导数的最上图所示的判别过程作为终止准则；对于不使用导数的最优化方法，则只需把图中涉及优化方法，则只需把图中涉及 的部分去掉。今后的部分去掉。今后 统称为统称为Himmelblau计算终止准则，简称计算终止准则，简称H终止准则。终止准则。例例1：已知：已知求求解：解：，例例2：用图解法求解：用图解法求解解：解：画出目标函数画出目

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

45、一条抛物线；画出不等式约束所代表的区域。画出不等式约束所代表的区域。容许集为抛物线的一段，最优解为抛物线的端容许集为抛物线的一段，最优解为抛物线的端点，即方程点，即方程的解的解最优值最优值目标函数的等值线与容许集的切点，即最优目标函数的等值线与容许集的切点，即最优点满足方程点满足方程切点切点点点不在容许集上不在容许集上.最优解最优解例例4：设目标函数为：设目标函数为从点从点出发，沿出发，沿的方向的方向作直线搜索，试求搜索到的极小点作直线搜索，试求搜索到的极小点并验证并验证解：解：例例5：判别最优化问题是否为凸规划：判别最优化问题是否为凸规划解：解：正定正定并用图解法求出最优点。并用图解法求出最

46、优点。从图上可判别出容许集为淡绿色区域，此从图上可判别出容许集为淡绿色区域，此区域为凸集，故此最优化问题为凸规划。区域为凸集，故此最优化问题为凸规划。用解析方法也可证明容许集为凸集。用解析方法也可证明容许集为凸集。都为半平面，它们的交集为凸集，以下判别都为半平面，它们的交集为凸集，以下判别为凸函数。为凸函数。各阶主子式非负，各阶主子式非负，为凸函数。为凸函数。为凸集。为凸集。即容许集为凸集。即容许集为凸集。用一阶导数判别用一阶导数判别 的凸性。的凸性。为凸函数。为凸函数。即容许集为凸集。即容许集为凸集。为凸集为凸集.由图解法可求得局部极小点，它一定是此由图解法可求得局部极小点，它一定是此最优化

47、问题的全局最优点。最优化问题的全局最优点。最优点满足条件最优点满足条件解得解得为全局最优点。为全局最优点。开始开始 最最优化方法化方法（最（最优化化课件件研制制组）退出退出主讲：张主讲：张 京京 在最优化中，目标函数和约束函数皆为线性在最优化中，目标函数和约束函数皆为线性函数的优化问题称为线性规划（函数的优化问题称为线性规划（LP），它是），它是相对简单的最优化问题。本章是有关线性规相对简单的最优化问题。本章是有关线性规划的理论与求解方法的内容。划的理论与求解方法的内容。第二章第二章 线性规划线性规划2.1 2.1 线性性规划的各种形式划的各种形式1.标准形式和典范形式标准形式和典范形式 如下

48、形式的线性规划如下形式的线性规划称为线性规划的标准形式。称为线性规划的标准形式。其中各其中各称称为价格系数，各价格系数，各采用向量矩阵表示法，标准形式可以简写为采用向量矩阵表示法，标准形式可以简写为。（2.1）称为右端项。称为右端项。（2.2）在在进行理行理论分析分析时，有，有时需要把需要把表示成表示成这样，（，（2.2）中的）中的又可写成又可写成若若中有中有个列向量可以合并成个列向量可以合并成为单位矩位矩阵，且，且 例如，如下线性规划例如，如下线性规划，此时（，此时（2.2）则称为线性规划的典范形式。）则称为线性规划的典范形式。就呈就呈现为典范形式，因典范形式，因为和和可合并可合并成单位矩阵

49、成单位矩阵。不失一般性，假定不失一般性，假定单位矩位矩阵位于前位于前列，即典范列，即典范形式呈形式呈现为（2.3）其中其中。用向量矩阵表示法，那么（用向量矩阵表示法，那么（2.3）可简写成）可简写成（2.4）2.2.一般形式一般形式线性规划线性规划（2.5）3.一般形式与标准形式的关系一般形式与标准形式的关系（1）松弛变量）松弛变量考考虑“”约束中的第束中的第个不等式个不等式（2.6）引入非引入非负变量量，迫使，迫使使不等式约束（使不等式约束（2.6）变为等式约束（）变为等式约束（2.7）的非负变量）的非负变量 称为松弛变量。称为松弛变量。（2）剩余变量）剩余变量考考虑“”约束中的第束中的第

50、个不等式个不等式（2.7）（2.8）引入非引入非负变量量，迫使，迫使引入非引入非负变量量，迫使，迫使使不等式约束（使不等式约束（2.8）变为等约束（）变为等约束（2.9）的非负变量）的非负变量（2.9）称为剩余变量。称为剩余变量。在引入在引入个松弛个松弛变量、量、个剩余个剩余变量后，量后，线性性规划划（2.5）可化成标准形式：）可化成标准形式：（2.10）它含有它含有个个变量、量、个等式个等式约束。束。注意，新引入注意，新引入变量的价格系数全部量的价格系数全部设为零。因此，在零。因此，在（2.10）的目）的目标函数中没有出函数中没有出现新新变量。量。下面说明线性规划（下面说明线性规划（2.5）