linear_programming (681B)
1 # Linear programming 2 3 minimize c^t x st A^t x = b and x >= 0 pointwise 4 - [dual] problem: [variable]s y dans R^d, cost b, we want to minimize b^t y 5 - and A y \geq c, defines a [polytope] 6 - so we want to find the point inside the polytope which minimizes the cost 7 8 [algorithm]s (cf [aaron_sidford_talk]): 9 - [simplex_algorithm], fast in practice but slow in memory 10 - [ellipsoid], moderate in both 11 - [interior_point] methods, it's the best in practice 12 - can be approximated ("first order methods") 13 - recent improvements 14 15 Up: [optimization] 16 17 See also: [integer_linear_programming], [linear_equation], [linear_relaxation], [farkas_lemma], [linear_algebra_program], [linear_system]