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