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

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .