solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看5239次
A Fast Polynomial-time Primal-Dual Projection Algorithm for Linear Programming. (arXiv:1810.04517v1 [math.OC])
来源于:arXiv
Traditionally, there are several polynomial algorithms for linear programming
including the ellipsoid method, the interior point method and other variants.
Recently, Chubanov [Chubanov, 2015] proposed a projection and rescaling
algorithm, which has become a potentially \emph{practical} class of polynomial
algorithms for linear feasibility problems and also for the general linear
programming. However, the Chubanov-type algorithms usually perform much better
on the infeasible instances than on the feasible instances in practice. To
explain this phenomenon, we derive a new theoretical complexity bound for the
infeasible instances based on the condition number, which shows that algorithms
can indeed run much faster on infeasible instances in certain situations. In
order to speed up the feasible instances, we propose a \emph{Polynomial-time
Primal-Dual Projection} algorithm (called PPDP) by explicitly developing the
dual algorithm. The numerical results validate that our PPDP algorithm achi 查看全文>>