线性规划的梯度投影算法

A Gradient Projection Method for Linear Programming

  • 摘要: Karmarkar算法是解线性规划的多项式算法,但其具有数值不稳定的缺点,同时,由于它属于内点法,在算法终止时所得的点始终是一个近似最优解。文中给出的梯度投影法,可以穿过区域内部,或穿过区域的边界的相对内部,证明了该方法将在有限步终止。

     

    Abstract: The karmarkar algorithm is one kind of ploynomial method of solving the linear programming,but it has the deteat that the fruit is not stable.Meanwhile,for the method is belonging to the inner point algorithm,the point get at the termination step is always approximately optimal.The gradient project method given in this paper can go throngh the inner part or the relative inner part of the boundary of area.It is also proved that the method will terminate at limit step in this paper.

     

/

返回文章
返回