连续和离散单调优化与不定二次规划算法的分析.pdf

摘要 全局优化问题主要研究如何寻找一个非凸优化问题的全局最优解．随着社会的 进步以及科学技术的发展，全局最优化广泛应用于企业生产管理、金融工程、工程 设计及控制、交通运输、农业预测、国防军事等重要领域．因此研究全局优化问题 在理论和应用方面都有重要的意义． 本论文主要研究两类特殊结构的全局优化问题——单调优化和不定二次规划． 单调优化是指目标函数和约束函数都是单调函数的全局优化问题．把单调优化问题 中的变量取值限制为整数，即为离散单调优化问题(通常也称为多维不可分离背包 问题)．单调优化问题的目标函数和约束函数不要求是凸的或是可分离的．不定二次 规划问题是指目标函数是不定二次函数，约束函数是线性函数或二次函数的全局优 化问题．把不定二次规划问题中的变量取值限制为整数，即为整数(离散)不定二次 规划问题．本文将着重研究带线性约束的连续和离散不定二次规划问题． 本论文分为七章，各章内容简要介绍如下： 第一章给出了单调优化和不定二次规划及其离散问题的描述及一些应用模型， 同时对本论文的主要工作作了简要介绍． 第二章首先介绍了一般全局优化的基本算法，然后介绍文献中连续和离散单调 优化及不定二次规划的现有算法． 第三章给出了一个求解单调优化问题的精确算法．该算法的框架是分枝定界， 并且与区域剖分、凸化、局部有哪些信誉好的足球投注网站三种基本策略相结合．区域剖分就是把区域剖分 成若干个子箱的并集，而且这些子箱的并集覆盖了可行域的边界；在每个子箱上使 用凸化外逼近方法得到目标函数最优值的上界；再结合局部有哪些信誉好的足球投注网站改进下界．我们对 该算法进行了数值实验，数值实验结果表明该算法是有效的，能在合理的时间内求 解中小规模的单调优化问题． 第四章对离散型的单调优化问题进行研究，提出了一个离散的Polyblock算法， 并且在此基础上结合凸化思想，对离散Polybloek算法进行改进，提高了界的质量， 从而提高算法效率．数值实验结果表明两个算法是有效的，而且数值比较结果表明 I 改进后的算法对具有较大区域的问题计算效果优于改进前的离散Polyblock算法． 第五章给出了一个求不定二次规划问题全局最优解的新算法．首先我们给出了 不定二次规划问题的三种下界的确定方法：线性逼近、拉格朗日对偶松弛和凸松弛． 然后利用这些下界并结合超长方形的两分法建立一个分枝定界算法．而且我们还证 明了经正交变换所得的不定二次可分离问题的凸松弛与拉格朗臼对偶松弛是等价 的．数值实验结果表明该算法是有效的． 第六章给出了不定二次整数规划问题的几种新的下界并且证明了它们之间的 关系．首先我们构造了问题的线性下方估计，以及通过D．c．分解构造了问题的两 种凸松弛；然后通过矩阵的Cholesky分解把不定二次整数规划化为等价的可分离问 题，进而应用对偶分解导出两种拉格朗日对偶界，并建立了凸松弛界和拉格朗日对 偶界的关系．本章提出的某些下界估计方法也可以应用到求(连续)不定二次规划问 题的算法中． 最后，我们在第七章总结了本文的主要工作，并讨论了有待进一步研究的问题． 关键词：全局最优化，单调优化，凸化方法，分枝定界，不定二次规划，凸松弛，拉格 朗日松弛． 11 Abstract Global aimstofindthe solutionofanonconvex optimization globaloptimal the of andthe themodem optimiza土ionproblem．Withprogress society development ofscienceand rolein fields． technology,globaloptimizationplays吼importantmany and such聃productionplanningma