Bellman Equation for nonlinear model

Question

Consider the following model: \begin{align*} max \quad Z &= 19x_1 - 3x_1^2 + 5x_2^2 - x_2^4 + 4x_3 \\ & s.t. \quad x_1 + 3x_2 + 3x_3 \leq 7 \\ & \quad \quad \quad x_1,x_2,x_3 \geq 0 \end{align*}

Also note that all $x_i$ are integers. How does one formulate a Bellman equation for each stage? Can someone maybe give me a hint so I learn from it.

Answer 1

Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$. Let $a_i$ be the constraint coefficient of $x_i$, and let $z_i(x_i)$ be the contribution to the objective value for variable $x_i$. For example, $z_2(x_2) = 5x_2^2-x_2^4$. The boundary condition is $f(0,b)=0$. To derive the Bellman equation as a recurrence for $f(n,b)$ in terms of $f(n-1,.)$, condition on the finite number of choices for the value of $x_n$: $$f(n,b) = \max_{x_n \in \{0,\dots,\lfloor b/a_n \rfloor\}} (z_n(x_n) + f(n-1,b-a_n x_n))$$ The resulting values of $f$ are as follows: \begin{matrix} n\backslash b &0 &1 &2 &3 &4 &5 &6 &7 \\ \hline 0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 1 &0 &16 &26 &30 &30 &30 &30 &30 \\ 2 &0 &16 &26 &30 &30 &30 &34 &34 \\ 3 &0 &16 &26 &30 &30 &30 &34 &\color{red}{34} \\ \end{matrix}

Answer 2

Assuming there are n stages, S symbolized by say $s$ define $x$ as $x_{1,s},x_{2,s}, x_{3,s}$: decision vector $X_s$ and $Z(X_s)$ as optimal value for every stage $s$ subject to same constraint
Using Bellman equation its
Z = max[$Z(X_{s_O}) + \sum_{i=1}^n Z(X_{s+i}:b^{T} X_{s+i} \le 7)]$ $\forall s \in\ $S
s.t.
$b^T X_{s_0} \le 7$

I would however solve it like: max $Z(X_{s}) \ \forall s \in\ $ S
s.t.
$b^T X_{s} \le 7$
$L_{s+1} \le max(Z(X_{s+1}:b^{T} X_{s+1} \le 7)$

Since now $X$ is integer and vector of $x_i$ where $i$ is stage [1,2,3] so we have finite set
For stage=3, $x_3$ can have values of [0,1,2]
$\begin{array}{c|c|c|} & \text{$x_3$} & \text{$Z=4x_3$} & \text{Max} \\ \hline \text{State 1} & 0 & 0 & 0 \\ \hline \text{State 2} & 1 & 4 & 4 \\\hline \text{State 3} & 2 & 8 & 8 \\ \hline \end{array}$
$Max(stage=3)=8$ at $x_3=2$

For stage 2, $x_2$ can have values of [0,1,2] with rhs of constraint=7
$\begin{array}{c|c|c|} & \text{$x_2$} & \text{$x_3$} & \text{rhs=7} & \text{$Z=5x_2^2 - x_2^4 +max(Stage 3 \ Z \ for \ x_3$} & \text{Max}\\ \hline \text{Row 1} & 0 & 0 & 7 & 0 & \\ \hline \text{Row 2} & 0 & 1 & 7-3(1)=4 & 4 & \\ \hline \text{Row 3} & 0 & 2 & 1 & 8 & 8 \\ \hline \text{Row 4} & 1 & 0 & 4 & 4 & \\ \hline \text{Row 5} & 1 & 1 & 1 & 8 & 8 \\ \hline \text{Row 5} & 2 & 0 & 1 & 4 & 4 \\ \hline \end{array}$
$Max(stage=2)=8$ at either $(0,2)$ or $(1,1)$. Cant consider (1,2) or (2,1) as this will violate constraint.\

For stage 1, $x_1$ can have values of [0,1,2]
$\begin{array}{c|c|c|} & \text{$x_1$} & \text{$x_2$} & \text{rhs=7} & \text{$Z=19x_1 - 3x_1^2 + max (Stage2 \ Z \ for \ x_2)$} & \text{Max}\\ \hline \text{Row 1} & 0 & 0 & 7 & 8 \\ \hline \text{Row 2} & 0 & 1 & 7-3(1)=4 & 8 \\ \hline \text{Row 3} & 0 & 2 & 1 & 4 & 8 \\ \hline \text{Row 4} & 1 & 0 & 6 & 24 \\ \hline \text{Row 5} & 1 & 1 & 3 & 24 \\ \hline \text{Row 5} & 1 & 2 & 0 & 20 & 24 \\ \hline \text{Row 5} & 2 & 0 & 5 & 34 \\ \hline \text{Row 5} & 2 & 1 & 2 & 34 & 34 \\ \hline \text{Row 6} & 3 & 1 & 1 & 34 & 34 \\ \hline \end{array}$
$x_1 \ge 4$ onwards objective val will start declining

So at Stage 1, Z = 34 for $X = [3,1,0], [2,1,2]$