Karmarkar's algorithm
（重定向自Projective method）
![Example solution](/Images/godic/202502/04/Karmarkar.svg5635.png")
![The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.](/Images/godic/202502/04/Max_paraboloid.svg5635.png")
Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice.