Use Lagrangian relaxation to solve the following optimization problem in $x, y\in \mathbb{R}$.

$$\begin{array}{ll} \text{minimize} & x^2 + 2 y^2\\ \text{subject to} & x + y \geq 2\\ & x^2 + y^2 \leq 5\end{array}$$

Solution :

Let $f(x,y)=x^2+2y^2$, $g_1(x,y)=2-x-y$, and $g_2(x,y)=x^2+y^2-5$.\~~ \ For $\lambda \in \mathbb{R}_+^2$ we define the Lagrangian Relaxation of the problem above : \begin{equation*} \begin{aligned} min~&f_\lambda(x,y)\\ subj.~to~~&x,y\in \mathbb{R} \end{aligned} \end{equation*} With, \begin{equation*} \begin{aligned} f_\lambda(x,y)=&f(x,y)+\sum_{i=1}^2\lambda_ig_i(x,y)\\ =&x^2+2y^2+\lambda_1(2-x-y)+\lambda_2(x^2+y^2-5) \end{aligned} \end{equation*}

$f_\lambda$ is two times differentiable on $\mathbb{R}^2$, and $\mathbb{R}^2$ is open and convex. Moreover, \begin{equation*} \nabla^2f_\lambda(x,y)=2 \begin{pmatrix} 1+\lambda_2&0\\ 0&2+\lambda_2 \end{pmatrix} \end{equation*}

Each eigenvalues of $\nabla^2f$ are positives therefore it is positive definite. So $f_\lambda$ is a convex function, thus a local min of $f_\lambda$ in $\mathbb{R}^2$ is a global min.\ We want to find a local minimum by differentiating $f_\lambda$. If $\nabla f_\lambda(\bar x,\bar y)=0$ then $(\bar x,\bar y)$ is optimal for the Lagrangian relaxation of the problem.\ \begin{equation*} \nabla f_\lambda(\bar x,\bar y)=0~~\Leftrightarrow ~~ \begin{pmatrix} 2\bar x-\lambda_1+2\lambda_2\bar x\\ 4\bar y-\lambda_1+2\lambda_2\bar y\\ \end{pmatrix} =0 ~~\Leftrightarrow ~~ \begin{pmatrix} \bar x \\ \bar y \end{pmatrix}= \begin{pmatrix} \frac{\lambda_1}{2+2\lambda_2}\\ \frac{\lambda_1}{4+2\lambda_2} \end{pmatrix} \end{equation*}

Hence $(\bar x(\lambda) ,\bar y (\lambda))=( \frac{\lambda_1}{2+2\lambda_2}, \frac{\lambda_1}{4+2\lambda_2}) $ is optimal for the Lagrangian relaxation of the problem.\ Now, $(\bar x(\lambda) ,\bar y (\lambda))$ is optimal for the initial problem if : \begin{equation*} \begin{aligned} &(i)~~g(\bar x(\lambda) ,\bar y (\lambda))\leq 0\\ &(ii)~~\lambda_i g_i(\bar x(\lambda) ,\bar y (\lambda))=0,~~\text{for }i=1,2.\\ &(iii)~~\lambda \geq 0 \end{aligned} \end{equation*}

I choose $\lambda$ such that : \begin{equation*} \begin{aligned} &g_1(\bar x,\bar y)=0\\ &g_1(\bar x,\bar y)=0 \end{aligned} \end{equation*} So, $(i),(ii)$ hold. my choice implies : \begin{equation*} \begin{aligned} 2-\frac{\lambda_1}{2(1+\lambda_2)}-\frac{\lambda_1}{2(2+\lambda_2)} &=0\\ \frac{\lambda_1^2}{4(1+\lambda_2)^2}+\frac{\lambda_1^2}{4(2+\lambda_2)^2}-5 &=0\\ \end{aligned} \end{equation*}


\begin{equation*} \begin{aligned} \lambda_1( \frac{1}{2(1+\lambda_2)}+\frac{1}{2(2+\lambda_2)}) &=2\\ \lambda_1^2(\frac{1}{4(1+\lambda_2)^2}+\frac{1}{4(2+\lambda_2)^2}) &=5\\ \end{aligned} \end{equation*}

$\Leftrightarrow$ \begin{equation*} \begin{aligned} \lambda_1^2(\frac{1}{4(1+\lambda_2)^2}+\frac{1}{4(2+\lambda_2)^2}+\frac{1}{2(1+\lambda_2)(2+\lambda_2)}) &=4\\ \lambda_1^2(\frac{1}{4(1+\lambda_2)^2}+\frac{1}{4(2+\lambda_2)^2}) &=5\\ \end{aligned} \end{equation*}

$\Leftrightarrow$ \begin{equation*} \begin{aligned} \lambda_1^2(\frac{1}{2(1+\lambda_2)(2+\lambda_2)}) &=-1\\ \lambda_1^2(\frac{1}{4(1+\lambda_2)^2}+\frac{1}{4(2+\lambda_2)^2}) &=5\\ \end{aligned} \end{equation*}

$\Leftrightarrow$ \begin{equation*} \begin{aligned} \lambda_1^2&=-2(1+\lambda_2)(2+\lambda_2)\\ \lambda_1^2(\frac{1}{4(1+\lambda_2)^2}+\frac{1}{4(2+\lambda_2)^2}) &=5\\ \end{aligned} \end{equation*}

So I get : \begin{equation*} \begin{aligned} -2(1+\lambda_2)(2+\lambda_2)(\frac{1}{4(1+\lambda_2)^2}+\frac{1}{4(2+\lambda_2)^2}) &=5\\ \Leftrightarrow~~~\frac{(2+\lambda_2)^2+(1+\lambda_2)^2}{2(1+\lambda_2)(2+\lambda_2)}&=-5\\ \Leftrightarrow~~~ 12 \lambda_2^2+36 \lambda_2+25&=0\\ \Leftrightarrow~~~ \lambda_2&=\frac{-36\pm \sqrt{96}}{24}\leq 0 \end{aligned} \end{equation*} Therefore $(iii)$ is not verified. $$ $$ And if I choose $\lambda =0$ then $(i)$ is not verified. $$ $$ I'm stuck here...

  • $\begingroup$ You found the minimum of the Lagrangian function once $\lambda$ is fixed, which is a first step. Now you need to find the maximum of the Lagrangian dual function to find a saddle-point. $\endgroup$ – borisd Dec 9 '19 at 8:59
  • $\begingroup$ Thank you I found the solution. $\endgroup$ – Sylvain Lhermite Dec 9 '19 at 13:20

Show that $$x^2+2y^2\geq \frac{8}{3}$$ the equal sign holds if $$x=\frac{4}{3}y=\frac{2}{3}$$, Since $$f(x,y)=x^2+2y^2$$ we get $$\frac{\partial f(x,y)}{\partial x}=2x$$ and $$\frac{\partial f(x,y)}{\partial y}=4y$$ you should search the extreme points on the curves $x+y=2$ and $$x^2+y^2=5$$

  • $\begingroup$ Ok thank you but your method don't use Lagrangian relaxation... And for my assignement I have to use it. $\endgroup$ – Sylvain Lhermite Dec 8 '19 at 17:25

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.