求全局最优化的几种确定性算法

论文题目: 求全局最优化的几种确定性算法

论文类型: 博士论文

论文专业: 运筹学与控制论

作者: 杨永健

导师: 张连生

关键词: 混合整数规划,非线整数性规划,非线性规划,全局最优解,填充函数,打洞函数,分支定界,积分函数

文献来源: 上海大学

发表年度: 2005

论文摘要: 最优化理论和方法的出现可以追溯到十分古老的极值问题,然而,它成为一门独立的学科还是在本世纪40年代末,是在1947年Dantzing提出求解一般线性规划问题的单纯形算法之后。随着工业革命、信息革命的不断深化,和计算机技术的巨大发展,至今短短的几十年,它得到了迅猛的发展。现在,解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速,新方法不断涌现,在经济、军事、科学等方面得到了广泛的应用,成为一门十分活跃的学科。全局最优化是最优化一个重要分支。相对于线性规划等分支,它在理论和算法上远没有那么成熟、完善,大多数的全局最优化算法缺少终止准则。但是现实社会对它有更多更迫切的要求,使得全局最优化工作者利用不同的数学理论和工具,提出了各式各样的算法,从理论到算法,都具有强大的生命力,而且需要进一步完善、深化。例如,在函数变换的基础上,提出了填充函数法;在非线性方程理论的基础上,提出了打洞函数法;在微分方程动力系统的基础上,提出了动力打洞算法;在积分原理的基础上,提出了积分水平集算法;在组合理论的基础上提出了分支定界算法,在随机和启发式基础上提出了模拟退火法、遗传算法等等。全局最优化算法,从算法的构造上大体可以分为确定型算法和随机型算法,例如,填充函数法、打洞函数法属于确定型算法;模拟退火法、遗传算法属于随机型算法。我们在这篇文章中仅仅考虑非线性规划的全局最优化确定型算法、非线性整数规划的全局最优化确定型算法和非线性混合整数规划的全局最优化确定型算法。这篇文章的主要目的就是,在研究已有确定型算法的基础上,尝试提出一些改进和创新。力图在算法效果方面有所提高,在理论方面有所深化。其内容详细情况如下:在第一章中,我们介绍了几种常见的全局最优化算法,以及他们的特点。这包括:填充函数法、打洞函数法、分支定界算法和积分水平集算法。每一个算法

论文目录:

摘要

Abstract

第一章全局最优化问题概述及基础知识

1.1 基础知识

1.2 全局优化中的确定性算法简介

1.2.1 分枝定界方法

1.2.2 填充函数方法

1.2.3 打洞函数方法

1.2.4 积分水平集算法

第二章非线性规划的全局最优化算法

2.1 引言

2.2 无约束全局最优化的填充函数法

2.2.1 新的填充函数及其性质

2.2.2 填充函数法及其数值结果

2.3 无约束全局最优化的变形打洞函数法

2.3.1 变形打洞函数及其性质

2.3.2 变形打洞函数法及其数值结果

2.4 无约束全局最优化的积分函数法

2.4.1 积分函数和向量序列

2.4.2 积分函数法及其数值结果

第三章离散全局最优化算法

3.1 预备知识

3.2 离散全局最优化的填充函数法

3.2.1 离散填充函数及其性质

3.2.2 离散填充函数算法和数值试验

3.3 离散全局最优化的变形打洞函数法

3.3.1 离散变形打洞函数及其性质

3.3.2 变形离散打洞函数算法和数值试验

3.4 离散全局最优化的逐次下降算法

3.4.1 一个辅助函数及其性质

3.4.2 逐次下降算法和数值试验

第四章混合整数非线性规划的近似全局最优化算法

4.1 引言

4.2 一般无约束混合整数非线性规划

4.3 无约束混合整数非线性规划的全局最优化算法

4.3.1 一类混合填充函数

4.3.2 混合填充函数算法

参考文献

附录：算例

作者攻读博士学位期间发表和已投稿的论文

致谢

发表意见书

博硕士学位论文同意发表声明

发布时间: 2006-12-12

参考文献

[1].群体决策、多目标最优化和全局最优化的若干结果[D]. 李静.上海大学2007
[2].非凸规划问题的全局最优性条件和全局最优化方法[D]. 全靖.上海大学2011
[3].全局优化的填充函数和变形打洞函数法[D]. 李忠豪.上海大学2012
[4].非凸优化问题的全局优化算法[D]. 周雪刚.中南大学2010

求全局最优化的几种确定性算法

猜你喜欢