1
$\begingroup$

The problem is $$ (P) \hspace{1cm} \begin{array}{ll}\min & e^{-x} \\ \text{s.t.} & \frac{x^2}{y} \leq 0 \end{array} $$ over the domain $\mathcal{D}= \{(x,y)| y>0\}$, which I tried to rewrite as $$ (\tilde{P}) \hspace{1cm} \begin{array}{ll}\min & e^{-x} \\ \text{s.t.} & \frac{x^2}{y} \leq 0 \\ & -y<0 \end{array} $$ So the Lagrangian is $\mathcal{L}(x,y,\lambda,\mu) = e^{-x} + \lambda \frac{x^2}{y} - \mu y$

To get the dual problem I tried to find $(\lambda,\mu)$ such as $$ q(\lambda, \mu) = \inf_{x,y} \mathcal{L}(x,y,\lambda,\mu) \neq -\infty $$ But I cant seem to find any because

  • $\lambda \geq 0 , \mu \geq 0$, by taking $x=0,y \to \infty$, $q(\lambda, \mu) = -\infty$
  • $\lambda \geq 0 , \mu < 0$, by taking $y<0, |y|<|x|,x \to \infty$, $q(\lambda, \mu) = -\infty$
  • $\lambda < 0$, by taking $y=1,x \to \infty$, $q(\lambda, \mu) = -\infty$

My intuition is that on the second case I shouldn't be able to take $y<0$ 'cause is off the domain $\mathcal{D}$ at $(P)$ but since I put that as a restriction it shouln't be a constraint over $y$ when looking at $q$ for $(\tilde{P})$ (the definition of $q$ is the infimum of $\mathcal{L}$ over the points on the domain of the restrictions).

This problem is an exercise on Boyd's Convex Optimization (5.21) where the solution is obtained from the problem $(P)$ and I asume they consider the domain $D$ as a restriction over the infimum (it's not specified).

So are $(P)$ and $(\tilde{P})$ not equivalente problems? or am I missing something?

Thanks in advance for your help.

$\endgroup$
5
  • $\begingroup$ The solution is $x=0$. Why are you trying to take the dual? $\endgroup$
    – copper.hat
    Commented Jun 20, 2019 at 0:43
  • $\begingroup$ 'cause is a pedagogical exercise to see a case when there's not strong duality. And also I was trying to undersand the procedure of the excercise itself which ask for 4 things (a) determine is a convex problem and find the optimal value. (b) compute the dual and find the optimal value of the dual problem. (c) Check that Slater's condition doesn't hold. (d) Study a penalized version of the problem. And I got stuck on part (b). $\endgroup$ Commented Jun 20, 2019 at 0:56
  • $\begingroup$ Strict constraints ($y>0$ here) are a bit unusual. $\endgroup$
    – copper.hat
    Commented Jun 20, 2019 at 1:23
  • 1
    $\begingroup$ Do not add $y>0$. That is the domain of the function $f(x,y)=x^2/y$, so let it remain implicit to that constraint, and minimize over $y>0$ in the Lagrangian. $\endgroup$ Commented Jun 20, 2019 at 2:12
  • $\begingroup$ That book has 2 authors. $\endgroup$ Commented Jun 20, 2019 at 21:38

1 Answer 1

2
$\begingroup$

Hint:At first place you can ignore $y$ it dose not play role in problem P. Secondly: You need only consider cases $\mu , \lambda \geq 0$ and what if $ \mu = 0 $ ?

$D$ is an open set and you do not need incorporate it as a sign inequality constraint. Even more the standard definition of Lagrange Duality does not involve any strict inequality.

$\endgroup$
4
  • $\begingroup$ but on this case, if i were to take $y<0$ and then $x\to \infty$, $q(\lambda, \mu=0) = -\infty$. or not? $\endgroup$ Commented Jun 20, 2019 at 0:11
  • $\begingroup$ $ e^{-x} + \lambda \frac{x^2}{y}$ is always positive term for $\lambda \geq 0$ $\endgroup$
    – Red shoes
    Commented Jun 20, 2019 at 0:31
  • 1
    $\begingroup$ then it would be $q(\lambda) = \inf_D e^{-x} + \lambda \frac{x^2}{y}$ as $\lambda \geq 0$? $\endgroup$ Commented Jun 20, 2019 at 0:58
  • 1
    $\begingroup$ You explicitly calculate that by setting derivative = 0 $\endgroup$
    – Red shoes
    Commented Jun 20, 2019 at 1:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .