广义非线性分式规划问题的近似算法

发布时间：2017-09-04 13:31

  本文关键词：广义非线性分式规划问题的近似算法

  更多相关文章： 非凸优化问题 非线性分式规划问题 全局优化 近似算法 计算复杂度

【摘要】：非凸优化问题是一类重要的优化问题,它能过广泛应用于分子生物学、环境工程、信息技术和工业制造等领域.一般情况下这类问题存在大量的非全局最优解的局部最优解,求解起来比较困难.因此,近年来引起许多工作者的关注,求解方法越来越多,但这些方法要么没有给出其计算复杂性,要么在理论上无法保证获得的解的质量.本文针对一类广义分式规划问题的两种特殊形式分别提出相应的近似算法,不仅证明了这些近似算法能够为优化问题获得一个近似最优解,而且讨论了这些近似算法的计算复杂性.当组成目标函数的比式函数的个数固定时这些近似算是完全多项式近似算法.主要内容如下：第一章,首先给出本文研究的优化问题,其次简要介绍该优化问题的应用背景、理论意义及当前研究工作,最后介绍本文的主要工作.第二章,本章针对一类目标函数是带正系数的分式多项式函数的优化问题提出一种近似算法.通过引入变量将原问题转化为一个等价问题,根据该等价问题的特点,构造一个求解原问题的近似算法,并从理论上证明该近似算法的收敛性和分析其计算复杂性,数值算例也说明该近似算法是有效可行的.第三章,本章考虑一类具有特殊性质的一般形式的分式规划问题,采用类似于第二章的方法,将原问题转化为一个等价问题.利用等价问题的特征,设计一个求其解近似最优解的近似算法,从而获得原问题一个近似最优解.同时,从理论上证明该算法的收敛性并给出该近似算法的计算复杂性,数值算例表明其是一个有效可行的近似算法.
【关键词】：非凸优化问题 非线性分式规划问题 全局优化 近似算法 计算复杂度
【学位授予单位】：河南师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221
【目录】：

• 摘要3-4
• ABSTRACT4-8
• 第一章 绪论8-14
• 1.1 研究模型8-9
• 1.2 相关工作9-11
• 1.3 主要内容11-14
• 第二章 一类分式规划问题的近似算法14-28
• 2.1 引言14
• 2.2 原问题的等价转化14-20
• 2.3 近似算法及其计算时间复杂度20-24
• 2.3.1 近似算法20-22
• 2.3.2 近似算法的计算时间复杂性22-24
• 2.4 数值实验24-28
• 第三章 一类广义分式规划问题的近似算法28-42
• 3.1 引言28-29
• 3.2 算法的理论基础29-32
• 3.3 近似算法及其复杂度分析32-37
• 3.3.1 近似算法32-35
• 3.3.2 算法的计算复杂度分析35-37
• 3.4 数值实验37-42
• 结论42-44
• 参考文献44-48
• 致谢48-50
• 攻读学位期间发表的学术论文目录50-52

【相似文献】

中国期刊全文数据库 前10条

1 魏麒;蒋义伟;;一类两阶段杂交流水作业的近似算法(英文)[J];软件学报;2012年05期

2 刘振宏;组合最优化问题的近似算法[J];数学的实践与认识;1983年03期

3 马绍汉;一类限制树问题的复杂性及其近似算法[J];山东大学学报(自然科学版);1984年01期

4 杨延龄,戚文发;关于最优备件问题的近似算法的研究[J];工程数学学报;1989年01期

5 杜林古;;带风向投递员问题的一个多项式1—近似算法[J];山东纺织工学院学报;1992年01期

6 苏纯洁;带服务器的三台平行机排序问题的复杂性和近似算法[J];应用数学学报;2003年03期

7 刘光聪;朱大铭;姜海涛;;有向基因组反转和转位排序最小权重问题的1.5k近似算法[J];小型微型计算机系统;2010年07期

8 何勇;带核集分划问题的一个线性(1/7)-近似算法[J];高校应用数学学报A辑(中文版);1997年04期

9 季敏,何勇;带核集分划问题的一个改进近似算法[J];系统工程理论与实践;2003年12期

10 何晓琼;陈冲;李荣珩;;工厂地址集中的k-种产品选址问题的近似算法[J];计算机工程与应用;2010年08期

中国重要会议论文全文数据库 前9条

1 刘声田;朱大铭;;基因序列翻转排序的一种近似算法[A];山东省计算机学会2005年信息技术与信息化研讨会论文集（一）[C];2005年

2 梅生伟;洪奕光;秦化淑;翁绍鹏;;非线性H_∞控制的粘性解及其近似算法[A];1996年中国控制会议论文集[C];1996年

3 田世俊;李建;朱洪;;多需求目标的UFL问题及其近似算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 梁国宏;郭云霞;郑明发;;最大化下模函数的近似算法及其性能保证[A];第十届中国不确定系统年会、第十四届中国青年信息与管理学者大会论文集[C];2012年

5 保利勇;赵东风;丁洪伟;;双服务器异步控制策略轮询系统性能的近似算法分析[A];2009年中国高校通信类院系学术研讨会论文集[C];2009年

6 任建峰;张玉忠;孙国;;一种新的柔性车间排序问题[A];中国企业运筹学学术交流大会论文集[C];2005年

7 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];上海市制冷学会一九九七年学术年会论文集[C];1997年

8 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];全国暖通空调制冷1998年学术年会论文集（2）[C];1998年

9 周露;吴瑶华;黄文虎;闻新;;一种推广卡尔曼滤波的近似算法[A];1995中国控制与决策学术年会论文集[C];1995年

中国重要报纸全文数据库 前1条

1 PALADIN;近似算法[N];电脑报;2003年

中国博士学位论文全文数据库 前5条

1 杨朝霞;超图嵌入圈问题的近似算法[D];山东大学;2010年

2 潘锐;设施选址与K-中间点问题的复杂性与近似算法[D];山东大学;2007年

3 陈仕平;若干组合优化问题的近似算法设计与分析[D];浙江大学;2002年

4 柳楠;基因组片段填充问题的算法研究[D];山东大学;2013年

5 姜海涛;基因组比较算法研究[D];山东大学;2011年

中国硕士学位论文全文数据库 前10条

1 陈崇琛;多色点集直线划分的复杂性及其近似算法[D];复旦大学;2014年

2 王敏;基于图特征的介度中心近似算法研究[D];曲阜师范大学;2015年

3 张亚平;最小赋权连通k-子图覆盖问题的近似算法[D];新疆大学;2015年

4 张永俊;广义非线性分式规划问题的近似算法[D];河南师范大学;2015年

5 李彦杰;连通控制吸收集的近似算法[D];新疆大学;2013年

6 张峰;漫射光化通量的二流四流混合近似算法求解[D];中国气象科学研究院;2010年

7 刘海;非光滑问题的三次近似算法[D];北京工业大学;2014年

8 张诸俊;异构车辆路径问题近似算法的研究[D];华东师范大学;2014年

9 赵倩;公共邻接距离基因组片段填充问题研究[D];山东大学;2013年

10 王锦;集装箱调度问题的平行机排序算法研究[D];复旦大学;2010年

，

本文编号：791825