最优化方法第一章_第1页
最优化方法第一章_第2页
最优化方法第一章_第3页
最优化方法第一章_第4页
最优化方法第一章_第5页
已阅读5页,还剩30页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第1页,课件共35页,创作于2023年2月

或解法:Lagrange乘子法1.2实例数据拟合问题原料切割问题运输问题营养配餐问题分配问题1.3基本概念1.最优化问题的向量表示法设

则(1)

第2页,课件共35页,创作于2023年2月

以向量为变量的实值函数定义向量间的序关系(定义1.1):等于=,小于,严格小于。由此(2)以向量为变量的实向量值函数最优化问题的一般形式

(3)第3页,课件共35页,创作于2023年2月

2.最优化问题的分类试验问题:用于检验、比较最优化方法优劣的一些最优化问题。3.术语目标函数等式约束

不等式约束容许解(点)容许集

第4页,课件共35页,创作于2023年2月

求解问题(3)是指:在容许集中找一点目标函数在该点取极小值,即对于容许集中的任,总有

意一点最优点(极小点)最优值最优解严格极小点局部非严格极小点严格极小点非严格极小点全局,使得第5页,课件共35页,创作于2023年2月

到目前为止,大多数最优化算法求到的都是局部极小点。为了求得全局极小点,一种解决办法是,先求出所有的局部极小点,然后再从中找出全局极小点。

4.极大值问题与极小值问题的关系第6页,课件共35页,创作于2023年2月

第7页,课件共35页,创作于2023年2月

1.4二维问题图解法二维极值问题有时可以用图解的方式进行求解,有明显的几何解释。例求解第8页,课件共35页,创作于2023年2月

图解法的步骤:,显然;②取并画出相应的曲线(称之为等值线).

③确定极值点位置,并用以往所学方法求之。

易知本题的极小值点。

再复杂点的情形见P13上的例1.7。虽然三维及以上的问题不便于在平面上画图,图解法失效,但仍有相应的等值面的概念,且等值面具有以下性质:①有不同函数值的等值面互不相交(因目标函数是单值函数的缘故);②等值面不会在区域的内部中断,除了极值点所在的等值面以外。这是由于目标函数是连续函数的缘故;①令第9页,课件共35页,创作于2023年2月

⑶等值面稠密的地方,目标函数值变化得比较快;等值面稀疏的地方,目标函数值变化得比较慢;⑷在极值点附近,等值面(等值线)一般近似地呈现为同心椭球面族(椭圆线族)。1.5梯度和Hesse矩阵本段讨论都基于对函数以下及今后的讨论中还经常要用到以下一些向量的知识。可微的假定。第10页,课件共35页,创作于2023年2月

与。

记作。向量也常用希腊字母等表示。向量内积的性质:ⅰ)(对称性);ⅱ)

(线性性);ⅲ),当且仅当时,(正定性);向量的内积设则称为向量的内积,其实,第11页,课件共35页,创作于2023年2月

向量的长单位向量

向量的夹角,

向量的正交

(正交性)

1.可微定义1.7设.如果存在维向量对于可任意小的维非零向量,总有在点那么称函数处可微。第12页,课件共35页,创作于2023年2月

若令便得到(1.9)的等价形式

.(1.10)

2.梯度定理1.1若在点处可微,则在该点关于各个变量的一阶偏导数存在,并且

定义1.8以函数的个偏导数为分量的向量称为在点处的梯度,记为。。第13页,课件共35页,创作于2023年2月

梯度也称为函数关于变量于是,(1.10)可写为这个公式与一元函数展开到两项的Taylor公式是相对的。

梯度的性质:当梯度连续时,第一,若,则必垂直于过点处的等值面;的一阶偏导数。第14页,课件共35页,创作于2023年2月

第二,梯度方向是函数具有最大变化率的方向。下面以为例来解释这个性质。上图是该函数的等值线图。今考虑一点,不妨取坐标为。设想有出发沿某个方向移动到了点,其坐标,那么目标函数值将产生如下变化量一动点从设为假定。试问:动点沿哪个方向移动会使目标函数值有最多的下降或上升?从图上看,这相当于问:在以点为圆心、以1为半径的圆周上,哪一个点具有最大的或最小的目标函数值。第15页,课件共35页,创作于2023年2月

为了一般地描述函数在点处沿情况及变化速度,须引入上升方向和下降方向及方向导数的概念。方向的变化函数在点处沿方向的变化反映的是函数在一条直线上的变化,空间中由一点和一方向所确定的直线方程为

上升方向和下降方向设是连续函数。第16页,课件共35页,创作于2023年2月

若存在,对于都有,则称方向是在点处的上升方向;若存在对于都有,则称方向是在点处的下降方向。定义1.9设在点处可微,是非方向上的单位向量。如果极限零向量存在,则称其为函数在点处沿方向的方向导数,。记作思考:与的异同。第17页,课件共35页,创作于2023年2月

若,则方向是在点处的上升方向;根据极限理论,易见若,则方向是在点处的下降方向。因此,方向导数的正负决定了函数值的升降。定理1.2设在点处可微,则,其中是非零向量方向上的单位向量。定理1.2又表明:只要,则方向是在点处的上升方向;只要,则方向是在点处的下降方向。第18页,课件共35页,创作于2023年2月

函数值升降的快慢则是由方向导数绝对值的大小决定的。绝对值越大,升或降的速度就越快;绝对值越小,升或降的速度就越慢。这是因为据此有ⅰ)等号成立当且仅当与同方向或与同方向。且当与同方向时,取到最大值

。当与同方向时,取到最小值

第19页,课件共35页,创作于2023年2月

ⅱ)若是锐角,则;若是钝角,则。因此,方向导数又可以称为函数在点处沿方向的变化率。使函数值下降最快的方向称为最速下降方向。最速下降方向为例1.8P19第20页,课件共35页,创作于2023年2月

几个常用函数的梯度公式(1)若,则,即(2)(3);(4).;;2.Hesse矩阵问:函数关于变量的二阶导数又是什么?先来看什么是向量值函数的可微。定义1.11设。若的所有分量

在点都可微,则称向量值函数在点处可微。

第21页,课件共35页,创作于2023年2月

定义表明,在点处可微,则成立,其用向量形式可简单地表示为其中称为向量值函数在点处的导数,第22页,课件共35页,创作于2023年2月

而称为向量值函数在点处的Jacobi矩阵。设具有二阶连续偏导数,且则矩阵称为函数关于变量的二阶导数,简记为。也称为多元实值函数的Hesse矩阵。例1.9P21第23页,课件共35页,创作于2023年2月

几个特殊的向量值函数的导数公式:(1);(2);(3);(4)设,其中。则利用(4),可得多元函数展开到三项的Taylor公式(1.29)或(1.31)这个公式与一元函数展开到三项的Taylor公式是相对应的。多元函数的Taylor展开式在最优化方法中十分重要,许多方法及其收敛性的证明都是从它出发的。第24页,课件共35页,创作于2023年2月

1.凸集1.6凸函数与凸规划直观上,凸集就是空间中内部无“洞”,边界又不向内凹的一些点的集合,其基本特征是该集合中任意两点间的线段仍然属于这个集合。非凸集凸集空间中两点间的线段是由点的凸组合定义的。定义1.12设是中的个已知点。点,若存在满足的非负实数

对于使得,则称是的一个凸组合。第25页,课件共35页,创作于2023年2月又若是满足的正实数,则称是的一个严格凸组合。两点的凸组合恰是连接两点的的线段。线段,而严格凸组合是不含端点定义1.13设集合。如果中任意两点的,那么集合称为凸集。任意凸组合仍然属于规定:空集是凸集。

思考:空间中三个不同点的凸组合的集合,空间中四个不同点的凸组合的集合.常见的凸集有超平面,直线,球.定理1.5凸集的交集是凸集。第26页,课件共35页,创作于2023年2月2.凸函数定义1.16设,其中为凸集。若对于中的任意互异两点和任意一对满足的非负实数,

总有则称是定义在凸集上的凸函数。又若对于任意的正实数,总有一对满足则称是定义在凸集上的严格凸函数。第27页,课件共35页,创作于2023年2月若是凸集上的(严格)凸函数,则称是凸集上的(严格)凹函数。凸函数有以下重要性质。定理1.6

(1)若是定义在凸集上的凸函数,是也是上的凸函数。任意的非负实数,则(2)若是定义在凸集上的凸函数,则也是上的凸函数。由定理1.6易见,定义在凸集上的任意有限个凸函数的任意非负组合仍然是凸函数。例1.10第28页,课件共35页,创作于2023年2月定理1.7设,其中为非空凸集,若是凸函数,则对于任意实数,

水平集是凸集。证若是空集,则是凸集。以下设非空。任取,则

。又设但,根据的凸性,必有即。因此,是凸集。判断一个函数是否为凸函数,一般说来,是比较困难的。但当函数可微时,有以下几个判定定理。定理1.7设第29页,课件共35页,创作于2023年2月定理1.8设是可微函数,其中为凸集。则ⅰ)

为凸函数的充要条件是对于中的任意两点,都有ⅱ)

为严格凸函数的充要条件是对于中的任意都有两个互异点定理1.8有明显直观的几何解释。可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面(切线)都不在曲面(曲线)的上方。右图画出了一维的情形。第30页,课件共35页,创作于2023年2月定理1.9设是二次可微函数,为非空开凸集。则为上凸函数的充要条件是Hesse矩阵在上处处半正定。定理1.10设是二次可微函数,为非空凸集,若的Hesse矩阵在上处处正定,则是上的严格凸函数。这个命题的逆命题不真。例如,在上为严格凸函数,在处是半正定的。但是它的Hesse矩阵第31页,课件共35页,创作于2023年2月3.凸规划设是定义在非空凸集上的凸函数,则形式为(1.36)的最优化问题称为凸规划问题,简称凸规划。换言之,定义在凸集上的凸函数的极小化问题是凸规划问题。若都是上的凹函数,都

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论