Find $\min u^2 + v^2, \mbox{s.t. }, u+2v\ge x, u\ge 0,v\ge 0$

Question

How to find

$$\min u^2 + v^2\\\mbox{s.t. } \\u+2v\ge x\\u\ge 0\\v\ge 0$$

I need to solve this. Normally I'd analyze where the conditions meet and analyze if in the point of meeting I can write $\nabla f$ as a linear combination of negative $\lambda_i$ and the transpose matrix made of the meetings, which is a submatrix of the original matrix. That is:

The problem as matrices is

$$\begin{bmatrix}-1 & -2\\-1 & 0\\0&-1\end{bmatrix}\begin{bmatrix}u\\v\end{bmatrix} \le \begin{bmatrix}x\\0\\0\end{bmatrix}$$

An example of submatrix would be

$$\begin{bmatrix}-1 & -2\\-1 & 0\end{bmatrix}$$

which would correspond to the first and second conditions.

Anyways, I think the optimization people know this method, I added just as a context.

The problem is that I'm told that the result is $(0,0)$ for any $x$, but if $x>0$ the point $(0,0)$ isn't even in the region of possible points. What's wrong?

UPDATE:

Actually my book says that for $x\le 0$ the solution is $(0,0)$ but for $x>0$ the objective function at the minimum point is $\frac{x^2}{5}$, but this is what I found with the method:

The only intersections of $u+2v\ge 0,u\ge0 , v\ge 0$ are at $(x,0)$, $(0,x/2)$.

$(0,x)$ is not an optimal, but $(0,x/2)$ is. In this point the optimal function would be $\frac{x^2}{4}$ which is pretty close. Who's wrong? Me or the book?

Answer 1

Here is your error: the red point is not optimal, the green is.

Answer 2

Because our target function monotonically increases with $u$, we want the minimal possible choice for $u$ if we had already chosen $v$.

Thus we can make the inequality tight and say that $u = x - 2v$. So we get $(x - 2v)^2 + v^2 = 5v^2 - 4vx +x^2$ as our quantity to minimize.

If we view $x$ as a given constant, we have a simple parabola with minimum when:

$$10v - 4x = 0 \Longrightarrow v = \frac{2}{5}x$$

So we substitute $v = \frac{2}{5}x$ to find our minimum value:

$$5(\frac{2}{5}x)^2 - 4\cdot\frac{2}{5}x\cdot x + x^2 = \frac{1}{5}x^2$$