最优化方法第一章精.ppt

《最优化方法第一章精.ppt》由会员分享，可在线阅读，更多相关《最优化方法第一章精.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第1页，本讲稿共35页 或或 解法：解法：LagrangeLagrange乘子法乘子法1.2 1.2 实例实例 数数据据拟拟合合问问题题 原原料料切切割割问问题题 运运输输问问题题 营营养配餐问题养配餐问题 分配问题分配问题1.3 1.3 基本概念基本概念 1.1.最优化问题的向量表示法最优化问题的向量表示法 设设 则则（1）第2页，本讲稿共35页 以向量为变量的实值函数以向量为变量的实值函数 定义向量间的序关系定义向量间的序关系(定义定义1.1)：等于，小于等于，小于，严格小于，严格小于。由此。由此（2）以向量为变量的实向量值函数以向量为变量的实向量值函数最优化问题的一般形式最优化问题的一般

2、形式 （3）第3页，本讲稿共35页 2.2.最优化问题的分类最优化问题的分类 试验问题：用于检验、比较最优化试验问题：用于检验、比较最优化方法优劣的一些最方法优劣的一些最优化问题。优化问题。3.术语术语目标函数目标函数等式约束等式约束 不等式约束不等式约束容许解（点）容许解（点）容许集容许集 第4页，本讲稿共35页 求解问题求解问题（3）是指：在）是指：在容许集容许集中找一点中找一点目标函数目标函数在该点取极小值，即对于在该点取极小值，即对于容许集容许集中中的任的任，总有，总有 意一点意一点 最优点（极小点）最优点（极小点）最优值最优值 最优解最优解严格极小点严格极小点局部局部 非严格极小点非

3、严格极小点严格极小点严格极小点非严格极小点非严格极小点全局全局 ，使得使得第5页，本讲稿共35页 到目前为止，大多数最优化算法求到的都是到目前为止，大多数最优化算法求到的都是局部极小点。局部极小点。为了求得全局极小点，一种解决办法是，先求出所有的局部为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。极小点，然后再从中找出全局极小点。4.极大值问题与极小值问题的关系极大值问题与极小值问题的关系第6页，本讲稿共35页 第7页，本讲稿共35页 1.4 1.4 二维问题图解法二维问题图解法 二维二维极值极值问题有时可以用图解的方式进行求解，有问题有时可以用图解的方式

4、进行求解，有明显的几何解释。明显的几何解释。例例 求解求解 第8页，本讲稿共35页 图解法的步骤：图解法的步骤：，显然；取取并画出相应的曲线（称之为等值线）并画出相应的曲线（称之为等值线）.确定极值点位置，并用以往所学方法求之。确定极值点位置，并用以往所学方法求之。易知本题的极小值点易知本题的极小值点。再复杂点的情形见再复杂点的情形见P13上的例上的例1.7。虽然三维及以上的问题不便于在平面上画图，图解法虽然三维及以上的问题不便于在平面上画图，图解法失效，但仍有相应的等值面的概念，且等值面具有以下性失效，但仍有相应的等值面的概念，且等值面具有以下性质：质：有不同函数值的等值面互不相交（因目标函

5、数是单值函有不同函数值的等值面互不相交（因目标函数是单值函数的缘故）；数的缘故）；等值面不会在区域的内部中断，除了极值点所在的等值面以等值面不会在区域的内部中断，除了极值点所在的等值面以外。这是由于目标函数是连续函数的缘故；外。这是由于目标函数是连续函数的缘故；令令第9页，本讲稿共35页 等值面稠密的地方，目标函数值变化得比较快；等值等值面稠密的地方，目标函数值变化得比较快；等值 面面稀疏的地方，目标函数值变化得比较慢；稀疏的地方，目标函数值变化得比较慢；在极值点附近，等值面（等值线）一般近似地呈现为同心在极值点附近，等值面（等值线）一般近似地呈现为同心椭球面族（椭圆线族）。椭球面族（椭圆线族

6、）。1.5 1.5 梯度和梯度和HesseHesse矩阵矩阵本段讨论都基于对函数本段讨论都基于对函数以下及今后的讨论中还经常要用到以下一些向量的知识。以下及今后的讨论中还经常要用到以下一些向量的知识。可微的假定。可微的假定。第10页，本讲稿共35页 与。记作记作。向量也常用希腊字母向量也常用希腊字母等表示。等表示。向量内积的向量内积的性质性质：)（对称性）；（对称性）；)（线性性）；（线性性）；),当且仅当当且仅当时时，（正定性）；（正定性）；向量的内积向量的内积 设设则则称为向量称为向量的内积，的内积，其实，其实，第11页，本讲稿共35页 向量向量的长的长 单位向量单位向量 向量的夹角向量的

7、夹角 ，向量的向量的正交正交 （正交性）正交性）1.可微 定义定义1.7 1.7 设设.如果存在如果存在维向量维向量对于可任意小的对于可任意小的维非零向量维非零向量，总有，总有在点在点那么称函数那么称函数处处可微。可微。第12页，本讲稿共35页 若令若令便得到（便得到（1.9）的等价形式）的等价形式.（1.10）2.梯度 定理定理1.1 若若在点在点处可微，则处可微，则在该点关于各个变量的一阶偏导数存在，并且在该点关于各个变量的一阶偏导数存在，并且 定义定义1.8 1.8 以函数以函数的的个偏导数为分量的向量个偏导数为分量的向量称为称为在点在点处的梯度，记为处的梯度，记为。第13页，本讲稿共3

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

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

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

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

12、明：只要，则，则方向是方向是在点在点处的上升方向；只要处的上升方向；只要，则，则方向是方向是在点在点处的下降方向。处的下降方向。第18页，本讲稿共35页 函数值升降的快慢则是由方向导数绝对值的大小决函数值升降的快慢则是由方向导数绝对值的大小决定的。绝对值越大，升或降的速度就越快；绝对值越小，定的。绝对值越大，升或降的速度就越快；绝对值越小，升或降的速度就越慢。这是因为升或降的速度就越慢。这是因为据此有据此有)等号成立当且仅当等号成立当且仅当与与同方向或与同方向或与同方向同方向。且当。且当与同方向同方向时，时，取到最大值取到最大值。当当与与同方向同方向时，时，取到最小值取到最小值 第19页，本讲

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

14、量的所有分量 在在点点都都可微，则称向量值函数可微，则称向量值函数在点在点处可微处可微。第21页，本讲稿共35页 定义表明，定义表明，在点在点处可微，则处可微，则成立，成立，其用向量形式可简单地表示为其用向量形式可简单地表示为其中其中称为向量值函数称为向量值函数在点在点处的导数，处的导数，第22页，本讲稿共35页 而而称为向量值函数称为向量值函数在点在点处的处的JacobiJacobi矩阵。矩阵。设设具有二阶连续偏导数，且具有二阶连续偏导数，且则矩阵则矩阵称为函数称为函数关于变量关于变量的二阶导数，简记为的二阶导数，简记为。也称为多元实值也称为多元实值函数函数的的HesseHesse矩阵。矩阵

15、。例例1.9 P21第23页，本讲稿共35页 几个特殊的向量值函数的导数公式：几个特殊的向量值函数的导数公式：（1）；（2）；（3）；（4）设设，其中，其中。则。则利用（利用（4），可得多元函数展开到三项的），可得多元函数展开到三项的Taylor公式公式（1.29）或或（1.31）这个公式与一元函数展开到三项的这个公式与一元函数展开到三项的Taylor公式是相对应的。公式是相对应的。多元函数的多元函数的Taylor展开式在最优化方法中十分重要，展开式在最优化方法中十分重要，许多方法及其收敛性的证明都是从它出发的。许多方法及其收敛性的证明都是从它出发的。第24页，本讲稿共35页 1.凸集凸集1.

16、6 凸函数与凸规划凸函数与凸规划 直观上，凸集就是空间中内部无直观上，凸集就是空间中内部无“洞洞”，边界又不向，边界又不向内凹的一些点的集合，其基本特征是该集合中任意两点内凹的一些点的集合，其基本特征是该集合中任意两点间的线段仍然属于这个集合。间的线段仍然属于这个集合。非凸集非凸集 凸集凸集 空间中两点间的线段是由点的凸组合定义的。空间中两点间的线段是由点的凸组合定义的。定义定义1.12 设设是是中的中的个已知点。个已知点。点点，若存在满足，若存在满足的非负实数的非负实数 对于对于 使得使得，则称，则称是是的一个凸组合。的一个凸组合。第25页，本讲稿共35页又若又若是满足是满足的正实数，则称的

17、正实数，则称是是的一个严格凸组合。的一个严格凸组合。两点两点的的凸组合凸组合恰是连接两点的恰是连接两点的的的线段。线段。线段，而严格凸组合是不含端点线段，而严格凸组合是不含端点 定义定义1.13 1.13 设集合设集合。如果。如果中任意两点的中任意两点的，那么集合，那么集合称为凸集。称为凸集。任意凸组合仍然属于任意凸组合仍然属于规定：空集是凸集。规定：空集是凸集。思考思考：空间中三个不同点的凸组合的集合，空间中：空间中三个不同点的凸组合的集合，空间中四个不同点的凸组合的集合四个不同点的凸组合的集合.常见的凸集有超平面，直线，球常见的凸集有超平面，直线，球.定理定理1.5 凸集的交集是凸集。凸集

18、的交集是凸集。第26页，本讲稿共35页2.凸函数凸函数定义定义1.16 设设，其中，其中为凸集。若对于为凸集。若对于中的任意互异两点中的任意互异两点和任意一对满足和任意一对满足的非负实数的非负实数，总有总有则称则称是定义在凸集是定义在凸集上的凸函数。又若对于任意上的凸函数。又若对于任意的正实数的正实数，总有，总有一对满足一对满足则称则称是定义在凸集是定义在凸集上的严格凸函数。上的严格凸函数。第27页，本讲稿共35页若若是凸集是凸集上的（严格）凸函数，则称上的（严格）凸函数，则称是凸集是凸集上的（严格严格）凹函数凹函数。凸函数有以下重要性质。凸函数有以下重要性质。定理定理1.6 （1）若）若是定

19、义在凸集是定义在凸集上的凸函数，上的凸函数，是是也是也是上的凸函数。上的凸函数。任意的非负实数，则任意的非负实数，则（2）若）若是定义在凸集是定义在凸集上的凸函数，则上的凸函数，则也是也是上的凸函数。上的凸函数。由定理由定理1.6易见，定义在凸集上的任意有限个凸函数易见，定义在凸集上的任意有限个凸函数的任意非负组合仍然是凸函数。的任意非负组合仍然是凸函数。例例1.10第28页，本讲稿共35页定理定理1.7 设，其中，其中为非空凸集，若为非空凸集，若是凸函数，则对于任意实数是凸函数，则对于任意实数，水平集水平集是凸集。是凸集。证证 若若是空集，则是凸集。以下设是空集，则是凸集。以下设非空。任取非

20、空。任取，则，则。又设。又设但但，根据，根据的凸性，必有的凸性，必有即即。因此，。因此，是凸集。是凸集。判断一个函数是否为凸函数，一般说来，是比较困判断一个函数是否为凸函数，一般说来，是比较困难的。但当函数可微时，有以下几个判定定理。难的。但当函数可微时，有以下几个判定定理。定理定理1.7 设设第29页，本讲稿共35页定理定理1.8 设设是可微函数，其中是可微函数，其中为为凸集。则凸集。则)为凸函数的充要条件是对于为凸函数的充要条件是对于中的任意两点中的任意两点，都有，都有)为严格凸函数的充要条件是对于为严格凸函数的充要条件是对于中的任意中的任意都有都有两个互异点两个互异点 定理定理1.8有明

21、显直观的几何解释。有明显直观的几何解释。可微函数为凸函数的充要条件是在其可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面（切定义域凸集中任一点处的切平面（切线）都不在曲面（曲线）的上方。右线）都不在曲面（曲线）的上方。右图画出了一维的情形。图画出了一维的情形。第30页，本讲稿共35页定理定理1.9 设设是二次可微函数，是二次可微函数，为非为非空开凸集。空开凸集。则则为为上凸函数的充要条件是上凸函数的充要条件是Hesse矩阵矩阵在在上处处半正定。上处处半正定。定理定理1.10 设设是二次可微函数，是二次可微函数，为非为非空凸集，空凸集，若若的的Hesse矩阵矩阵在在上处处正定，则上处

22、处正定，则是是上的严格凸函数。上的严格凸函数。这个命题的逆命题不真这个命题的逆命题不真。例如，例如，在在上为严格凸函数，上为严格凸函数，在在处是处是半正定的。半正定的。但是它的但是它的Hesse矩阵矩阵第31页，本讲稿共35页3.凸规划凸规划 设设是定义在非空凸集是定义在非空凸集上的凸函数，上的凸函数，则形式为则形式为（1.36）的最优化问题称为凸规划问题，简称凸规划。换言之，的最优化问题称为凸规划问题，简称凸规划。换言之，定义在凸集上的凸函数的极小化问题是凸规划问题。定义在凸集上的凸函数的极小化问题是凸规划问题。若若都是都是上的凹函数，上的凹函数，都是都是上的线性函数，容易验证集合上的线性函

23、数，容易验证集合是凸集。在这种情况下，凸规划（是凸集。在这种情况下，凸规划（1.36）可以表示成如下形式）可以表示成如下形式（1.37）第32页，本讲稿共35页下面的定理指出了凸规划的一些重要性质。下面的定理指出了凸规划的一些重要性质。定理定理1.11 设设是凸规划（是凸规划（1.36）的局部极小点。则）的局部极小点。则i）是（是（1.36）的全局极小点；）的全局极小点；ii）当）当是严格凸函数时，是严格凸函数时，是（是（1.36）的唯一极小点；）的唯一极小点；iii）（）（1.36）的全部极小点的集合是凸集。）的全部极小点的集合是凸集。定理定理1.12 设设是可微凸函数，是可微凸函数，是非空

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

25、矩阵。若是正定的，则（是正定的，则（1.38）称为正定）称为正定二次函数二次函数。，注意到注意到，于是由定理于是由定理1.10得知：正定二次得知：正定二次函数是严格凸函数。在最优化算法构造中，正定二次函数函数是严格凸函数。在最优化算法构造中，正定二次函数起着特殊的作用，本书的许多章节都要涉及它。起着特殊的作用，本书的许多章节都要涉及它。第34页，本讲稿共35页形式为形式为（1.39）的最优化问题称为二次规划问题，简称二次规划。若的最优化问题称为二次规划问题，简称二次规划。若 是半正定的或正定的，则（是半正定的或正定的，则（1.39）称为二次凸规划。）称为二次凸规划。定理定理1.14 一个一个 对称矩阵对称矩阵 为正定矩阵的充为正定矩阵的充要条件是条件是 的各阶主子式皆大于零。的各阶主子式皆大于零。第35页，本讲稿共35页