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.

$\endgroup$
1
  • 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, 2014 at 7:22

3 Answers 3

Reset to default
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}.$$

$\endgroup$
4
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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.

$\endgroup$
4
  • $\begingroup$ an answer below said $\|y+Ax\|_\infty \leq \beta\|y\|_\infty$ is not convex if $\beta >0$ $\endgroup$
    – user4259
    Aug 15, 2014 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, 2014 at 2:31
  • $\begingroup$ $y$ is a known vector. $\endgroup$
    – user4259
    Aug 15, 2014 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, 2014 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.

$\endgroup$
4
  • $\begingroup$ It is a convex problem but I don't think either constraint is a second order cone constraint. $\endgroup$
    – littleO
    Aug 14, 2014 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, 2014 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, 2014 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, 2014 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.