Two quadratic programs

Question

Solve the problem

\begin{align} \text{min}&\quad f(x_1,x_2)&& \\ \text{s.t}& \quad 0\le x_1,x_2\le 1 && \end{align}

with $f(x_1,x_2)=g(x_1)-x_1^2+x_2^2$, where $g(x_1)$ is the optimal value of

\begin{align} \text{min}&\quad u_1^2+u_2^2&& \\ \text{s.t}& \quad u_1+2u_2\ge x_1 &&\\ & \quad u_1,u_2\ge 0. && \end{align}

Please help me with this problem.

Answer 1

First, we can solve for $g(x_1)$ explicitly.

If $x_1 < 0$, the domain for the second optimization problem includes origin, hence $g(x_1) =0 $.

If $x_1 \geq 0$, the distance from the origin to the line $u_1+2u_2=x_1$ would be $\frac{|1(0)+2(0)-x_1|}{\sqrt{1+2^2}}.$ Hence $g(x_1)=\frac{x_1^2}{5}$.

In summary,

$$g(x_1)= \begin{cases} \frac{x_1^2}{5} & \text{ if } x_1 \geq 0 \\ 0 & \text{ if } x_1 < 0 \end{cases}$$

(Credit: Rodrigo de Azevedo)

In the first optimization problem, we are interested in the case where $x_1 \geq 0$,

Hence $f(x_1,x_2)=\frac{x_1^2}{5}-x_1^2+x_2^2=-\frac{4x_1^2}{5}+x_2^2$

Are you able to complete the problem now?

Answer 2

Hint: Note that $f(x_1,x_2)$ can be minimized with respect to each variable independently, giving $x_2^\star=0,\ x_1^\star=\arg\min_{x_1\in[0,1]}(g(x_1)-x_1^2)$. Now, note that $g(x_1)=x_1^2/5$ for $x_1\ge 0$ (Prove this). So, $x_1^\star=1$.