1
$\begingroup$

I want to find the solution by dynamic programming of the following problem. Minimize $f(x_1,x_2)=e^{-x_1^a}+e^{-x_2^a}$

subject to

$e^{-x_1}+e^{-x_2}=b, x_1\geq x_2>0, a,b \in (0,1]$

I started with the second stage

min$e^{-x_2^a}$ subject to $e^{-x_1}+e^{-x_2}=b, x_1\geq x_2>0, a,b \in (0,1]$

then we have two possible solutions $x^*_2=x_1$ or $x_2^*

In the first stage, you have to find the minimum

$e^{-x_1^a}+e^{-{x^*_2}^a}$ subject to $e^{-x_1}\leq b/2$. Then the solution is $x_1=0$ or $x_1=b/2$.

$\endgroup$
1
  • $\begingroup$ Can you show us what you've tried, or at least write down a few things that you know about optimization via dynamic programming? $\endgroup$
    – Alex Jones
    Sep 24, 2018 at 21:14

1 Answer 1

1
$\begingroup$

First rewrite the problem as $$ \min\limits_{x_2} e^{-x_2^a} + \left( \min\limits_{x_1} e^{-x_1^a} \right) $$

or the equivalent problem for max. Given $x_2$, solve the inner problem. Since we have the constraint that $e^{-x_1} + e^{-x_2} = b$, we can see that, given a valid $x_2$, we must have $x_1 = \log\frac{1}{b-e^{-x_2}}$. Since this is the only valid choice for $x_1$, it must solve the min problem, so the updated problem is

$$ \min\limits_{x_2} e^{-x_2^a}+e^{-\log^a\frac{1}{b-e^{-x_2}}} $$

This is only valid for $x_2$ such that $x_1$ exists. This means we need $b-e^{-x_2} > 0 \Rightarrow x_2 > \log\frac{1}{b}$ so that the expression for $x_2$ is real. Also, since $x_1\geq x_2$, we have $2e^{-x_2} \geq b \Rightarrow x_2 \leq \log\frac{2}{b}$. Thus, the valid range for $x_2$ is $(\log\frac{1}{b},\log\frac{2}{b}]$. Thus, the problem we wish to solve is just $$ \min\limits_{x_2\in(\log\frac{1}{b},\log\frac{2}{b}]} e^{-x_2^a}+e^{-\log^a\frac{1}{b-e^{-x_2}}} $$

And equivalently for max. From here, it's a single variable optimization, so we're at the end of the "dynamic" part of it. However, I don't think there exists an analytic solution in terms of $a$ and $b$.

$\endgroup$
4
  • $\begingroup$ And if I want to find the maximum? $\endgroup$
    – Quema
    Sep 24, 2018 at 23:33
  • $\begingroup$ Sorry, I made a mistake and actually calculated the maximum here. I will edit the answer to correctly show the calculation for both min and max. $\endgroup$
    – Alex Jones
    Sep 25, 2018 at 0:01
  • $\begingroup$ This is the best I can do. Maybe someone else can give a full solution :/ $\endgroup$
    – Alex Jones
    Sep 25, 2018 at 1:05
  • $\begingroup$ Well, I really need to prove that $\min\limits_{x_2\in(\log\frac{1}{b},\log\frac{2}{b}]} e^{-x_2^a}+e^{-\log^a\frac{1}{b-e^{-x_2}}}\geq e^{-(-lnb)^a}$ $\endgroup$
    – Quema
    Sep 25, 2018 at 18:03

You must log in to answer this question.

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