非凸约束优化问题的理论研究与算法设计

发布时间：2021-03-26 13:49

　　非凸约束优化问题不仅是最优化领域中的重要问题,而且生产实际中的很多问题都可以归结为或者转化为非凸约束优化问题。凸优化问题具有很好的性质,一般情况下在多项式时间内可以求解。但是对一般的非凸约束优化问题而言,凸优化问题所具有的很多好的性质在非凸情形下都没有了。因此非凸优化问题的求解通常非常复杂,设计非凸约束优化问题的高效算法显得困难重重。本文对两类重要的非凸约束优化问题:带两个线性约束的非凸扩展信赖域子问题、带一个一般的二次约束的非凸扩展信赖域子问题（即广义的非凸Celis-Dennis-Tapia,CDT问题）进行了研究。这两类问题不仅是利用信赖域方法求解某些非凸约束优化问题的过程中,每一步迭代都需要求解的子问题,而且应用广泛。这两类问题与其Lagrangian对偶问题之间可能存在正的对偶间隙,与其半正定松弛问题存在相同的对偶间隙,这将导致这些问题的求解变得十分困难。由于这两类问题中都包含球约束,我们可以对这两类问题进行某种二阶锥重塑。本文的主要工作就是利用二阶锥重塑技术来缩小甚至是消除这些问题的对偶间隙。带两个线性约束的非凸扩展信赖域子问题是带一个单位球约束和两个线性不等式约束的非凸二... 

【文章来源】：北京邮电大学北京市 211工程院校 教育部直属院校

【文章页数】：116 页

【学位级别】：博士

【部分图文】：

图３－丨相交情形的可行域二維示意图??证明：显然，ｖ（ＳＰｌ）?＃?ｖ（￡７７？２）意味着?ｖ（ＳＰｌ）?＜?ｖ（五７７？２）?（＝?ｖ（ｇ尸?１））成立

第三章带两个线性约束的扩展信赖域子问题的理论研究与算法设计??隙的例子。??例３．１?（￡７７？２）问题的实例（它的可行域如图３－２所示）定义如下：??＾?－８５?３９?１?，?Ｉ＂?－１７?１?７?＼?０．７?１?＼?－０．８??２〇＝［?３９?－１２Ｊ５?〇＝［?２５?Ｊ?１＝［－〇－２ｊ，Ｚ７２＝［?０－８?＇??？?＝?２，?Ｃｊ?＝?０．３，?〇２?＝?—０．５．??－１．５?－１?－０．５?０?０．５?１?１．５??图３－２?例３．丨的可行域??通过计算可以求得该（￡７７？２）实例的最优值为ｖ（￡７７？２）?＝?６．８２２５，最优解为??ｆ?＝?（－０．３５，?０．２７５）７＇；该问题的二阶锥重塑模型的半正定松弛问题的最优值为??ｖ（Ｓ／ｎ）?＝?６．８２２５，最优解为??１?－０．３５?０．２７５??Ｘ＊?＾?—０．３５?０．１２２５?—０．０９６２?；??０．２７５?－０．０９６２?０．０７５６??该问题的经典的半正定松驰问题的最优值为ｖ（见）户２）?＝?－７４．９０１２，最优解为??１?－０．３５?０．２７５??ＸＳＤｐ

这个ＳＤＰＲ－ＳＯＣＲ间隙也比（￡７７？２）问题与其经典的半正定松弛模型之间的对偶间隙??小得多。下面的例３．２正是这样的例子。??例３．２?（￡ｎ？２）问题的实例（它的可行域如图３－３所示）定义如下：??［－１００?１０?１?［?４５?］?［?〇?１?［?〇＿９??２。＝｜＿?１。Ｏ．Ｈ〇．６＿｜’??ｎ?＝?２：?＝?０．１，?〇２?＝?—０．２．??：围??－１．５?－１?－０．５?０?０．５?１?１．５??图３－３?例３．２的可行域??通过计算可以求得该（￡７Ｖ？２）实例的最优值为ｖ（￡７７？２）?？－１２．５７９１，最优解??为ｆ?＝?（０．９６８２，?０．２５广；该问题的二阶锥重塑模型的半正定松弛问题的最优值为??ｖ（Ｓ尸１）?＝?—１３．１８９８，最优解为??１?０．９２２７?０．０３２５?＂??Ｘ＊？?０．９２２７?０．８９７８?０．０３４６?；??０．０３２５?０．０３４６?０．１０２２??５０??

【参考文献】：
期刊论文
[1]ON MAXIMA OF DUAL FUNCTION OF THE CDT SUBPROBLEM[J]. Xiong-da Chen (Reserach Development Center of Parallel Software, Institute of Software, Beijing 100080, China) Ya-xiang Yuan (State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Ssientific/Engineering C.  Journal of Computational Mathematics. 2001(02)



本文编号：3101691