广义分式规划问题的全局优化方法研究

We study the global optimization methods for generalized fractional programming problems, which include the sum of ratios fractional programming, generalized geometric programming etc. The problems considered are the current frontier and hot research in many fields, such as global optimization, computer perspective problem, steady-state optimization of biochemical systems. The global optimal solution need to be obtained in practical problems, which brings essential difficulty for numerical methods, and the existing mature local optimization methods cannot be used to solve these problems. Based on the structural characteristics of these optimization problems, in order to establish effective and stable global optimization algorithms, the new relaxation bounded functions will be constructed by using the corresponding convex (concave) envelope, and special branch and bound methods and the region reduction rules will be determined via interval analysis. For the special sum of ratios fractional programming, constructing and using the equivalent problems in the outcome space, combining the relevant theory of multiobjective optimization and outer approximation methods, the global optimization methods will be presented efficiently in the outcome space. In view of some low-rank optimization problems, by constructing a suitable grid we will transform or separate the problems into easily handled ones by reducing dimension or number of constraints to the problems solved. And the approximation algorithms will be developed and its computation complexity will be given for some low-rank optimization problems. Finally, in order to create social and economic profits, the proposed methods will be applied to some practical problems, including computer perspective, steady-state optimization of biochemical systems etc.

本项目研究广义分式规划问题的全局最优解方法。考虑的问题（包括比式和分式规划、广义几何规划等）是国际最优化、计算机视角、生化系统平衡等领域的研究前沿和热点。由于工程实际需要寻求该问题的全局最优解，这给数值求解带来本质性困难，已有的局部化方法难于求解这些问题。本项目基于所考虑问题的特点，通过凸（凹）包逼近确定新的松弛界函数，利用区间分析等工具建立区域删除加速原则，确定各具特色的分支和定界技巧，建立相应问题高效、稳定的分支定界全局优化算法。对于特殊的比式和优化问题，构造并利用外空间上的等价问题，结合多目标优化的相关理论及外逼近方法，建立高效的外空间全局优化方法。对于某些低秩优化问题，构造合适的网格节点，通过降低求解问题的维数或减少约束个数，将问题转化或分离成容易处理的特殊规划问题，建立相关问题的全局优化近似算法，给出算法的计算复杂度。最后将提出的方法应用于计算机视角、生化系统稳定态等实际问题中。

本项目针对工程设计、经济管理与人工智能等中归结出的广义分式规划及其特殊形式的优化问题，建立了求解相应问题的全局优化算法，获得算法的理论分析和有效的数值计算结果。具体如下：1）利用代数变换和特殊不等式等建立求解广义多项式比式和问题的压缩方法。2）基于分割、删除、减小等基本操作，提出求解线性比式和优化问题的区域分割和定界算法。3）针对由多个仿射函数复合而成的分式规划或其特殊形式的优化问题，利用外空间和线性化分解技术，将原来复杂问题的求解过程转化为求解一系列线性规划问题，建立了求解相应问题的近似算法。4) 对一类广义线性多乘积规划，利用辅助变量所处的外空间矩形，建立适合的非均匀剖分网格，将原问题的求解过程转化为求解有限个网格节点所对应的线性规划子问题，提出了完全多项式时间近似算法，分析了算法的收敛性和计算复杂性。5）对一类特殊的线性多乘积优化问题，基于原问题的等价问题的特点提出了线性化松弛技术，将原问题的求解转化为求解一系列线性规划问题。通过将提出的线性松弛、分支规则和区域减少等技术相结合，建立了求解优化问题的分支定界算法，并证明提出的算法能获得原问题的全局最优解。6）在约束优化的群智能算法方面，对粒子群算法，利用社会和个体经验建立了粒子群移动方程以有效改进粒子的收敛速度，提出位置废弃和新位置产生机制以避免陷入局部最优。对萤火虫算法，基于性别差异设计相应的移动方式以平衡局部与全局搜索能力，引入混沌搜索和反向学习机制以提高算法的搜索速度和精度。对蝙蝠算法，为摆脱算法陷入局部最优，基于当前迭代连续未更新的次数提出位置废弃机制，基于历史最优信息建立新的搜索方程和自适应搜索方程。7）在对称锥规划、DC规划等方面也提出了相应的求解方法。以上研究结果共发表学术论文30篇，其中SCI收录20篇，中文核心10篇。培养研究生18名，其中毕业生12名，举办全国性学术会议3次，已实现了预期研究目标。