Minimize of $x^2+y^2$ subject to $x+y \ge 1$ 
Consider the problem of minimizing $x^2 +y^2$, subject
to $x + y \ge 1$.
Suppose that you start coordinate descent for this problem at $x = 1$ and $y = 0$.
Discuss why coordinate descent will fail.

The primal problem is equivalent to:
minimize $x^2+y^2$ subject to $-x-y \le -1$.
The lagrangian is: $L(x,y,a) = x^2+y^2-a(x+y-1)$. Then,
$\frac{dL}{dx} = 2x-a=0, x = a/2$
$\frac{dL}{dy} = 2y-a=0, y = a/2$
$\frac{dL}{da} = x+y-1=0$
So, the dual problem is: maximize $a^2/2$ subject to $a=1$. Hence, we get the primal optimal to be $(x,y) = (1/2,1/2)$. Right?
Now if we start at $(1,0)$. Let's solve for $x$.
plug in $y=0$ to get minimze $x^2$ subject to $x \ge 1$. So, $x = 1$.
Then plug in $x=1$ to solve for $y$: minimize $y^2+1$ subject to $y \ge 0$. We will get $y = 0$.
Hence, basically we are stuck at the starting point $(1,0)$.
 A: I suggest you start by drawing a picture. The objective function $x^2+y^2$ is the square of the distance from the point $(x,y)$ to the origin. So, basically, we’re trying to find the point in the feasible region that’s closest to the origin.
The feasible region is above and to the right of the line $x+y=1$.
You’re supposed to start at $(x,y)=(1,0)$.
What does the coordinate descent algorithm do, geometrically?
A: First let's observe from the following figure of the gradient fields for the objective function that the optimum occurs at the boundary, not inside the region bounded by the objective function curve (circle).

Now, by Lagrangian, we have $\nabla f = \lambda \nabla g$, where we have the gradient of the objective function $\nabla f=\begin{bmatrix}2x\\ 2y\end{bmatrix}$ and gradient of the constraint function as $\nabla g=\begin{bmatrix}1\\ 1\end{bmatrix}$ and hence $\begin{bmatrix}2x\\ 2y\end{bmatrix}$ $=\lambda\begin{bmatrix}1\\ 1\end{bmatrix}$
Eliminating $\lambda$ from the above system of equations, we get $x=y$ and along with $x^2+y^2=1$, we get $x^2=y^2=\frac{1}{2}$. Notice from the above gradient field that at $x=y=\frac{1}{\sqrt{2}}$ the maximum occurs, whereas $x=y=-\frac{1}{\sqrt{2}}$ is the point where the minimum occurs, but the constraint $x+y\geq 1$ is not satisfied here (hence an infeasible solution).
Now, let's look at the contour plot for the function and the feasible region for the solution, as can be seen from the following figure that minimum occurs at $(0,1)$ and $(1,0)$, where the value of the objective function is $1$.

