Minimize $x y$ subject to $x^2 + y^2 \le 1$ by Mangasarian-Fromovitz constraint qualification

505 Views Asked by At

I'm trying to solve this problem by KKT

$$\begin{align*} \text{min} & \quad x y \\ \text{s.t} & \quad x^2 + y^2 \le 1 \end{align*}$$

One of the regularity conditions is Mangasarian-Fromovitz constraint qualification - MFCQ, which is

The gradients of the equality constraints are linearly independent at $x^{*}$ and there exists a vector $v \in \mathbb{R}^{n}$ such that $\langle \nabla g_{i}\left(x^{*}\right), v \rangle<0$ for all active inequality constraints and $\langle \nabla h_{j}\left(x^{*}\right), v\rangle=0$ for all equality constraints.

Could you please verify if I correctly apply the KKT's theorem? Thank you so much for your help!


My attempt:

Let $f(x,y) = x y$, $g(x,y) = x^2+y^2-1$, and $\mathcal K= \{(x,y) \in \mathbb R^2 \mid g(x,y) \le 0\}$. Because $\mathcal K$ is compact and $f$ is continuous, the problem has a solution.

Moreover, $\nabla f (x,y) = \begin{pmatrix} y \\ x \\ \end{pmatrix}$ and $\nabla g (x,y) = \begin{pmatrix} 2x \\ 2y \\ \end{pmatrix}$. Let $v = \begin{pmatrix} -x \\ -y \\ \end{pmatrix}$. It follows that $$g(x,y)=0 \implies \langle \nabla g (x,y), v \rangle = -2(x^2+y^2)=-2 <0$$

Hence Mangasarian-Fromovitz constraint qualification is satisfied. Consider the system

$$\begin{cases} \mu \ge 0 \\ \mu g(x,y)=0 \\ \nabla f (x,y)+\mu \nabla g (x,y) =0 \end{cases} \iff \begin{cases} \mu \ge 0 \\ \mu (x^2+y^2-1)=0 \\ \begin{pmatrix} y \\ x \\ \end{pmatrix} + \mu \begin{pmatrix} 2x \\ 2y \\ \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \end{pmatrix} \end{cases} \iff \begin{cases} \mu \ge 0 \\ \mu (x^2+y^2-1)=0 \\ 2x \mu = -y \\ 2y \mu = -x \end{cases}$$

Solving this system, we get $$(\mu,x,y) \in \left \{(0,0,0), \left (1,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right ), \left (1,\frac{1}{\sqrt{2}},\frac{-1}{\sqrt{2}} \right ), \left (-1,\frac{-1}{\sqrt{2}},\frac{-1}{\sqrt{2}} \right ), \left (1,\frac{-1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right ) \right \}$$

Consequently, $f (0,0) = 0$, $f \left (\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right ) = \frac{1}{2}$, $f \left (\frac{1}{\sqrt{2}},\frac{-1}{\sqrt{2}} \right ) = \frac{-1}{2}$, $f \left (\frac{-1}{\sqrt{2}},\frac{-1}{\sqrt{2}} \right ) = \frac{1}{2}$, and $f \left (\frac{-1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right ) = \frac{-1}{2}$.

Hence the solution to the problem is $$\left\{\left (\frac{1}{\sqrt{2}},\frac{-1}{\sqrt{2}} \right ),\left (\frac{-1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right ) \right\}$$

1

There are 1 best solutions below

1
On BEST ANSWER

I think you wrote your values of $\mu$ incorrectly(even though those coefficients aren't of much value here), these are what I worked out

$$(\mu,x,y) \in \left \{(0,0,0), \left (\frac{-1}{2},\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right ), \left (\frac{-1}{2},\frac{1}{\sqrt{2}},\frac{-1}{\sqrt{2}} \right ), \left (\frac{1}{2},\frac{-1}{\sqrt{2}},\frac{-1}{\sqrt{2}} \right ), \left (\frac{1}{2},\frac{-1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right ) \right \}$$

and instead of calculating the values at these points you should first observe that $\mu\geq0$ which negates two of the possibilities, furthermore, $(0,0,0)$ is the local minima if the nature of the minima is also of importance to you. Your methodology and application seems right to me.