论文部分内容阅读
非凸规划问题是一类重要的优化问题,在经济、金融和投资、管理科学、系统工程等很多领域都有广泛应用.一般情况,这类问题通常会有多个非全局的局部最优解,求解起来较为困难,目前已有多种方法研究这类问题,如启发式算法、水平集算法、分支定界算法等.本文针对两类非凸规划问题,依据问题本身特点,分别提出相应的求其全局最优解的近似算法,具体内容如下: 第一章,首先给出本文所研究的全局优化问题模型,其次是简单介绍了该模型的问题背景、目前的研究现状和这类研究的理论意义,最后呈现本文所做的主要工作. 第二章,本章针对一类凸多乘积问题提出一个近似算法,根据模型本身特点,通过引入变量将原问题的求解过程转化为所划定网格区域上一系列易于求解的凸规划问题,进而得出原问题的最优解和最优值,并给出了算法的收敛性证明和计算复杂度分析.数值算例的结果比较也表明本章算法有效可行. 第三章,本章针对一类线性分式规划问题进行研究,通过引入变量和建立网格区域,将原问题转化和分解为一系列易于求解的线性规划子问题,进而使用线性加速技术求解等价问题,从而获得原问题的最优解,并从理论上证明提出的近似算法能获得这类问题的一个全局ε-近似解,最后给出了算法的计算复杂度,且由此表明该算法是完全多项式时间近似算法.与其他算法的数值实验结果的比较也表明本章算法对于求解这类问题具有一定的优势.