《数值最优化1.ppt》由会员分享，可在线阅读，更多相关《数值最优化1.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数值最优化数值最优化主讲：陈高洁 推荐教材：推荐教材：李董辉等，李董辉等，数值最优化数值最优化，科学出版社，科学出版社参考教材参考教材：1、袁亚湘，孙文瑜，、袁亚湘，孙文瑜，最优化理论与方法最优化理论与方法，科学出版社科学出版社2、陈宝林，、陈宝林，最优化理论与算法最优化理论与算法，清华大学出版社，清华大学出版社前言前言一、什么是最优化一、什么是最优化 最优化是一门应用性相当广泛的学科，它讨论决策最优化是一门应用性相当广泛的学科，它讨论决策问题的最佳选择之特性，寻找最佳的计算方法，研究这问题的最佳选择之特性，寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。些计算方法的理论性质及
2、其实际计算表现。应用范围：信息工程及设计、经济规划、生产管理、交应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。通运输、国防工业以及科学研究等诸多领域。二、包含的内容二、包含的内容按照优化思想分为经典方法与现代方法。按照优化思想分为经典方法与现代方法。经典方法主要包括：线性规划、非线性规划、整数经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等规划、动态规划等现代方法主要包括：随机规划、模糊规划、模拟退现代方法主要包括：随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等。火算法、遗传算法、禁忌搜索和人工神经网络等。我们学习的内
3、容主要是经典的最优化方法。我们学习的内容主要是经典的最优化方法。内容包括无约束最优化方法、约束最优化方法、线内容包括无约束最优化方法、约束最优化方法、线性规划及其对偶规划等主要内容。性规划及其对偶规划等主要内容。三、学习方法三、学习方法1、认真听讲，课后及时复习巩固，并主动完成课、认真听讲，课后及时复习巩固，并主动完成课后习题。后习题。2、多看参考书，通过不同学者的讲述，全方位理、多看参考书，通过不同学者的讲述，全方位理解最优化方法的思想方法和应用，特别是计算方法。解最优化方法的思想方法和应用，特别是计算方法。3、学以致用，通过最优化方法的学习，培养研究、学以致用，通过最优化方法的学习，培养研
4、究生数学建模的能力和解决实际问题的能力。大家可生数学建模的能力和解决实际问题的能力。大家可以尝试对于一些实际问题，先建立数学模型，转化以尝试对于一些实际问题，先建立数学模型，转化为数学问题，通过一些算法解决。为数学问题，通过一些算法解决。课程内容课程内容一、基本概念与基础知识一、基本概念与基础知识 (第一章、第二章第一章、第二章)二、最优性条件二、最优性条件 (第二章、第八章第二章、第八章)三、各类算法三、各类算法 (其它各章其它各章)第一章第一章 引言引言第一节第一节 最优化问题概述最优化问题概述第二节第二节 凸集与凸函数凸集与凸函数1.最优化问题的提出最优化问题的提出例例1.1.11.1.
5、1（食食谱谱问问题题）设设市市场场上上可可以以买买到到n n种种不不同同的的食食品品，每每种种食食品品含含有有m种种营营养养成成分分。设设每每单单位位的的j j种种食食品品含含i i种种营营养养成成分分的的数数量量为为aij，i=1,，m,j=1,n.第第j种种食食品品的的单单位位价价格格为为cj,j=1,n.再再设设每每人人每每天天对对第第i种种营营养养成成分分的的需需求求量量为为bi,i=1,m.试试确确定定在在保保证证营营养养需需求求条条件件下下的的经经济济食食谱谱。例例1.1.21.1.2（数数据据拟拟合合问问题题）设设有有观观测测数数据据(xk,yk),k=1,5,其其值值由表由表1
6、.11.1给给出：出：k12345xkyk22.0142.9853.5085.0295.47试用一个简单的函数关系拟合这些数据。试用一个简单的函数关系拟合这些数据。2.最优化问题的数学模型最优化问题的数学模型 其中其中 是定义在是定义在 上的实值函数。上的实值函数。（1.1）无约束最优化问题无约束最优化问题 （）约束最优化问题约束最优化问题基本概念：基本概念：可行点、可行域可行点、可行域局部最优解局部最优解全局最优解全局最优解其中其中 到目前到目前为为止，大多数最止，大多数最优优化算法求到的都是化算法求到的都是局部极小点。局部极小点。为为了求得全局极小点，一种解决了求得全局极小点，一种解决办办
7、法是，先求出所有的局法是，先求出所有的局部极小点，然后再从中找出全局极小点。部极小点，然后再从中找出全局极小点。极大值问题与极小值问题的关系极大值问题与极小值问题的关系3.回顾几个数学概念回顾几个数学概念 梯度向量：梯度向量：Hessian矩阵：矩阵：例 梯度的性质梯度的性质：当梯度当梯度连续时连续时，第一，若第一，若，则则必垂直于必垂直于过过点点处处的等的等值值面；面；第二，梯度方向是函数具有最大第二，梯度方向是函数具有最大变变化率的方向。化率的方向。下面以下面以为为例来解例来解释这释这个性个性质质。下下图图是是该该函数的等函数的等值线图值线图。今考今考虑虑一点一点，不妨取坐，不妨取坐标为标
8、为。设设想有想有出出发发沿某个方向移沿某个方向移动动到了点到了点，其坐，其坐标标，那么目，那么目标标函数函数值值将将产产生如下生如下变变化量化量一动点从一动点从设为设为假定假定。试问试问：动动点沿哪个方向移点沿哪个方向移动动会使会使目标函数值有最多的下降或上升？目标函数值有最多的下降或上升？从从图图上看，上看，这这相当于相当于问问：在以点：在以点为圆为圆心、以心、以1 1为为半径半径的的圆圆周上，哪一个点具有最大的或最小的目周上，哪一个点具有最大的或最小的目标标函数函数值值。为为了一般地描述函数了一般地描述函数在点在点处处沿沿情况及情况及变变化速度，化速度，须须引入上升方向和下降方向及方向引入
9、上升方向和下降方向及方向导导数数的概念。的概念。方向的方向的变变化化函数函数在点在点处处沿沿方向的方向的变变化反映的是函数化反映的是函数在一条直在一条直线线上的上的变变化，空化，空间间中由一点中由一点和一方向和一方向所确定的直所确定的直线线方程方程为为 上升方向和下降方向上升方向和下降方向 设设是是连续连续函数。函数。若存在若存在，对对于于都有都有，则则称称方向是方向是在点在点处处的上升方向；若存在的上升方向；若存在对对于于都有都有，则则称称方向是方向是在点在点处处的下降方向。的下降方向。定定义义1.9 1.9 设设在点在点处处可微，可微，是非是非方向上的方向上的单单位向量。如果极限位向量。如
10、果极限零向量零向量存在，存在，则则称其称其为为函数函数在点在点处处沿沿方向的方向方向的方向导导数，数，。记记作作思考：思考：与的异同。的异同。若若，则则方向是方向是在点在点处处的上升方向；的上升方向；根据极限理根据极限理论论，易易见见若若，则则方向是方向是在点在点处处的下降方向。的下降方向。因此因此，方向方向导导数的正数的正负负决定了函数决定了函数值值的升降的升降。定理定理1.2 1.2 设设在点在点处处可微，可微，则则，其中其中是非零向量是非零向量方向上的方向上的单单位向量。位向量。定理定理1.2又表明：只要又表明：只要，则则方向是方向是在点在点处处的上升方向；只要的上升方向；只要，则则方向
11、是方向是在点在点处处的下降方向。的下降方向。函数函数值值升降的快慢升降的快慢则则是由方向是由方向导导数数绝对值绝对值的大小决的大小决定的。定的。绝对值绝对值越大，升或降的速度就越快；越大，升或降的速度就越快；绝对值绝对值越小，越小，升或降的速度就越慢。升或降的速度就越慢。这这是因是因为为据此有据此有)等号成立当且等号成立当且仅仅当当与与同方向或与同方向或与同方向同方向。且当。且当与同方向同方向时时，取到最大取到最大值值。当当与与同方向同方向时时，取到最小取到最小值值 )若若是是锐锐角，角，则则;若若是是钝钝角，角，则则。因此，方向因此，方向导导数又可以称数又可以称为为函数函数在点在点处处沿沿方
12、向的方向的变变化率。化率。使函数使函数值值下降最快的方向称下降最快的方向称为为最速下降方向。最速下降方向。最速下降方向为最速下降方向为 几个常用函数的梯度公式几个常用函数的梯度公式（1）若，则则，即，即（2）（3）；（4）.；一阶一阶Taylor 展开式：展开式：二阶二阶Taylor 展开式：展开式：多元函数的多元函数的Taylor展开式在最优化方法中十分重要，展开式在最优化方法中十分重要，许多方法及其收敛性的证明都是从它出发的。许多方法及其收敛性的证明都是从它出发的。首先将向量长度概念推广到首先将向量长度概念推广到Rn(或或Cn)中中.称为向量称为向量x,y的的数量积数量积(内积内积).将非
13、负实数将非负实数称为向量称为向量x的的欧氏范数欧氏范数.定义定义1.设设x=(x1,x2,xn)T,y=(y1,y2,yn)T Rn,将实数将实数向量和矩阵的范数向量和矩阵的范数 我我们们还还可可以以用用其其他他办办法法来来度度量量Rn中中向向量量的的“大大小小”.例例如如,对对于于x=(x1,x2)T Rn,可可以以用用一一个个x的的函函数数N(x)=max|xi|来来度度量量 x 的的“大大小小”,而而且且这这种种度度量量 x 的的“大大小小”的的方方法法计计算算起起来来比比欧欧氏氏范范数数方方便便.在在许许多多应应用用中中,对对度度量量x的的“大大小小”的的函函数数N(x)都都要要求求是
14、是正正定定的的、齐齐次次的的且且满满足足三三角角不不等等式式.下下面面我我们们给给出出向向量量范范数数的的一一般定义般定义.(1)|x|0(|x|=0当且仅当当且仅当x=0)(正定性正定性),(2)|x|=|x|,对任何对任何 R(或或 C)(齐次性齐次性),(3)|x+y|x|+|y|(三角不等式三角不等式).则称则称f(x)=|x|是是Rn(或或Cn)上的一个上的一个向量范数向量范数(或或模模).定义定义2.(向量的范数向量的范数)如果向量如果向量x Rn(或或Cn)的某个实值函的某个实值函数数f(x)=|x|，满足条件满足条件:下面给出几种下面给出几种常用的向量范数常用的向量范数,设设x
15、=(x1,x2,xn)T.容易证明前三种范数是的容易证明前三种范数是的p-范数范数特殊情况特殊情况,其中其中向量的向量的-范数范数(最大范数最大范数)向量的向量的1-范数范数向量的向量的p-范数范数(0p0,使得对一切使得对一切x Rn有有结结论论:如如果果在在一一种种范范数数意意义义下下向向量量序序列列收收敛敛时时,则则在在任任何何一种范数意义下该向量序列均收敛一种范数意义下该向量序列均收敛.定理定理3.,其中其中|为向量的为向量的任一种范数任一种范数.定义定义3.设设x(k)为为Rn中一向量序列中一向量序列,x*Rn,记记x(k)=(x1(k),xn(k)T,x*=(x1*,xn*)T.如
16、果如果则称则称x(k)收敛于收敛于x*.记为记为 下下面面我我们们将将向向量量范范数数概概念念推推广广到到矩矩阵阵上上去去.可可以以将将Rnn中中的的矩矩阵阵A=(aij)nn当当作作n2维维向向量量,则则由由向向量量的的2-范范数数可以得到可以得到Rnn中矩阵的一种中矩阵的一种范数范数称称为为A的的Frobenius范范数数.|A|F显显然然满满足足正正定定性性、齐齐次次性性及三角不等式及三角不等式.下面我们给出矩阵范数的一般定义下面我们给出矩阵范数的一般定义.定义定义4.(矩阵的范数矩阵的范数)如果矩阵如果矩阵A Rnn的的某个实值函数某个实值函数N(A)=|A|，满足条件满足条件:(1)
17、|A|0(|A|=0当且仅当当且仅当A=0)(正定性正定性)；(2)|cA|=|c|A|,c为为实数实数 (齐次性齐次性)；(3)对任意对任意A,B有有|A+B|A|+|B|(三角不等式三角不等式)(4)对任意对任意A,B有有|AB|A|B|(相容性相容性)；则称则称 N(A)是是Rnn上上的一个的一个矩阵范数矩阵范数(或或模模).上上面面我我们们定定义义的的F(A)=|A|F就就是是Rnn上上的的一一个个矩矩阵阵范数范数.上述条件上述条件(即不等式即不等式)就称为就称为矩阵范数与向量范数的相容矩阵范数与向量范数的相容性条件性条件.由由于于在在大大多多数数与与估估计计有有关关的的问问题题中中,
18、矩矩阵阵和和向向量量会会同同时时参参与与讨讨论论,所所以以希希望望引引进进一一种种矩矩阵阵的的范范数数,它它是是和和向向量量范范数数相相联联系系而而且且和和向向量量范范数数相相容容的的,即即对对任任何何向向量量x Rn及及矩矩阵阵A Rnn都成立都成立|Ax|A|x|.为此我们再引进一种矩阵的范数为此我们再引进一种矩阵的范数.定义定义5.(矩阵的算子范数矩阵的算子范数)设设x Rn,A Rnn,给出一种向给出一种向量范数量范数|x|v(如如v=1,2或或),相应地定义一个矩阵的非负函相应地定义一个矩阵的非负函数数可验证可验证|A|v满足满足定义定义4,所以所以|A|v是是Rnn上上矩阵的一个范
19、数矩阵的一个范数,称为称为A的的算子范数算子范数.定理定理4.设设|x|v是是Rn上的一个向量范数上的一个向量范数,则则|A|v是是Rnn上上矩矩阵的范数阵的范数,且满足相容条件且满足相容条件显然这种矩阵的范数显然这种矩阵的范数|A|v依赖于向量范数依赖于向量范数|x|v的具体含义的具体含义.也就是说也就是说,当给出一种具体的向量范数当给出一种具体的向量范数|x|v时时,相应地就相应地就得到了一种矩阵范数得到了一种矩阵范数|A|v.定理定理5.设设x Rn,A=(aij)Rnn,则有则有常用的算子范数常用的算子范数（称为（称为A的的行范数行范数）,（称为（称为A的的列范数列范数）,（称为（称为
20、A的的2-范数范数）.其其中中 max(ATA)表表示示ATA的的最最大大特特征征值值,由由于于矩矩阵阵2-范范数数与与ATA 的特征值有关，所以又称为的特征值有关，所以又称为A的的谱范数谱范数.例例.求矩阵求矩阵A的各种常用范数的各种常用范数解解:由于由于特征方程为容易计算计算较复杂对矩阵元素的变化比较敏感不是从属范数较少使用使用最广泛性质较好Jacobi矩阵矩阵设向量值函数设向量值函数连续可微连续可微.在在点的点的Jacobi矩阵为矩阵为例例4.凸集和凸函数凸集和凸函数 凸集和凸函数是线性规划和非线性规划都要涉及的凸集和凸函数是线性规划和非线性规划都要涉及的基本概念。关于凸集和凸函数的一些
21、定理在最优化基本概念。关于凸集和凸函数的一些定理在最优化问题的理论证明及算法研究中具有重要的作用。问题的理论证明及算法研究中具有重要的作用。凸集凸集 直观上，凸集就是空间中内部无直观上，凸集就是空间中内部无“洞洞”，边界又不，边界又不向向内凹的一些点的集合，其基本特征是该集合中任意两点内凹的一些点的集合，其基本特征是该集合中任意两点间的线段仍然属于这个集合。间的线段仍然属于这个集合。非凸集非凸集 凸集凸集 空间中两点间的线段是由点的凸组合定义的。空间中两点间的线段是由点的凸组合定义的。定定义义.设设是是中的中的个已知点。个已知点。点点，若存在，若存在满满足足的非的非负实负实数数 对于对于 使得
22、使得，则则称称是是的一个凸的一个凸组组合。合。又若又若是是满满足足的正的正实实数，数，则则称称是是的一个的一个严严格凸格凸组组合。合。两点两点的的凸凸组组合合恰是恰是连连接两点的接两点的的的线线段。段。线段，而严格凸组合是不含端点线段，而严格凸组合是不含端点 定定义义1.2.1 1.2.1 设设集合集合。如果。如果中任意两点的中任意两点的，那么集合，那么集合称称为为凸集。凸集。任意凸组合仍然属于任意凸组合仍然属于规定：空集是凸集。规定：空集是凸集。常见的凸集有超平面，直线，球常见的凸集有超平面，直线，球.凸函数凸函数定定义义1.16 设设，其中，其中为为凸集。若凸集。若对对于于中的任意互异两点
23、中的任意互异两点和任意一和任意一对满对满足足的非的非负实负实数数，总有总有则则称称是定是定义义在凸集在凸集上的凸函数。又若上的凸函数。又若对对于任意于任意的正的正实实数数，总总有有一对满足一对满足则则称称是定是定义义在凸集在凸集上的上的严严格凸函数。格凸函数。若若是凸集是凸集上的（上的（严严格）凸函数，格）凸函数，则则称称是凸集是凸集上的（严严格格）凹函数凹函数。凸函数有以下重要性质。凸函数有以下重要性质。定理定理6 （1）若）若是定是定义义在凸集在凸集上的凸函数，上的凸函数，是是也是也是上的凸函数。上的凸函数。任意的非负实数，则任意的非负实数，则（2）若）若是定是定义义在凸集在凸集上的凸函数
24、，上的凸函数，则则也是也是上的凸函数。上的凸函数。由定理由定理6易易见见，定，定义义在凸集上的任意有限个凸函数在凸集上的任意有限个凸函数的任意非的任意非负组负组合仍然是凸函数。合仍然是凸函数。定理定理1.7 设，其中，其中为为非空凸集，若非空凸集，若是凸函数，是凸函数，则对则对于任意于任意实实数数，水平集水平集是凸集。是凸集。判断一个函数是否为凸函数，一般说来，是比较困判断一个函数是否为凸函数，一般说来，是比较困难的。但当函数可微时，有以下几个判定定理。难的。但当函数可微时，有以下几个判定定理。定理定理7.设设定理定理8.设设二次二次连续连续可微，可微，则则下面的命下面的命题题等价：等价：（1
25、 1）函数）函数 是凸函数是凸函数.定理定理8有明显直观的几何解释。有明显直观的几何解释。可微函数为凸函数的充要条件是在其可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面（切定义域凸集中任一点处的切平面（切线）都不在曲面（曲线）的上方。右线）都不在曲面（曲线）的上方。右图画出了一维的情形。图画出了一维的情形。（2 2）对对任意任意，一元函数，一元函数是是0,1上的凸函数上的凸函数.（3 3）对对任意任意，下面不等式成立，下面不等式成立（4 4）梯度函数）梯度函数 单调单调（5 5）对对所有所有 半正定半正定.定理定理9.设设是二次可微函数，是二次可微函数，为为非非空开凸集。空开凸集
26、。则则为为上凸函数的充要条件是上凸函数的充要条件是Hesse矩矩阵阵在在上上处处处处半正定。半正定。定理定理10.设设是二次可微函数，是二次可微函数，为为非非空凸集，空凸集，若若的的Hesse矩矩阵阵在在上上处处处处正定，正定，则则是是上的上的严严格凸函数。格凸函数。这个命题的逆命题不真这个命题的逆命题不真。例如，例如，在在上上为严为严格凸函数，格凸函数，在在处处是是半正定的。半正定的。但是它的但是它的Hesse矩阵矩阵 凸规划凸规划 设设是定是定义义在非空凸集在非空凸集上的凸函数，上的凸函数，则形式为则形式为（1.36）的最的最优优化化问题问题称称为为凸凸规规划划问题问题，简简称凸称凸规规划
27、。划。换换言之，言之，定定义义在凸集上的凸函数的极小化在凸集上的凸函数的极小化问题问题是凸是凸规规划划问题问题。若若都是都是上的凹函数，上的凹函数，都是都是上的上的线线性函数，容易性函数，容易验证验证集合集合是凸集。在这种情况下，凸规划（是凸集。在这种情况下，凸规划（1.36）可以表示成如下形式）可以表示成如下形式（1.37）下面的定理指出了凸规划的一些重要性质。下面的定理指出了凸规划的一些重要性质。定理定理1.11 设设是凸是凸规规划（划（1.36）的局部极小点。）的局部极小点。则则i）是（是（1.36）的全局极小点；）的全局极小点；ii）当）当是是严严格凸函数格凸函数时时，是（是（1.36
28、）的唯一极小点；）的唯一极小点；iii）（）（1.36）的全部极小点的集合是凸集。）的全部极小点的集合是凸集。定理定理1.12 设设是可微凸函数，是可微凸函数，是非空是非空。凸集，凸集，则则是凸是凸规规划（划（1.36）的极小点的）的极小点的充要中任意一点中任意一点，总总有有。条件是，对于条件是，对于 定理定理1.12表明，凸规划（表明，凸规划（1.36）在最优点处的任何）在最优点处的任何容许方向（定义容许方向（定义4.3）都不是下降方向。）都不是下降方向。推推论论1.13 设设是可微凸函数，是可微凸函数，是非空是非空凸集，凸集，。若。若使得使得，则则是凸是凸规规划（划（1.36）的全局极小点
29、。）的全局极小点。二次函数与二次规划二次函数与二次规划函数函数（1.38）称称为为元二次函数，其中元二次函数，其中是是对对称矩称矩阵阵。若。若是正定的，是正定的，则则（1.38）称）称为为正定正定二次函数二次函数。，注意到注意到，于是由定理于是由定理1.10得知：正定二次得知：正定二次函数是严格凸函数。在最优化算法构造中，正定二次函数函数是严格凸函数。在最优化算法构造中，正定二次函数起着特殊的作用，本书的许多章节都要涉及它。起着特殊的作用，本书的许多章节都要涉及它。形式为形式为（1.39）的最优化问题称为二次规划问题，简称二次规划。若的最优化问题称为二次规划问题，简称二次规划。若 是半正定的或正定的，则（是半正定的或正定的，则（1.39）称为二次凸规划。）称为二次凸规划。定理定理1.14 一个一个 对称矩阵对称矩阵 为正定矩阵的充为正定矩阵的充要条件是条件是 的各阶主子式皆大于零。的各阶主子式皆大于零。