# 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.

• Let me clear up the confusion that seems to be occurring below regarding $\beta$ and convexity. Yes, this problem is convex regardless of the sign of $\beta$, because you have specified that $y$ is constant. However, if $\beta<0$, then this problem is trivially infeasible, since there's no way that $\|y+Ax\|_\infty$ can be negative. – Michael Grant Aug 15 '14 at 7:22

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

• an answer below said $\|y+Ax\|_\infty \leq \beta\|y\|_\infty$ is not convex if $\beta >0$. I can't select an answer for this question, because I don't know which one is correct. – user4259 Aug 15 '14 at 1:46
• If $y$ is constant, then that constraint is convex regardless of the sign of $\beta$. However, if $\beta<0$, then the problem is trivially infeasible, because there's no way $\|y+Ax\|_\infty$ can be negative. So the problem is only meaningful if $\beta\geq 0$. – Michael Grant Aug 15 '14 at 7:20
• @MichaelGrant Thank you. $y$ has to be known, it can not be a variable, otherwise the problem is not solvable. $y$ is a constant vector. Can $y$ be a variable here, i thought not, regardless of the value of $\beta$. – user4259 Aug 15 '14 at 14:25
• If it were a variable, then the model would be convex if $\beta<0$. But it wouldn't be a very useful scenario: the resulting constraint would require $y\equiv 0$ and $Ax\equiv 0$. So no, I'd say $y$ must be a constant and $\beta\geq 0$ in any useful version of this problem. – Michael Grant Aug 15 '14 at 19:28

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.

• an answer below said $\|y+Ax\|_\infty \leq \beta\|y\|_\infty$ is not convex if $\beta >0$ – user4259 Aug 15 '14 at 1:47
• I was assuming $y$ is constant -- the optimization problem indicates that the only variable is $x$. However, if $y$ is also a variable, that changes things. – littleO Aug 15 '14 at 2:31
• $y$ is a known vector. – user4259 Aug 15 '14 at 2:47
• In that case, the sign of $\beta$ doesn't matter. I think the other answer assumes $y$ is a variable. – littleO Aug 15 '14 at 3:08

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.

• It is a convex problem but I don't think either constraint is a second order cone constraint. – littleO Aug 14 '14 at 18:47
• Oh indeed, the second-order cone is using the Euclidean norm. The second constraint is a second order cone constraint, just a really basic example of it (A = I, b = 0, c = 0 in when using the notation of Wikipedia) – Etienne Pellegrini Aug 14 '14 at 18:56
• It seems you haven't fully acknowledged littleO's objection. It is not the case that the infinity norm constraint "describes a second-order cone," as you have stated. That is only the case with an otherwise unadorned Euclidean norm constraint (i.e., with no affine operation $y+Ax$). Expressing an infinity norm constraint requires either $n$ second-order cones of order 2, or $2n$ linear inequalities, or $2n$ nonnegative variables and some equality constraints. – Michael Grant Aug 15 '14 at 13:49
• I understand that the infinity norm does not describe a second-order cone. But I don't understand why it should be an 'unadorned' Euclidean norm constraint, with no affine operation. The definition of a second-order cone is: $\|Ax + b \|_2 \leq c^Tx + d$. I agree that the infinity norm should be replaced by $2n$ linear inequalities, or $n$ second-order cones. I edited my answer – Etienne Pellegrini Aug 15 '14 at 20:27