1. General Problem Definition
The Problem
We want to minimize a cost function \( G(u) \) subject to \( u \in U \).
Here, \( u = (u_0, u_1, \dots, u_{N-1}) \) is a vector of \( N \) components.
2. Sequential View
We can view the selection of the vector \( u \) as a sequential process, choosing one component \( u_k \) at a time.
- • State: A partial solution \( (u_0, \dots, u_{k-1}) \), called a \( k \)-solution.
- • Control: The choice of the next component \( u_k \).
- • Constraint: \( u_k \) must be chosen such that it can lead to a feasible full solution.
3. DP Formulation
We can define the optimal cost-to-go function \( J^*_k(u_0, \dots, u_{k-1}) \) as the minimum cost achievable starting from the partial solution.
DP Algorithm
Backward Induction:
\[ J^*_k(u_0, \dots, u_{k-1}) = \min_{u_k \in U_k(\dots)} J^*_{k+1}(u_0, \dots, u_k) \]Terminal Condition: \( J^*_N(u) = G(u) \)
Forward Construction
Once we have the functions \( J^* \), we can construct the optimal solution component by component:
\[ u^*_k \in \arg \min_{u_k} J^*_{k+1}(u^*_0, \dots, u^*_{k-1}, u_k) \]4. Approximation & Rollout
The Challenge
The state space (all partial solutions) grows exponentially. Exact DP is usually impossible.
The Solution: Rollout
Instead of computing \( J^*_{k+1} \) exactly, we approximate it using a Base Heuristic.
\(\tilde{J}_{k+1}\) = Cost of the solution found by the heuristic starting from \((u_0, \dots, u_k)\).
5. Feasibility as DP
Constraint satisfaction problems (finding any feasible \( u \)) can also be formulated as DP.
Transformation
Minimize the sum of constraint violations:
\[ \min \sum_{k=1}^N \max \{0, h_k(x_k, u_k)\} \]If the minimum cost is 0, a feasible solution exists.