A corollary of the separating hyperplane theorem known as Farkas's lemma is used with the KKT conditions to prove a "strong" theorem in this field.
A corollary of the separating hyperplane theorem known as Farkas's lemma is used with the KKT conditions to prove a "strong" theorem in this field. While a popular algorithm and its variants are all thought to be exponential, the leading term is only raised to the 3.5th power in a polynomial time algorithm in this field that uses the interior point method and improved upon the ellipsoid method. Methods in this field rely on the correspondence between the (*) primal and dual forms of a problem; those methods find a solution within a convex space known as the feasible region. A popular algorithm in this field converts inequalities to equalities using slack variables. Two popular algorithms of this type are Karmarkar's algorithm and the simplex method. For 10 points, name this method of optimization that uses constraints to maximize a first order objective function.
A corollary of the separating hyperplane theorem known as Farkas's lemma is used with the KKT conditions to prove a "strong" theorem in this field.
linear programming [prompt on partial answers; prompt on “optimization” or “linear optimization”]