The context: I have been working lately with problems like the following: Let $ x_{k}\in\mathbb{R}^n$ be a state evolving accroding to: $ $ x_{k+1} = f(x_k,u_k), k=0,\dots,N-1 $ $ given some $ x_0$ and controls $ u_0,\dots,u_{N-1}\in\{1,\dots,L\}$ (the set of possible controls is a finite set of "modes"). The goal is to choose the controls to minimize $ $ J = \sum_{k=0}^{N} g(x_k) $ $ In most of my examples, $ f$ does provide structure to make $ x_k$ lie in a finite set, but may lie an arbitrary place in $ \mathbb{R}^n$ in general. The "naive" solution would be to make a tree traversing all combinations of $ u_0,\dots,u_{N-1}$ , then look for the leaf with the least value of $ J$ . Of course, branch and bound or other techniques may be used, but as far as I know this approach won’t be able to get rid of the exponential complexity $ O(L^N)$ (right?).

In order to provide structure to the state space, I decided to quantize $ \mathbb{R}^n$ in blocks of length, say $ \epsilon$ , and assume that $ x_k$ won’t exit a box $ [-B,B]^n\subset\mathbb{R}^n$ , so that $ x_k$ will always lie in a set of finite size $ \mathcal{X}\subset\mathbb{R}^n$ and $ \hat{f}:\mathcal{X}\times\{1,\dots,L\}\to\mathcal{X}$ is the approximation of $ f$ in this setting. In this context, since $ \hat{f}$ transitions between finite sets, one can build a trellis diagram of $ N$ stages with weights given by costs $ g(x_k)$ , then we may apply a shortest path algorithm (viterbi-like approach) which is polynomial. (right?).

To formalize this approach I plan to:

• Use the original $ f$ to obtain a bound $ B$ which will depend on $ N$ .
• Show that for a correct value of $ B$ , one obtains that the true optimum $ J^*$ and our approximated one $ J_\epsilon$ comply that $ J_\epsilon\to J^*$ as $ \epsilon\to 0$ .

My questions:

• I have read that in other problems, a similar quantization approach have been used to obtain a trade-off between accuracy and computational complexity, e.g. in some knapsack problem solutions or some scheduling problems, although these methods quantize the cost and not the state space. My question is, if this approach (quantization + dynamic programming) is standard, if it has a name and if there is a standard reference for me to read more about it.
• Given the problem statement I gave, do you think the solution outline I provided is suitable, or if there is a different approach you can suggest?