Consider the following maximization problems:

  1. $\max_{x} x -\gamma p(x)$ subject to $x \in \Omega_1$

  2. $\max_{x} x-\gamma (p(x) + q(x) )+K$ subject to $x \in \Omega_2$

where $\Omega_1 $ and $ \Omega_2$ are convex sets, $p(x) \geq 0 $ and $q(x) \geq 0$ for all $x\in \Omega_2$. Also, $p''(x)>0$ and $q(x)$ is linear in $x$ and $K>0$ is a constant.

If for given $\gamma = \bar{\gamma}$, the optimized objective value for problem 1 was greater than the optimized objective value of problem 2, does the optimized objective value for the problem 1 always greater than that of problem 2 for all $\gamma > \bar{\gamma}$?

Prove or provide counter example for (1) $\Omega_1= \Omega_2$ and (2) $\Omega_1 \subset \Omega_2$.

Since the higher penalty proportional to $\gamma$ is imposed to the objective function of problem 2, this claim seems right. I tried using contradiction, in which assuming there exists $\gamma'>\bar{\gamma}$ such that optimized value for problem 2 is greater than that of problem 1, but struggling. How can this be proved?

  • $\begingroup$ Please clarify: By optimal value, do you mean the optimal $x^*$ or the optimised value of the objective function? If its the former, you can only claim that the optimal $x^*$ from problem 1 will be WEAKLY greater than the optimal $x^*$ from Problem 2 as you increase $\gamma$. The issue is that the optimal $x^*$ for both the problems may hit the lower boundary of the interval as you increase $\gamma$. $\endgroup$
    – user28372
    Aug 15 '20 at 15:59
  • $\begingroup$ What I meqn was optimised value of the objective function, not the optimal $x^*$. I will edit $\endgroup$
    – OR_student
    Aug 15 '20 at 23:42
  • $\begingroup$ Cross-posted on Operations Research Stack Exchange: or.stackexchange.com/q/4681 $\endgroup$
    – Flux
    Aug 16 '20 at 18:04
  • $\begingroup$ For $K \leq 0$ the claim is true, but not for $K>0$ $\endgroup$
    – Bertrand
    Aug 18 '20 at 11:13
  • $\begingroup$ Are you referring to my claim in the comment or OP’s claim? $\endgroup$
    – user28372
    Aug 18 '20 at 16:54

Take $\Omega_1=\Omega_2=[0,0.5]$.

Let $p(x)=x^4$, so that $p''(x)=12x^2>0$ on $(0,0.5)$.

Let $q(x)=0.5x$, which is linear in $x$, and $K=0.2>0$.

For $\bar\gamma=1$, both objective functions attain their respective maximum at $x=0.5$. As the following figure shows, objective function $(1)$ (blue curve) has a higher maximum than that of objective function $(2)$ (red curve).

enter image description here

But for $\gamma=5>\bar\gamma$, objective function $(1)$ attains a maximum value of approximately $0.276$, while objective function $(2)$ attains a higher maximum value of approximately $0.309$, contradicting the claim that $(1)$'s maximum would always be greater than $(2)$'s maximum for $\gamma>\bar\gamma$.

enter image description here


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.