Is this optimization problem solvable?

Question

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.

Answer 1

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}.$$

Answer 2

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.

Answer 3

Here are some useful facts:

1. If $f$ is convex and $T$ is affine, then $g(x) = f(T(x))$ is convex.
2. Any norm is a convex function, including the $\infty$-norm.
3. The function $f(x) = \|x\|^2$ is convex. (Here $\|x\|$ is the $2$-norm of $x$.)
4. 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.