# Lagrangian relaxation of optimization problem

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*}

$$\Leftrightarrow$$

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

• 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. – borisd Dec 9 '19 at 8:59
• Thank you I found the solution. – 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$$