论文部分内容阅读
带离散结构的非凸优化问题是最优化领域的一类重要问题,在现实生活中有许多应用,比如金融优化、网络和交通运输、信号处理和压缩感知等问题.由于这类问题具有组合性质,所以可行域通常是非凸的,在一般情况下此类问题是NP-难的.因此研究此类问题的求解算法既有重要意义,义极具挑战性.随着优化技术的发展,求解非凸优化问题的理论和算法也有了很大的发展,但这些算法也存在许多不足之处,比如计算时间长,求解效率有待提高等,只能用来求解小到中等规模的问题.本文在现有算法的理论基础之上,针对几类特殊的带离散结构的非凸优化问题,提出了更有效的求解方法.以下是本文的主要工作:第一章,我们概括介绍了带离散结构的非凸优化问题的研究背景,并简单介绍了本文所研究的问题.最后给出了本文的主要研究结果和贡献.第二章,我们详细介绍了文中所考虑的三类特殊的带离散结构的非凸优化问题的研究现状和进展.第三章,我们研究了求解一般凸优化问题稀疏解的方法.寻找优化问题的稀疏解在现实生活中经常遇到,特别是必须控制决策变量非零元素个数的时候.我们提出了一种序列凸近似的方法来求解稀疏凸优化问题的正则化形式,该方法基于l0函数的D.C.近似,通过序列地求解凸子问题产生一系列近似解.我们证明了算法能够收敛到近似正则化问题的KKT点.通过利用混合整数规划等价形式的l1精确罚函数,我们给出了lo正则项的一个分段线性D.C.近似.我们分析了不同的D.C.近似在计算有限多元化均值方差投资组合问题时的数值表现.数值结果表明该方法在寻找凸优化问题的稀疏解方面是有优势的.第四章,我们考虑了概率约束优化问题,其中随机变量服从有限离散分布.一般来说,这类问题是非凸的,可以等价地写成混合整数规划问题.通过利用概率约束的特殊结构,我们提出了一种交替方向法来求解问题的近似最优解.我们的算法在迭代中交替地求解一个凸二次规划问题和一个0-1背包问题.最后,我们在一定条件下证明了算法的一阶收敛性,并报告了算法对数值算例的求解结果,这些算例包括带VaR约束的投资组合问题和带概率约束的运输问题.数值结果表明我们的方法能够在合理的时间内找到高质量的最优解,我们方法的表现要优于CPLEX和其他已有的方法,特别是对大规模的问题第五章,我们考虑基于巴塞尔协议风险度量的资产配置问题.与金融危机之前相比,金融机构在现阶段需要满足更加严格的资本要求.资本要求的明显增长使得银行在做出资产配置决策的时候必须要考虑新的资本要求约束.在本章我们提出了一类带监管资本要求的资产配置模型,其中监管资本要求既包括含120种VaR组合的巴塞尔协议2.5,也包括含60种CVaR组合的巴塞尔协议Ⅲ.我们提出了一种基于增广拉格朗日函数的交替方向法来求解这个模型.在一定的条件下,我们给出了算法产生点列的聚点所满足的一阶最优性条件.数值试验结果表明:与其它方法相比,我们的算法是有比较优势的,特别是在问题是非凸的情况下,我们的算法优势更明显.