带有一个余凸约束的凹极小

Minimizing a concave function subject to a reverse convex constraint

针对在线性约束加一个余凸约束的条件下，求拟凹函数的全局极小问题，提出一个先构造包含整个可行域的单纯形，然后在目标函数值最小的极点附近逐步予以修正，使之局部重合于可行域的凸包，而得到问题的全局最优解。算法采用分枝和割平面相结合的技巧，对于凡能计算函数值的拟凹函数和凸约束函数，算法就易于执行，并具有有限步终止的收敛性质。由于算法仅在目标函数小的局部搜寻可行域的极点，故当变量及约束个数较大时，计算量远小于极点排序法。

This paper establishes a finite method for finding an optimal solution to a concave program with an additional reverse convex constraint. The method presented is a new approach to global optimization problems by successively minimizing the function over polytopes. The procedure chooses the most promising vertex, the current containing polytope to refine approximation by branch method combines with Tuy cutting plane method.