一些DC规划问题的全局最优性条件和最优化方法

摘要

DC规划问题的目标函数是两个凸函数的差，它可以是无约束的或有约束的最优化问题.DC规划问题在现实世界中有很多的应用，主要包括经济、管理和工程等.DC规划问题是NP-难的,近三十多年里,对DC函数和DC规划的理论和算法的研究已经引起了国内外许多学者的关注，在许多文献中关于求解DC规划的算法越来越多.求解DC规划的方法中，割平面法、外逼近法、分支定界算法、次梯度算法、DCA算法是常用的方法.本文,我们主要在已有的二次规划、弱凸规划和多项式规划等研究的基础上,结合DC规划基本概念和相关性质，对一些特殊DC规划的全局最优性条件和全局最优化方法进行研究分析.
　　在本文,我们对于一些特殊的DC规划问题,给出了它的全局最优性充分条件和全局必要条件,并且根据这些条件设计出了新的局部优化算法和强局部优化算法.因为这些全局必要条件比Karush-Kuhn-Tucker(KKT)条件更强,所以,运用这些新的局部优化方法所得到的局部极小点可能会改进原问题的KKT点.此外,填充函数法是获得全局极小点的一种方法，因此,本文结合新的局部优化算法、强局部优化算法、全局充分条件和填充函数,给出了求解这些特殊的DC规划问题的全局优化算法.
　　本文结构安排如下：
　　第一章,我们简要介绍DC函数和DC规划的定义及性质,并介绍了国内外研究DC规划问题的最优性条件和最优化方法的现状,为后续的研究打好基础.
　　第二章,考虑带箱子约束的一类特殊的DC规划问题,记作(DC1).我们建立了问题(DC1)的全局充分条件和全局必要条件；然后，依据问题(DC1)的全局必要条件给出了求解问题(DC1)的一个新的局部优化方法（称为强局部算法)，该局部最优化方法不同于传统的局部优化方法,它是基于Karush-Kuhn-Tucker(KKT)条件建立的,是传统局部优化方法的改进.最后,结合问题(DC1)的局部优化方法、问题(DC1)的全局充分条件和一些辅助函数给出了求解问题(DC1)的全局优化方法,并通过一些数值算例来说明该全局最优化方法是有效的、稳定的方法.
　　第三章,在第二章的研究基础上进一步研究了带箱子约束的一类特殊的DC规划问题(BDC)的最优性条件和全局最优化算法.首先,我们给出了针对规划问题(BDC、的交替方向乘子法[NADMM],并利用规划问题(BDC)的全局必要性条件[GNC]设计了规划问题(BDC)的强局部算法[SLOMA].然后，我们结合算法[NADMM],强局部算法[SLOMA],规划问题(BDC)的全局充分性条件[GSC]和填充函数,设计出了规划问题(BDC)的一个全局最优化算法[GOMA].最后,通过一些数值算例将全局最优化算法[GOMA]与本文第二章设计的全局优化算法[GOM]进行了比较,说明了这两种全局最优化算法都是比较有效、可行的.
　　第四章,我们研究了带二次约束的DC规划（QDC).首先,我们通过构造小的区间,把规划问题(QDC)的可行域转化为一个箱子集.通过在规划问题（QDC)的全局极小点构造箱子集,然后在这个箱子集上考虑问题(QDC),我们推导出了问题(QDC)的全局必要条件[QGNC],再利用全局必要条件[QGNC]设计了规划（QDC)的强局部算法.然后,我们结合强局部算法和填充函数,设计出了规划问题（QDC)的一个全局最优化算法.最后,我们通过一些数值算例,考察了本章设计的全局最优化算法的有效性和稳定性.
　　第五章,我们对本文的研究进行总结,并对后续的研究工作作出了展望.

目录

第一个书签之前