求解非凸区域上凸函数比式和问题的全局优化方法(英文)  

Global Optimization for the Sum of Convex Ratios Problem over Nonconvex Feasible Region

作　　者：裴永刚[1] 顾敏娜[2] 申培萍[1] 

机构地区：[1]河南师范大学数学与信息科学学院,河南新乡453007 [2]新乡学院基础部,河南新乡453002

出　　处：《应用数学》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.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.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.

关 键 词：非凸规划 比式和 d.c.规划 分支定界 

分 类 号：O221.2[理学—运筹学与控制论]