优化中几个问题求解方法的新探讨

摘要

早在上个世纪六十年代,Bregman提出了一类特定的函数(后来被称之为Bregman函数),并根据相应的Bregman距离定义了点到闭凸集的一种广义投影——Bregman投影.此后在九十年代,Bauschke和Borwein提出了更为广泛的一类函数,Bregman-Legendre函数,并在这类函数的基础上研究Bregman距离和Bregman投影.近些年来,Bregman投影逐渐被应用到约束凸优化问题、凸可行问题(CFP)以及变分不等式问题等一系列优化问题上.其中,Byrne将Bregman用于求解凸可行问题的SGP(successive generalized projections)算法进一步扩展,得到了MSGP方法,并将其应用到凸可行问题的两个特例,一类凸约束优化问题和分裂可行问题(SFP)上,进而得到相应的IPA(interior point algorithm)和CQ算法.该文首先对IPA进行了修正,并证明了修正IPA的收敛性;然后将修正后的IPA分别应用到不等式约束凸优化问题、线性规划问题及非线性半定规划问题中,得到了求解这三类优化问题的新的内点算法,并将所得的算法与已有的算法进行了比较;然后专门讨论了分裂可行问题(SFP)的解法,首先给出了SFP的几种等价的优化问题,然后由等价的优化问题导出了几种SFP的解法,并以其中的三个方法进行简单数值实验,初步比较了其优劣;最后提出一些仍需进一步探讨的问题.值得一提的是,Byrne在做IPA收敛性分析时是从一般

目录

文摘

英文文摘

§1引言

§1.1 Bregman投影类方法的发展及相关概念

§1.2 MSGP算法和IPA

§1.3结构安排及符号说明

§2修正的IPA

§2.1 IPA的一种修正形式

§2.2修正算法的收敛性

§3不等式约束的凸优化问题的一种内点方法

§3.1算法的建立及其与传统对数障碍函数法的比较

§3.2解线性规划问题的一种内点算法

§3.3在非线性半定规划问题中的应用

§4分裂可行问题(SFP)的几种等价形式及算法探讨

§4.1 SFP的几种等价形式及相应算法

§4.2关于SFP算法的进一步探讨

§5后记

参考文献

致谢