1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What does $y_1+y_2 \leq 5,4$ mean? $\endgroup$ – Théophile Jan 8 '16 at 16:43
  • $\begingroup$ I mean the number $5.4$ , not both the numbers 4 and 5. @Théophile $\endgroup$ – Evinda Jan 8 '16 at 16:45
  • $\begingroup$ 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. $\endgroup$ – barrycarter Jan 8 '16 at 16:59
  • $\begingroup$ @barrycarter How do we use like that dynamic programming? $\endgroup$ – Evinda Jan 8 '16 at 17:32
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Did it without calculus, nice! $\endgroup$ – barrycarter Jan 8 '16 at 17:52
  • $\begingroup$ Not really, I found the top of the parabola by taking a derivative. ;) $\endgroup$ – CommonerG Jan 8 '16 at 17:53
  • $\begingroup$ @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? $\endgroup$ – Evinda Jan 9 '16 at 21:13
  • $\begingroup$ @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? $\endgroup$ – Evinda Jan 10 '16 at 0:52
  • $\begingroup$ I've clarified the solution. $\endgroup$ – CommonerG Jan 11 '16 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.