How to show that the following two optimization problems are equivalent?

Question

The first problem is $$\max. ~~g(\lambda)-x$$ $$s.t. ~~ x\geq 0, \lambda \geq 0, a-\lambda b +x \geq 0$$ where $g(\lambda)$ is an increasing function of $\lambda$ and $a,b$ are some positive constants and the optimization variables are $x,\lambda$.

I want to know how the above problem is equivalent to the following problem $$\min. ~~g(\lambda)+x$$ $$s.t. ~~ x\geq 0, \lambda \geq 0, x \geq a-\lambda b.$$ At this moment, I only understand the change in sign before $x$ in the objective function of second optimization problem. But I do not understand the rest of the changes. Any help in this regard will be much appreciated.

Answer 1

I am not sure if there exists some duality between these two problems. And I think there needs some more conditions for this equivalence.

From the constraints in the first problem, we have \begin{equation} -x \leq 0, \quad -x \leq a-\lambda b. \end{equation} Thus \begin{equation} g(\lambda) - x \leq g(\lambda) + \min(0, a-\lambda b). \end{equation} Then \begin{equation} \begin{aligned} \sup_{\lambda,x} \left\{g(\lambda) -x \right\} &= \max(\sup_{a-\lambda b \ge 0} \left\{g(\lambda) \right\}, \sup_{a-\lambda b \leq 0} \left\{g(\lambda) + a-\lambda b\right\}) \\ &= \max(g(\frac{a}{b}), \sup_{a-\lambda b \leq 0} \left\{g(\lambda) + a-\lambda b\right\}), \end{aligned} \end{equation} The second equality is derived by the fact that $g$ is increasing.

Similarly, for the second problem, we have \begin{equation} \begin{aligned} \inf_{\lambda, x} \left\{g(\lambda)+x\right\} &= \min(\inf_{a-\lambda b \leq 0} \{g(\lambda)\}, \inf_{a-\lambda b \ge 0} \{g(\lambda)+a-\lambda b\}) \\ &= \min(g(\frac{a}{b}), \inf_{a-\lambda b \ge 0, \lambda \ge 0} \{g(\lambda)+a-\lambda b\}), \end{aligned} \end{equation}

This two problems are not equivalent. And we need some more conditions, for example, suppose $g(\lambda) - \lambda b$ is decreasing in terms of $\lambda$. In this sense, we can easily know that \begin{equation} \sup_{\lambda,x} \left\{g(\lambda) -x \right\} = g(\frac{a}{b}), \quad \inf_{\lambda, x} \left\{g(\lambda)+x\right\} = g(\frac{a}{b}). \end{equation}

On the other hand, if $g(\lambda) - \lambda b$ is NOT decreasing in terms of $\lambda$, we can find some counterexamples:

• $a=b=1$ and $g(\lambda) = \lambda^3$. The maximum of the first problem is $+\infty$ and the minimum of the second problem is $1$.
• $a=b=1$ and $g(\lambda) = 2\lambda$. The maximum of the first problem is $+\infty$ and the minimum of the second problem is $1$.