0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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.