Groucho Marxism

Linear programming, also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear relationships. It is widely used in mathematics and, to a lesser extent, in business, economics, and engineering. More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. The canonical linear programming problem can be expressed as: find y ≥ 0 that maximizes the quantity b^Ty subject to the constraints Cy ≤ a, where y is an n by 1 vector, b is a known n by 1 vector, C is a known m by n matrix, and a is a known m by 1 vector.

Every linear programming problem can be converted into a so-called dual problem, which can be expressed as: find x ≥ 0 that minimizes the quantity x^Ta subject to the constraints xC ≥ b, where x is an m by 1 vector, and a, b, and C are defined as above. The strong duality theorem of linear programming states that if y* is a solution to the original (primal) problem and x* is a solution to the dual problem, then b^Ty* = x*^Ta. This result can be used to prove the well-known minimax theorem from game theory, which states that if C is an m by n matrix then max_p min_q p^TCq = min_q max_p p^TCq, where max_p is taken over m by 1 vectors p ≥ 0 satisfying  ∑_i p(i) = 1 and min_q over n by 1 vectors q ≥ 0 satisfying  ∑_j q(j) = 1.

Dynamic programming, also called dynamic optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model which can be broken down into stages or time steps. The simplest dynamic programming problem can be expressed as: find the sequence (u_0,u₁,u₂,…) which minimizes v(i₀) = ∑_k g(i_k,u_k) subject to the constraints i_k+1 = f(i_k,u_k) for each k, where f and g are known functions. The interpretation is that i_k represents the state of some system at time step k which is can be controlled using the inputs (u_0,u₁,u₂,…). Let v* be such that v*(i) attains the minimum for each i. Then it can be shown that v* satisfies the so-called Bellman equation, named after the American mathematician Richard Bellman: v*(i) = min_u{g(i,u)+ v*[f(i,u)]}.

This formulation can easily to be extended to stochastic systems, where instead of a transition function f we have a transition probability distribution P. In this extended formulation, P(i,u,j) represents the probability that the next state of the system is j given that the current state is i and the control input is u. The Bellman equation then becomes v*(i) = min_u{g(i,u)+ ∑_j P(i,u,j)v*(j)}, which can be written in a more compact notation as v* = Tv*, where Tv(i) = min_u{g(i,u)+ ∑_j P(i,u,j)v(j)}. It is straightforward to show that for all vectors v, if v ≤ Tv then v ≤ v*. It follows that if v is the maximum vector satisfying v ≤ Tv then v = v*. Thus the dynamic programming problem just described can be reformulated as the problem of maximizing v subject to the constraints v ≤ Tv.

This reformulated problem is not a linear program as the operator T is nonlinear, but we can turn it into a linear program by rewriting v ≤ Tv as v ≤ g(u)+P(u)v for each u, where g(u) is the vector whose ith component is g(i,u) and P(u) is the matrix whose (i,j)th component is P(i,u,j). This may be rewritten as [I-P(u)]v ≤ g(u) for all u, where I is the identity matrix. To convert this into the canonical linear programming form described above, we can define n to be number of possible states, m to be the total number of states multiplied by the total number of possible control inputs, a to be the m by 1 vector whose (i+u)th element is g(i,u), b to be an n by 1 vetor of 1s, and C to be the m by n matrix whose (i+u,j)th element is P(i,u,j).

This demonstrates that a dynamic programming problem can be reformulated as a linear programming problem, thereby providing a link between two seemingly unconnected types of mathematical optimization.