论文题目: 0-1二次规划的全局最优性条件及算法
论文类型: 博士论文
论文专业: 运筹学与控制论
作者: 陈伟
导师: 张连生
关键词: 二次规划,全局优化,全局最优性条件,填充函数,整数规划
文献来源: 上海大学
发表年度: 2005
论文摘要: 全局优化问题广泛见于工程、国防、经济等诸多重要领域,是数学规划理论的一个重要研究领域。本文首先讨论一类特殊结构的全局优化问题:二次规划的全局优化问题。我们给出了0-1二次规划的全局最优性条件,并讨论了其相应的算法。然后,对于一般结构的全局优化问题,我们给出了一个新的无参数的填充函数方法。 本论文的第一章介绍全局优化理论的一些研究成果。第二章讨论无约束0-1二次规划的全局最优性条件。在第二节得到一个充分条件和一个必要条件的基础上,我们希望能够得到一些充要条件。为此,我们首先在第三节中给出在线性约束条件下,(?)成为一个凸的二次函数的全局极大点的充分必要条件。从这个结论出发,在第四节,我们得到了无约束0-1二次问题全局最优的充分必要条件及其等价形式。在第五节,我们将注意力放在全局最优的必要条件上。我们得到的必要条件都不含对偶变量,仅用到原问题的数据。这样,这些条件在实际中都是可以被检验的。进一步,为了使必要条件在实际中易被检验、易操作,我们降低了必要条件中的维数,在比原问题维数更低的空间中,给出一些简洁的必要条件,以达到方便检验的目的。 在第三章,我们进一步研究有约束的0-1二次规划的全局最优条件。对于带有线性不等式约束的0-1二次问题,我们在第一节中得到了它全局最优的充分条件和必要条件。必要条件也不含对偶变量。当系数矩阵正定时,我们建立了原0-1问题的解与松弛问题的解之间的联系。对于带有线性等式约束的0-1二次问题,我们在第二节证明了一个带有线性等式约束的0-1二次规划问题,它的全局最优解集和其相应的罚问题的全局最优解集是相等的。这样,带有线性等式约束的0-1二次问题的解,可以通过无约束0-1二次规划问题的解得到。第三章的另一个内容是讨论0-1二次规划问题的实际应用。将我们得到的一些结论运用于极大团问题和二次分派问题,我们得出了一些相关的结论。 将全局最优条件发展成为可实现的算法,是全局优化研究中的重要的工作。本文的第四章讨论无约束0-1二次规划问题的算法。首先我们将原0-1问题化为一个等价的半正定的0-1二次问题。在得到这个半正定二次问题的松弛解x之后,取与x“最接近的”0-1解y,在一定的条件之下,y就是原0-1问题的全局最优解。由于松弛后的问题是凸的二次规划问题,可以在多项式时间内求解,所以,我们的算法是可实现的。为了确定y是否是原问题的最优解,我们设计了三种算法。在研究了第二章所给
论文目录:
摘要
Abstract
第一章 全局优化研究的一些新进展
§1.1 引言
§1.2 全局最优性条件简介
§1.2.1 D.C.规划、反凸规划
§1.2.2 二次规划
§1.3 全局优化的确定性算法概述
§1.4 相关定义和假设
第二章 无约束0-1二次规划问题的全局最优性条件
§2.1 引言
§2.2 充分条件和必要条件
§2.3 带有线性约束的二次规划的全局最优条件
§2.4 0-1问题全局最优的充分必要条件
§2.5 0-1问题全局最优的一些必要条件
第三章 有约束的0-1二次规划的全局最优性条件
§3.1 带有不等式约束的0-1二次规划的的全局最优条件
§3.2 带有等式约束的0-1二次规划问题
§3.3 0-1二次规划问题的应用
§3.3.1 极大团问题
§3.3.2 二次分派问题
第四章 无约束0-1二次规划的算法
§4.1 引言
§4.2 无约束0-1二次规划问题的一个算法
§4.3 充分条件之间的关系
§4.4 对算法的进一步讨论
第五章 无参数填充函数方法
§5.1 引言
§5.2 整变量问题的填充函数方法
§5.3 连续变量问题的填充函数
§5.4 算法
§5.5 算例
§5.5.1 测试问题
§5.5.2 整变量问题的计算结果
§5.5.3 连续变量问题的计算结果
§5.5.4 结论
参考文献
作者攻读博士学位期间完成的论文
致谢
发布时间: 2005-09-16
参考文献
- [1].{-1，1}二次规划算法及其应用研究[D]. 穆学文.西安电子科技大学2006
- [2].连续与离散单调优化和不定二次规划算法研究[D]. 黎健玲.上海大学2007
- [3].求解约束优化问题的序列二次规划方法研究[D]. 胡清洁.湖南大学2008
- [4].求解半定约束二次规划逆问题的数值方法[D]. 肖现涛.大连理工大学2009
- [5].强次可行方法与序列二次约束二次规划算法的研究[D]. 唐春明.上海大学2008
- [6].二次规划的线性锥规划表示及算法研究[D]. 郭晓玲.清华大学2014
- [7].生产过程稳态模型的寻优方法及应用研究[D]. 李山春.中南大学2011
- [8].肿瘤异质性研究的非负矩阵分解模型[D]. 王法有.上海师范大学2017
- [9].基于优化理论的支持向量机学习算法研究[D]. 吴青.西安电子科技大学2009
相关论文
- [1].0-1规划问题的连续化方法研究及应用[D]. 李艳艳.大连理工大学2009
- [2].连续和整数非凸二次规划理论和方法研究[D]. 郑小金.上海大学2010
- [3].非线性规划中的精确罚函数[D]. 白富生.上海大学2003
- [4].全局优化的几种确定性方法[D]. 吴至友.上海大学2003
- [5].非线性全局优化的变换函数方法[D]. 王薇.上海大学2005
- [6].非线性全局优化中填充函数方法的研究[D]. 尚有林.上海大学2005
- [7].求全局最优化的几种确定性算法[D]. 杨永健.上海大学2005
- [8].非线性整数规划问题的若干新算法[D]. 王粉兰.上海大学2006
- [9].{-1，1}二次规划算法及其应用研究[D]. 穆学文.西安电子科技大学2006
- [10].连续与离散单调优化和不定二次规划算法研究[D]. 黎健玲.上海大学2007