2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that the constraints require $(x,y)$ to be within $1$ unit of distance from $(1,1)$ and also within $1$ unit of distance from $(1,-1)$. If you visualize that, there is only one single point that satisfied both constraints. $\endgroup$ – littleO Nov 24 '15 at 19:38
  • $\begingroup$ Just to clarify this question: In the given problem, both constraints must be satisfied simultaneously. Visually, we can see that there is only a single point $(1,0)$ that satisfies both constraints. The main point of this problem is to see that if Slater's condition is not satisfied, then strong duality might not hold and the KKT conditions might not work as expected. This is problem 5.26 in Boyd and Vandenberghe. $\endgroup$ – littleO Nov 24 '15 at 21:38
  • $\begingroup$ Okay, I'll take a look at slater's Condition! Thank you @littleO $\endgroup$ – user293150 Nov 24 '15 at 21:41
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think the main point of this problem is to show that if Slater's condition is not satisfied, then strong duality might fail and the KKT conditions might not work as expected. $\endgroup$ – littleO Nov 24 '15 at 20:04
  • $\begingroup$ I'm not going to be bothered about that. Let someone else work on it. $\endgroup$ – Batominovski Nov 24 '15 at 20:04
  • $\begingroup$ It's not very clear either whether only one of the constraints is used (i.e., this problem is actually two separate problems), or both are used simultaneously. If only one is used, Slater's condition is satisfied. $\endgroup$ – Batominovski Nov 24 '15 at 20:07
  • $\begingroup$ You're right, the problem is written a bit unclearly here (with "subject to" repeated twice), but this is problem 5.26 in Boyd and Vandenberghe, and the original problem makes it clear that both constraints are used simultaneously. $\endgroup$ – littleO Nov 24 '15 at 20:16
  • $\begingroup$ thanks a lot everyone for your help. These answers and comments help a lot. $\endgroup$ – user293150 Nov 24 '15 at 21:39
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I was definitely thinking of a wrong approach. This really opens my perspective. thank you! $\endgroup$ – user293150 Nov 24 '15 at 21:38

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.