Data Science PT 10: Optimization/Dynamic Programming

Optimization is the selection of a best element from some set of available alternatives with regard to some criterion.

There are several applications of this optimization here. One example is classroom schedule, based on the constraints availability of rooms, proximity of classroom to department, day/time preferences, size of rooms, class enrollment, and student course interest conflicts. Another application is seeking a solution with the smallest ℓ1 norm. The ℓ1 Norm is the sum of the magnitudes of the vectors in a space. It is the most natural way of measure distance between vectors.

A 3rd application is reducing fuel consumption, whether to push a engine up a hill or coast down, or what to do to minimize gas usage. Another application is the process design in factories. We want to buy less inputs and use less energy, and produce the product quickly and flexible to surprises. We want to tune production process to minimize all "costs" in previous sentence. This is also known as multi-objective optimization. 

Dynamic Programming is solving a complex problem by breaking it down into simpler subproblems. We want to partition a problem into parts linking the past, present, and future. This resembles divide and conquer in which we have a large problem, that we partition into parts. The dynamic nature of problem links the past, present, and future. Again, we want a decision whose "combined costs" is the best. DP is much faster than brute force computation. 

In a problem setting we got the time t, time horizon T, state Xt, Possible actions 𝑎𝑡 ∈ Γ(𝑥𝑡). We also define T(x, a) as the next state upon choosing action a and F(x, a) as the payoff from action a. We want to maximize payoff upon horizon T.  We have basis case T = t - 1 having one time left for an action. We maximize payoff with this equation: 

 a* =arg maxa∈ΓF(xt ,a)

At the end of problem, arrive at state XT=T(x,a *) where we will evaluate the payoff one more time. We want optimal cost to account for current payoff and payoff in next step.

Let a*(XT) be the optimal action at time T given state xt. Ψ(XT) is the optimal payoff starting from time t. 

For each time step, we store the optimal actions and payoffs. We can have lookup table for Ψ called memoization. We start at t = T - 2 and repeat these actions recursively for smaller T values. We can construct the optimal actions with the lookup table. Whereas brute force optimization is computationally intense, Dynamic Programming is fast.

In brute force optimization, we have Γ actions per time step and T time steps. We need to evaluate Θ(Γ^T) actions, where in Dynamic Programming we only have to evaluate Θ(ΓT). There are deterministic/random and finite/infinite horizon. In deterministic/random, the next state and payoff can be random so we need to account for those (there can be more users than expected). In finite/infinite horizon, we have to define a discount rate β which decreases importance as the horizon increases. 

An example is the rod-cutting problem where we have a rod of length n. We also have a table of prices pi charged for length-i cuts. We want to cut the rod into parts, therefore maximizing profit. Let's say that we charge prices p1=1, p2=5, p3=8 and p4=9. The basis case is a rod of length n = 1 and Ψ(1)=p1=1. An example of a recursive case is n=3, Ψ(3)=max{Ψ(1)+Ψ(2),p3}=max{5+1,8}=8. At each stage we want to maximize Ψ(n) + Ψ(n - k). Dynamic programming can be used to find the shortest network path in CDMA, as well as speech recognition. 

For a pathfinder, we can use dynamic programming to compute a path from A to b. For each node x* we can denote the length of = Ψ(x*), which is equivalent to its shortest route. We can either reach a node by going to the upper right to lower right, if we are going from left to right. The dynamic programming problem can be formulated as follows: 

until we reach the end of the graph, and compute final solution from each node path before.