摘要
针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.
In this paper,a deterministic method is presented for globally solving the sum of convex ratios problem over nonconvex feasible region.The proposed approach is based on the branch and bound scheme.First,the considered problem is reformulated into a d.c.programming problem by introducing new variables.Next,by using subgradient and convex envelope,the fundamental problems for estimating lower bounds in the branch and bound algorithm change into a sequence of relaxation linear programming problems which do not change in scale and can be solved efficiently.Finally,the analysis theory and numerical experiment are reported on the feasibility and efficiency of the proposed algorithm.
出处
《应用数学》
CSCD
北大核心
2010年第3期582-588,共7页
Mathematica Applicata
基金
Supported by the Program for Science and Technology Innovation Talents in Universities of Henan Province(2008 HASTIT023)
关键词
非凸规划
比式和
d.c.规划
分支定界
Nonconvex programming
Sum of ratios
d.c.programming
Branch and bound
