Is this optimization problem solvable? I have the following optimization problem:
$$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~ \|\mathbf{y+Ax}\|_\infty \leq \beta\|\mathbf{y}\|_\infty ~~,~~ \|\mathbf{x}\|^2 \leq \alpha^2$$
where $\mathbf{a} \in \mathbb{C^{M\times 1}}$, $\mathbf{B} \in \mathbb{C^{M\times N}}, \mathbf{A} \in \mathbb{C^{K\times N}}$ and $\mathbf{y \in \mathbb{C^{K\times 1}}}$. $\alpha, \beta$ are constants.
I was wondering under what class of optimization problems does this problem falls and whether the infinity norm constraint is a convex set. Without the infinity norm constraint, the problem is a least squares with a quadratic constraint problem. Any help is appreciated.
 A: You can rewrite the infinity norm constraints as a set of linear inequalities.
$$ \text{max}_i (| (y + Ax)_i |) \leq \beta \ || y ||_{\infty} $$ Therefore, 
$$ (y + Ax)_i \leq \beta \ || y ||_{\infty} \quad i = 1,\dots,\mathbb{K}.$$ and 
$$ -(y + Ax)_i \leq \beta \ || y ||_{\infty} \quad i = 1,\dots,\mathbb{K}.$$ 
A: The $\|.\|_{\infty}$, like any other norm, is a convex function (because of the triangle inequality).
The constraint using the infinity norm describes a set of $n$ second-order cones:
$$
\|(y + Ax)_i\|_2 \leq \beta \|y\|_{\infty},\ \text{for } i = 1,..,k
$$
or
$$
\lvert(y + Ax)_i\rvert \leq \beta \|y\|_{\infty},\ \text{for } i = 1,..,k
$$
The quadratic constraint is another second-order cone.
Your problem therefore is a second-order cone program, and can be solved 'easily' using convex programming methods. 
A: Here are some useful facts:


*

*If $f$ is convex and $T$ is affine, then $g(x) = f(T(x))$ is convex.

*Any norm is a convex function, including the $\infty$-norm.

*The function $f(x) = \|x\|^2$ is convex.  (Here $\|x\|$ is the $2$-norm of $x$.)

*If $f$ is convex and $c$ is a real number, then $\{x \mid f(x) \leq c \}$ is a convex set.


These facts show that your optimization problem is convex.  Boyd and Vandenberghe (free online) is a good reference for this material.
