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