2
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Grant Aug 15 '14 at 7:22
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user4259 Aug 15 '14 at 1:46
  • 1
    $\begingroup$ 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$. $\endgroup$ – Michael Grant Aug 15 '14 at 7:20
  • $\begingroup$ @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$. $\endgroup$ – user4259 Aug 15 '14 at 14:25
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Aug 15 '14 at 19:28
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ an answer below said $\|y+Ax\|_\infty \leq \beta\|y\|_\infty$ is not convex if $\beta >0$ $\endgroup$ – user4259 Aug 15 '14 at 1:47
  • $\begingroup$ 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. $\endgroup$ – littleO Aug 15 '14 at 2:31
  • $\begingroup$ $y$ is a known vector. $\endgroup$ – user4259 Aug 15 '14 at 2:47
  • 1
    $\begingroup$ In that case, the sign of $\beta$ doesn't matter. I think the other answer assumes $y$ is a variable. $\endgroup$ – littleO Aug 15 '14 at 3:08
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It is a convex problem but I don't think either constraint is a second order cone constraint. $\endgroup$ – littleO Aug 14 '14 at 18:47
  • 1
    $\begingroup$ 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) $\endgroup$ – Etienne Pellegrini Aug 14 '14 at 18:56
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Aug 15 '14 at 13:49
  • $\begingroup$ 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 $\endgroup$ – Etienne Pellegrini Aug 15 '14 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.