I have the following minimization problem:
$$||x||_{\infty} \rightarrow min$$ s.t. $$ ||x - x_0||^2_2 \le r^2$$
where (to avoid trivial solutions) $||x_0||_2 > r $
Preliminary remarks:
-everything is convex i.e. we can use Lagrange dual
-if $x^{*}$ is a solution then $||x^{*} -x_0||_2 = r $
Unfortunately I have a great problem with estabilishing $$inf_{x \in \mathbb{R}^n} ||x||_{\infty} + \mu \cdot ||x- x_0||^2_2$$ (the $-\mu r^2$ part does not affect calculations of infimum) which is mandatory if I want to solve the dual problem.
If $||x||_{\infty} = \alpha<= ||x_0||_{\infty}$ then
$$inf_{x : ||x||_{\infty} = \alpha} ||x||_{\infty} + \mu \cdot ||x- x_0||^2_2 =
\alpha + \mu \cdot || x_0 \wedge \alpha - x_0 ||_{2}^2$$
where $x_0 \wedge \alpha ^{(i)} := min(|x_0^{(i)}|,\alpha) \cdot sgn(x_0^{(i)})$
but further minimization with respect to alpha seems to be intractable.
Is there some way to obtain closed form expression of $L(\mu)$ ?
I've also tried solving the primal problem by stating that $x^{*}$ must be of the form (hope that's true):
$x^{*,(i)} = x_0^{(i)}$ for $i \in I$ and $x^{*,(j)} = t \cdot x_0^{(j)}$ for $j \in J$
where $t < 1 $ and $J \cap I = \emptyset$ and $I \cup J = [1,2...,n]$
but I have problems characterizing sets $J,I$ in dimension biger than 2.
Any help greatly appreciated.
Write the problem as $$\min_{x,y} \{||x||_{\infty} : ||y - x_0||^2_2 \le r^2, x=y \}$$
Then you only need to estabilish $$\min_{x,y \in \mathbb{R}^n} ||x||_{\infty} + \mu ||y- x_0||^2_2 +\lambda^T(x-y)$$ This can be trivially related to the convex conjugates of the respective norms.