求解DC规划的全局收敛性算法和近似点算法

摘要

DC规划是一类重要的非线性规划,具有特殊的结构(可表为两个凸函数的差),在经济和工程等领域有着广泛应用,我们所熟知的不定二次规划及广义几何规划就属于DC规划.本文主要研究DC规划的理论和算法.第二章利用Tao提出的DCA算法并结合分枝定界技巧提出了一种解DC规划的全局收敛性算法,对于此算法的收敛性文中给出了理论性证明,并且数值试验也表明此算法是可行的.作为应用新算法应用于解决不定二次规划以及广义几何规划,从而也为这两类重要的非线性规划的求解提供了新的途径.第三章针对非光滑时的情形,在Sun给出的近似点算法的基础上运用Bregman函数提出一类修正的近似点算法,并且证明了这类算法的下降性及收敛性.这类算法不仅能够用来解决无约束DC规划问题,而且当所给出的Bregman函数为边界强制的情况下,这种算法能用来解决带凸约束的DC规划问题,当所给出的初始点为约束集合的内点时,则由算法所得到的点列均为约束集合的内点,则此算法实际为一内点算法.最后对一类求解凸规划的修正近似点算法进行了一些技术上的改进,并给出了收敛性和收敛率的证明.

目录

文摘

英文文摘

承诺书

第一章绪论

1.1 DC规划

1.1 DCA算法和近似点算法

1.3本文主要工作

第二章求解DC规划的全局收敛性算法

2.1用DCA算法局部求解(CDCP)问题

2.2全局求解箱约束DC规划

2.2.1 DCA算法局部解(P1)问题

2.2.2分枝定界法

2.2.3全局求解(P1)的算法BBDCA算法

2.3.4 BBDCA算法的收敛性

2.3全局求解带一般约束的DC规划问题

2.3.1分枝定界法

2.3.2算法BBDCA1

2.3.3算法BBDCA1的收敛性

第三章解DC规划的Bregman函数修正近似点算法

3.1预备知识

3.1.1 Bregman距离

3.1.2下半连续的正常凸函数的一些性质

3.2求解DC规划的修正近似点算法

3.2.1 Bregman函数修正的近似点算法

3.2.2算法BDC应用于求解无约束DC规划

3.2.3算法BDC应用于求解凸约束的DC规划

第四章关于广义近似点算法收敛性的一点讨论

4.1算法与收敛性

4.2收敛率

第五章数值试验

5.1不定二次规划

5.2解广义几何规划SGP

5.3解一般DC规划

第六章结束语

参考文献

致 谢

攻读硕士学位期间发表的主要论文