Karmarkar's algorithm

Karmarkar's algorithm falls within the class of interior-point methods: the current guess for the solution does not follow the boundary of the feasible set as in the simplex method, but moves through the interior of the feasible region, improving the approximation of the optimal solution by a definite fraction with every iteration and converging to an optimal solution with rational data.[2] Consider a linear programming problem in matrix form: Karmarkar's algorithm determines the next feasible direction toward optimality and scales back by a factor 0 < γ ≤ 1.[15] While applicable to small scale problems, it is not a polynomial time algorithm.On August 11, 1983 he gave a seminar at Stanford University explaining the algorithm, with his affiliation still listed as IBM.By the fall of 1983 Karmarkar started to work at AT&T and submitted his paper to the 1984 ACM Symposium on Theory of Computing (STOC, held April 30 - May 2, 1984) stating AT&T Bell Laboratories as his affiliation.[16] After applying the algorithm to optimizing AT&T's telephone network,[17] they realized that his invention could be of practical importance.[19] Mathematicians who specialized in numerical analysis, including Philip Gill and others, claimed that Karmarkar's algorithm is equivalent to a projected Newton barrier method with a logarithmic barrier function, if the parameters are chosen suitably.[20] Legal scholar Andrew Chin opines that Gill's argument was flawed, insofar as the method they describe does not constitute an "algorithm", since it requires choices of parameters that don't follow from the internal logic of the method, but rely on external guidance, essentially from Karmarkar's algorithm.[21] Furthermore, Karmarkar's contributions are considered far from obvious in light of all prior work, including Fiacco-McCormick, Gill and others cited by Saltzman.AT&T designed a vector multi-processor computer system specifically to run Karmarkar's algorithm, calling the resulting combination of hardware and software KORBX,[24] and marketed this system at a price of US$8.9 million.[27][28] Opponents of software patents have further argued that the patents ruined the positive interaction cycles that previously characterized the relationship between researchers in linear programming and industry, and specifically it isolated Karmarkar himself from the network of mathematical researchers in his field.In Diamond v. Diehr,[31] the Supreme Court stated, "A mathematical formula as such is not accorded the protection of our patent laws, and this principle cannot be circumvented by attempting to limit the use of the formula to a particular technological environment."[34] Karmarkar's algorithm was used by the US Army for logistic planning during the Gulf War.
Example solution
Graph of a strictly concave quadratic function with unique maximum.
Optimization computes maxima and minima.
algorithmNarendra Karmarkarlinear programmingpolynomial timeellipsoid methodFFT-based multiplicationBig O notationinterior-point methodsfeasible setsimplex methodaffine scalingaffine transformationsprojectiveSovietassignmentIBM San Jose Research LaboratoryStanford UniversitySymposium on Theory of ComputingAT&T Bell Laboratoriessoftware patentsRonald Rivestprior artnumerical analysisbarrier functionvectormulti-processorPentagonpublic domainUnited States Supreme CourtGottschalk v. BensonDiamond v. DiehrMayo Collaborative Services v. Prometheus Labs., Inc.Gulf WarResende, Mauricio G.C.CombinatoricaStrang, GilbertThe Mathematical IntelligencerRobert J. VanderbeiThe New York TimesAssociated PressParker v. FlookAlice Corp. v. CLS Bank Int’lOptimizationAlgorithmsmethodsheuristicsUnconstrained nonlinearFunctionsGolden-section searchPowell's methodLine searchNelder–Mead methodSuccessive parabolic interpolationGradientsConvergenceTrust regionWolfe conditionsQuasi–NewtonBerndt–Hall–Hall–HausmanBroyden–Fletcher–Goldfarb–ShannoL-BFGSDavidon–Fletcher–PowellSymmetric rank-one (SR1)Other methodsConjugate gradientGauss–NewtonGradientMirrorLevenberg–MarquardtPowell's dog leg methodTruncated NewtonHessiansNewton's methodConstrained nonlinearBarrier methodsPenalty methodsAugmented Lagrangian methodsSequential quadratic programmingSuccessive linear programmingConvex optimizationConvex minimizationCutting-plane methodReduced gradient (Frank–Wolfe)Subgradient methodLinearquadraticEllipsoid algorithm of KhachiyanBasis-exchangeSimplex algorithm of DantzigRevised simplex algorithmCriss-cross algorithmPrincipal pivoting algorithm of LemkeActive-set methodCombinatorialApproximation algorithmDynamic programmingGreedy algorithmInteger programmingBranch and boundGraph algorithmsMinimum spanning treeBorůvkaKruskalShortest pathBellman–FordDijkstraFloyd–WarshallNetwork flowsEdmonds–KarpFord–FulkersonPush–relabel maximum flowMetaheuristicsEvolutionary algorithmHill climbingLocal searchParallel metaheuristicsSimulated annealingSpiral optimization algorithmTabu searchSoftware