CNJK算法流程及鞍点共轭梯度法的多项式收敛性

The CNJK Algorithm Program and Polynomial Convergence of Saddlepoint Conjugate Gradient Method

摘要: 本文用鞍点逼近算法及鞍点共轭梯度算法组成了解决LP 问题的新算法,命名为CNJK 算法。本文证明了只要用鞍点逼近算法找到一个可行解,那么鞍点共轭梯度法就具有多项式收敛性。计算复杂性不超过O（m²n²）。

Abstract: In this paper,the program of CNJK algorithm is proposed.The CNJK consists of the sa- ddlepoint algorithm and saddiepoint conjugate gradient method. It is proyed thai when saddlepoint algorithm can find a feasible solution to the LP problem,the saddlepoint conjugate gradient method bas polynomial convergence.The computational complexity does not exceed O（m²n²）.