Minimize $x^2+y^2$, subject to... (optimal points, KKT conditions, dual theories)

Question

I am new to this. I am self learning to get ahead of my next years course and came across this question. I thought it would be a good question to look at due to it touching an many different aspects of optimization.

Minimize $x^2+y^2$

subject to $(x−1)^2 +(y−1)^2\leq 1$,

subject to $(x−1)^2 +(y+1)^2\leq 1$, where $(x, y)\in\Bbb R^2$.

(i) What are the set of feasible points for this problem? Using this, find the optimal point.

(ii) Write down the KKT conditions; are these conditions satisfied at the optimal point? Describe why.

(iii) Write the Lagrange dual problem, and find the optimal solution to the dual problem. Is this optimum solution attained? Does the strong duality theorem for convex programming apply to this scenario?

I have researched the basics of this course, and am trying to challenge myself with this question. Any help would be greatly appreciated.

Answer 1

I'm too lazy to use KKT, so I'm providing a non-KKT solution. Maybe, someone else will help with the KKT requirement.

With only the first constraint, from $(x-1)^2+(y-1)^2\leq 1$, we have by AM-GM that $x^2+y^2+1\leq 2x+2y\leq 2\sqrt{2}\sqrt{x^2+y^2}$. Thus, if $r:=\sqrt{x^2+y^2}$, then $r^2-2\sqrt{2}r+1\leq 0$, which means $\sqrt{2}-1 \leq r\leq \sqrt{2}+1$. Therefore, $3-2\sqrt{2} \leq x^2+y^2\leq 3+2\sqrt{2}$. The LHS equality holds iff $x=y=1-\frac{1}{\sqrt{2}}$. The RHS equality holds iff $x=y=1+\frac{1}{\sqrt{2}}$.

With only the second constraint, from $(x-1)^2+(y+1)^2\leq 1$, we have by AM-GM that $x^2+y^2+1\leq 2x-2y\leq 2\sqrt{2}\sqrt{x^2+y^2}$. Thus, if $r:=\sqrt{x^2+y^2}$, then $r^2-2\sqrt{2}r+1\leq 0$, which means $\sqrt{2}-1 \leq r\leq \sqrt{2}+1$. Therefore, $3-2\sqrt{2} \leq x^2+y^2\leq 3+2\sqrt{2}$. The LHS equality holds iff $x=-y=1-\frac{1}{\sqrt{2}}$. The RHS equality holds iff $x=-y=1+\frac{1}{\sqrt{2}}$.

With both constraints, $(x-1)^2+(y-1)^2\leq 1$ and $(x-1)^2+(y+1)^2\leq 1$ have only one feasible point $(x,y)=(1,0)$. Thus, $x^2+y^2=1$ under these two constraints.

There are also geometric solutions, if we talk only about one of the constraints. The extreme values of $\sqrt{x^2+y^2}$ are the radii of the circles centered at the origin $(x,y)=(0,0)$ that touch the constraint circle $(x-1)^2+(y-1)^2=1$ or the constraint circle $(x-1)^2+(y+1)^2=1$. (By symmetry, these values are the same for both constraint circles, so it suffices to work on only one constraint circle.) Thus, the point of tangency between a constraint circle and an optimal circle centered at $(0,0)$ must lie on the line connecting the centers of the two circles. The rest is quite easy.

Answer 2

$d^2=x^2+y^2$ is the square of distance from $(0,0)$ to $(x,y)$. $$\\$$ 1. When $(x,y)$ is within $\space (x−1)^2+(y−1)^2≤1$, then $d^2$ is minimum when $(x,y)=(1-\frac{\sqrt2}{2},1-\frac{\sqrt2}{2})$. (Imagine which point on the circle is closest from the origin.)

$\therefore d^2 \geq \left(1-\frac{\sqrt2}{2}\right)^2=\frac{3}{2}-\sqrt2$ $$\\$$ 2. When $(x,y)$ is within $\space (x−1)^2+(y+1)^2≤1$, then the minimum $d^2$ is minimum when $(x,y)=(1-\frac{\sqrt2}{2},-1+\frac{\sqrt2}{2})$. And the minimum $d^2$ is same to the above case.