0
$\begingroup$

I am struggling with the following optimization problems.

Problem 1

\begin{align}\max_{\alpha, s_1, s_2}&\quad s_1 + s_2 - \gamma (s_1 (K_1 +c_1 + s_1) + s_2 (K_2+ c_2 + s_2) + 2\alpha K) +C\\\text{s.t.}&\quad s_1 \geq 0, s_2 \geq 0, \alpha \geq 0, \alpha \geq A-s_1 - \beta s_2\end{align}

Problem 2

\begin{align}\max_{\alpha, s_1, s_2}&\quad s_1 + s_2 - \gamma (s_1 (K_1 + s_1) + s_2 (K_2 + s_2) + \alpha K)\\\text{s.t.}&\quad s_1 \geq 0, s_2 \geq 0, \alpha \geq 0, B-s_1 - \beta s_2 \leq \alpha \leq A-s_1 - \beta s_2\end{align}

where $K_1 >0, K_2 >0, C>0, 0<\beta<1, 0<B<A, \gamma >0, c_1, c_2 >0 $ are constants.

If for a given $\gamma = \gamma'$, the optimal objective value of Problem 1 is greater than that of Problem 2, is the optimal objective value of Problem 1 greater than that of Problem 2 for all $0< \gamma < \gamma'$?

I can prove this when the constraints $s_1, s_2, \alpha \geq 0$ do not exist. I proved it by determining a closed form solution for each problem and just compared the two (derivative with respect to $\gamma$ yields lower value for Problem 1 for all $\gamma >0$). How can this be solved when the non-negativity constraints are introduced?

$\endgroup$

1 Answer 1

4
$\begingroup$

If I understood everything correctly this should be false. The following is a counter example.

Let $\epsilon >0$ be small. Choose $K_1=K_2=2$, $c_1 = c_2 = 3$, $K=\epsilon$, $B=\epsilon, A=2\epsilon$, $\beta = \epsilon$ and $C = 4\epsilon^2$.

First consider $\gamma=\gamma'=1$:

Then the first objective becomes: $$ -(s_1^2+4s_1+s_2^2+4s_2+2\epsilon\alpha) + 4\epsilon^2 $$ This is optimized by $s_1=s_2=0$ and $\alpha=A=2\epsilon$ giving an objective of $0$.

Then the second objective we find: $$ -(s_1^2+s_1+s_2^2+s_2+\epsilon\alpha) $$ This is optimized by $s_1=s_2=0$ and $\alpha=B=\epsilon$ giving an objective of $-\epsilon^2$.

Thus the optimal solution for the first problem is bigger than the one for the second.

Now consider $\gamma=\frac{1}{4}<\gamma'$:

Now the first objective becomes: $$ -\frac{1}{4}(s_1^2+s_1+s_2^2+s_2+2\epsilon\alpha) + 4\epsilon^2 $$ This is again optimized by $s_1=s_2=0$ and $\alpha=A=2\epsilon$ giving an objective of $3\epsilon^2$.

And for the second objective we find: $$ \frac{1}{2}(s_1+s_2)-\frac{1}{4}(s_1^2+s_2^2+\epsilon\alpha)) $$ Here we consider the (not necessarily optimal) solution $s_1=0, s_2=1$ and $\alpha=0$ giving an objective of $\frac{1}{4}>3\epsilon^2$ for sufficient $\epsilon$.

Thus we have a contradiction to your conjecture.

$\endgroup$
2
  • $\begingroup$ First of all, thank you so much for your comment. But in Problem 2, we have the constraint $\alpha \leq A - s_1 - \beta s_2$. If we use $A = 2 \epsilon$, $(\alpha, s_1, s_2) = (0, 1, 1)$ is infeasible. $\endgroup$
    – OR_student
    Nov 25, 2020 at 14:44
  • $\begingroup$ That's a good point, but we should be able to fix it by adjusting $\beta$ accordingly and using $s_1=0, s_2=1$. I have adjusted my answer! $\endgroup$
    – SimonT
    Nov 25, 2020 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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