弱有效集上凹函数极大问题的分枝定界算法

A branch and bound algorithm for solving maximizing a concave function over weakly-efficient

弱有效(有效)集上的优化是处理多目标线性规划的一种重要途径。考虑了弱有效集上凹函数的极大问题。这个优化问题主要有两方面的困难:一方面,弱有效集一般说来不再是凸集;另一方面,该问题不属于存在一个全局最优解在多面体集的一个极点处取得的一类问题。因此,提出的方法的主要思想是:问题首先被转化为Rk+1空间中一个特殊全局优化问题;其次,对这个问题建立了一个分枝定界型算法。算法的分枝过程采用锥形剖分,定界过程通过求解普通的线性规划实现;最后,对算法的收敛性进行了分析。

Optimization over the weakly-efficient (or efficient) set is an important approach for handling the multiple objective linear programming (MOLP). The authors consider the problem of maximizing a concave function over the weakly-efficient set. This optimization problem contains two main difficulties. On the one hand, the set of weakly efficient solutions in general not convex, on the otber hand, this problem does not belong to the class of problems having the useful property that there exists a global optimal solution at a vertex of the polyhedral set. So, the main idea of the method to be presented can be described as follows. First, the problem is formulated as a special global optimization problem in the space of Rk+1. Second, an algorithm of branch and bound type is established for solving the nonconvex optimization problem. The branching procedure of the algorithm is the conical partition, and the bounding procedure is performed by solving ordinary linear programs. In the end, the convergence of the algorithm is analysed.