摘要
给出了解线性规划的广义起作用集法。从极点出发的搜索方向是该点处所有下降棱方向的一种凸组合。一般情况下,迭代路径置于容许集的表面上,而不是象单纯形法那样迭代点沿着棱移动。由于广义方法的迭代通常要跳过一些极点,因此收敛速度比单纯形法有明显的提高。
A generalized active set method is presented for solving linear programming problems. The direction of search starting from an extreme point is a convex combination of all descent directions along the edges at the point. Generally, the iterative path is on the faces of a feasible region instead of on its edges as in simplex method. Since each iteration in the generalized method will usually skip over a number of extreme points,the convergence rate is obviously quicker than that in simplex method.
关键词
线性规划
起作用集法
单纯形法
linear programming, simplex method, active set method, descent feasible direction.
