# Dynamic programming at a non linear programming problem

Could you explain to me how we can use dynamic programming in order to solve a non linear programming problem?

What do we do for example if we are given the following problem?

$$\max (y_1^3-11 y_1^2+40 y_1+y_2^3-8y_2^2+21 y_2) \\ y_1+y_2 \leq 5.4 \\ y_1, y_2 \geq 0$$

• What does $y_1+y_2 \leq 5,4$ mean? – Théophile Jan 8 '16 at 16:43
• I mean the number $5.4$ , not both the numbers 4 and 5. @Théophile – Evinda Jan 8 '16 at 16:45
• Not sure if this helps, but you can look at the derivative of the sum when y1+y2 = some constant. Between that and checking boundary conditions, you should be able to solve it. – barrycarter Jan 8 '16 at 16:59
• @barrycarter How do we use like that dynamic programming? – Evinda Jan 8 '16 at 17:32

## 1 Answer

I now know that this is an exercise and you need to use dynamic programming, however, I'll leave this solution up for reference.

Fix $y_1 + y_2 = z$ for $z\leq 5.4$.

The objective can be rewritten: $$y_1^3-11 y_1^2+40 y_1+(z-y_1)^3-8(z-y_1)^2+21(z-y_1)$$

This function is concave in $y_1$ (the cubic terms fall out leaving an upside-down parabola), so the first order condition is sufficient for (constrained) global maximum.

The first order condition is: $y_1 = \frac{z+1}{2}$ and thus $y_2 = \frac{z-1}{2}$

Plugging these into to the objective and simplifying gives:

$$\frac{1}{4}(z^3 - 19z^2 +119z +19)$$

This is increasing to $5\frac{2}{3}\geq5.4$. Thus, the objective is maximized for $z=5.4$. Using the first order condition above again gives the solution:

This is: $$y_1=\frac{16}{5}$$ $$y_2=\frac{11}{5}$$

• Did it without calculus, nice! – barrycarter Jan 8 '16 at 17:52
• Not really, I found the top of the parabola by taking a derivative. ;) – CommonerG Jan 8 '16 at 17:53
• @CommonerG In order to deduce that the function is increasing in both variables when they are positive did you fix one of them as a constant and then derived the function?  Also why can we assume that $y_1+y_2=5.4$ at the optimum?  Which first order condition do you mean? – Evinda Jan 9 '16 at 21:13
• @CommonerG We have that $\frac{\partial{f}}{\partial{y_1}}(y)= 3y_1^2-22y_1+40 \\ \frac{\partial{f}}{\partial{y_2}}(y)=3y_2^2-16y_2+21$. The roots are greater than $0$. How did you deduce that the function is increasing as for both variables? – Evinda Jan 10 '16 at 0:52
• I've clarified the solution. – CommonerG Jan 11 '16 at 2:31