基于松弛策略解半无限规划模型的修正算法

Relaxation-strategy-based Modification Algorithm for Solving Semi-infinite Programming

对于一类线性半无限规划问题给出一种我们称之为修正算法的一种新算法。算法采用松弛策略使得满足一定条件的新割面(相当于一个约束)在每一步迭代时被找到。修正算法的主要改进是避免了每一步迭代寻找全局极小解,或者在每一步迭代中去检验δ(xk)是否为极小值。最后,基于提出的修正算法,并与传统割平面方法、普通离散方法对同一问题作了初步的数值比较实验。

In this paper, a new algorithm relaxation-strategy-based for a class of linear semi-infinite programming is developed, called the modification algorithm. We adopt the relaxation-approach such that a new cut （corresponding to one constraint） is found under some conditions. The major improvement of the new algorithm is that modification algorithm avoids the task of finding the global minimizer or checking the minimum value in every iteration. In the last, three different algorithms （namely, the proposed algorithm, the traditional cutting plane method, and the discretization method） have been implemented for same problems.