Dynamic programming

Dynamic programming (DP) is a method for solving complex optimization problems by breaking them down into a sequence of simpler subproblems. The method is applied to multi-stage decision-making processes, where the optimal solution to the entire problem can be constructed from the optimal solutions of its subproblems.

The term was introduced by American mathematician Richard Bellman in the 1950s. In this context, the word "programming" refers to "planning" or "creating an optimal plan of action," rather than writing computer code.

Key Properties and Theorems

The applicability of dynamic programming to a problem is determined by its possession of two fundamental properties.

Bellman's Principle of Optimality

The central concept of the method is Bellman's principle of optimality. It states: whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

In other words, any part of an optimal trajectory is itself optimal. This property allows the overall problem to be broken down into a sequence of simpler subproblems and solved recursively.

Overlapping Subproblems

A problem has the property of overlapping subproblems if its recursive solution involves solving the same subproblems multiple times. DP avoids re-computation by storing the solutions to subproblems that have already been encountered (a technique called memoization or tabulation), which significantly improves efficiency compared to a naive recursive search.

The Bellman Equation

The principle of optimality gives rise to the method's fundamental recurrence relation—the Bellman equation. It connects the "value" (optimal payoff or cost) of the current state with the values of subsequent states. In its general form for a deterministic multi-stage process with an additive objective function, it is written as:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

where:

• $k$ — step number (from $m$ to 1);
• $x$ — state of the system at step $k-1$;
• $y$ — control decision made at step $k$;
• ${\phi }_k(x,y)$ — payoff (or cost) at step k;
• $f_k(x,y)$ — function defining the new state of the system;
• $V_k(s)$ — optimal value of the objective function for the subproblem starting at step $k$ in state $s$.

The equation is solved sequentially, typically "backwards," moving from the last step to the first.

Examples of Application

• Shortest path problem in a graph: This problem exhibits optimal substructure, as any subpath of a shortest path is itself a shortest path. The Bellman-Ford and Floyd-Warshall algorithms are classic examples of applying DP to solve this problem.
• Knapsack problem: The problem of optimally filling a knapsack of limited capacity with items of different values and weights. DP can solve this problem by considering items sequentially and, at each step, calculating the maximum value for all possible remaining capacities.
• Resource allocation problem: The allocation of a limited resource (e.g., investments) among several projects to maximize the total return.

Limitations

The main limitation of the method is the curse of dimensionality, a term coined by Bellman to describe the exponential growth in the number of states—and consequently, the computational complexity—as the number of variables describing the system's state increases. This limits the practical application of exact DP for problems of very high dimensionality.

Related Concepts

• Operations research
• Optimal control theory
• Markov decision process (stochastic generalization)
• Hamilton–Jacobi–Bellman equation (continuous-time analog)

See also

• Network model (operations research)
• Operations research models
• Integer programming