# Bellman Equation for nonlinear model

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.

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}$$

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]$$

• Could you maybe give me a bellmann equation with the variables and obj function of my problem, I do no really understand this formulation perfectly. Dec 16, 2022 at 9:31
• Just corrected myself Dec 16, 2022 at 23:07