CAJ | 학술논문

针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.
침대비철구역상적철함수비식화문제,급출일충구기전국최우해적학정성방법.해방법기우분지정계광가.수선통과인입변량,장원문제등개전화위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.