# How can this be proved? (Convex optimization)

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?

• 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$.
– user28372
Aug 15 '20 at 15:59
• What I meqn was optimised value of the objective function, not the optimal $x^*$. I will edit Aug 15 '20 at 23:42
• Cross-posted on Operations Research Stack Exchange: or.stackexchange.com/q/4681
– Flux
Aug 16 '20 at 18:04
• For $K \leq 0$ the claim is true, but not for $K>0$ Aug 18 '20 at 11:13
• Are you referring to my claim in the comment or OP’s claim?
– user28372
Aug 18 '20 at 16:54

## 1 Answer

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).

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