欢迎来到天天文库
浏览记录
ID:31995461
大小:735.50 KB
页数:38页
时间:2019-01-30
《全局最优化中的积分—水平集方法与其最优性条件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、土连左堂亟±堂焦逢塞!了一系列理论成果.积分.水平集方法的主要特点是;在理论算法方面有很好的判断全局最优的终止准则.但在算法的实现方面,由于水平集在一般情况下无法求得,故在实现算法中只能采用Monte-Carl.随机取样来实现并在此基础上重新构造闭箱体,在理论上易丢弃全局最优点和最优值,该算法的收敛性至今一直无法解决.§1.2预备知识最优化问题是研究最优解的特征和算法的一门应用性很强的学科,最优化问题的一般形式是;裂嚣(12.1)s.t.z∈S、’其中s={z∈jp:gl≤o,i=1,2,⋯,女),,称s为可行域,,(功:Rn—R,称f(x)为目标函
2、数.因为mo.x{f0):z∈毋⋯rain{,(z):z∈s),所以最大化问题包含在上面模型中.进而,由于gi(x)≥o等价于一gi(x)≥o舰(。)=0等价于91(x)≥0和一吼(z)<0,,我们看到(1.2.1)包含了许名其它类型的约束.如果可行域是整个n维欧氏空间,那么下列问题称为无约束最优化问题,。竺嚣(1,z.2)如果s是一个多面体时,称问题(1.2.1)是线性约束的;此外,若目标函数也是线性的,该问题称为线性规划问题.当(1.2.1)中出现的函数至少有一个是非线性的,该问题称为非线性规划问题.当目标函数,和每个约束函数都是凸的时候,7问题
3、(1.2.1)称为凸规划问题.有时,当,是凸函数,s是凸集时,问题(1.2.1)也称为凸规划.在本文中,为了方便统称问题(1.2.1)和问题(1.2.2)为原问题.如果不加特别说明¨I始终表示欧几里得范数;可,(z)表示,(z)在点z处的梯度;v2f(X)在点z处的Hesse矩阵.定义1.2.1点矿∈s称为一个局部极小点,如果存在某个E>0,对于所有满足忙一矿0≤e的z∈S,有,∽)≤,(z),而,(矿)称为局部极小值.定义1.2.2点矿∈S称为一个局部极小点,如果对于所有z∈S,有,(矿)≤,(z),而,p)称为全局极小值.土塑盘堂亟主堂焦迨塞§在
4、全局最优化问题中,凸规划具有很好的性质,也就是当目标函数是凸的,可行域也是凸的时,凸规划的每个局部极小值就是全局极小值,所以我们可以应用求局部极小点的方法,求得全局极小点,已有的局部极小化算法对它都是有效的.而对于非凸的问题,可能存在很多局部极小点,其函数值不同于全局极小值,这样就使我们在求解全局最优化问题时面临很多困难,所以我们要首先研究目标函数在可行域占上的局部和整体性质.为此,我们首先回顾一些基本概念,下面的定义和定理在大部分最优化的教材上都有叙述和证明,可以参考【1l
5、2】.定义1.2.3函数,在S上的下确界,记作纽f{,(砷:z∈s),是,
6、在S上的最大下界;函数,在s上的上确界,记作sup(f扛):z∈s),是,在s上的最小下界.定义1.2.4在sc舻上的一个实值函数,称为李普希兹函数,如果存在一个常数L=L(,'鄙>0,使得对于所有z1,z2∈s,有lf(x2)一fCxl)l≤Ll。2一zlI其中工称为李普希兹常数.定理1.2.1设sc矽是凸的,,在包含s的一个开集上连续可微,并且在S上具有有界的梯度,则,在s上是李普希兹函数,且李普希兹常数L≥sup钏口,(z)lJ:£∈研定义1.2.5sC形称为闭集,如果s包含所有收敛点列{zi}Cs的极限点;sC舻称为紧集,如果s是闭的有界集.
7、由函数在紧集上的连续性,我们可以得到下列著名的魏尔斯特拉斯定理:定理1.2.2如果s是舻中—个非空紧集,,(z)是s上的连续函数,那么,(z)在s上至少有一个全局极小(极大)点.定义1.2.6集合s∈铲上定义的实值函数,在s上的点。处称为下半连续,如果有f(x)=11%~inf,(”);f在S上的点z处称为上半连续,如果有f(x)=uq。supf(Y).容易看出,函数在z点处既下半连续,又上半连续,则它在。点处连续.在定理1.2.2中如果将f的连续替换成下半连续(上半连续),那么定理仍然成立.上海大学硕士学位论文4第二章全局最优化的几种主要算法在这一
8、章中,我们将介绍了几种常见的全局最优化算法,以及他们的特点。这包括t填充函数法.分支定界算法积积分水平集算法.每—个算法都有各自的优缺点.首先,我们从算法思想到相关理论都给出一些深入浅出的说明,在此基础上,分析了各自的优点和缺点,为我们进一步的推广和构造新的算法,提供一些指导思想和思路。鉴于本人的研究方向,对于填充函数法、分支定界算法本文只作简要的介绍和说明并直接给出相关的算法及其定义和定理;对于积分水平集算法的介绍将较为详细,并给出相关定理证明,同时在本章中介绍了近年来对积分水平集算法研究的一些进展和对该算法的一些修正完善.§2.1分支定界方法分支
9、定界是一种应用广泛的计算技术,它在组合优化中已得到了成功的应用,解决了各式各样的问题.近年来,分支定界的思想
此文档下载收益归作者所有