The optimization problem is \begin{equation} \begin{split} &\text{minimize} \quad ||Ax|_1-c| \\ &\text{subject to} \quad |x|_2 \leq b, \end{split} \end{equation} where $x\in \mathbb{C}^N$, $A$ is a known $M\times N$ complex matrix, $c$ and $b$ are constant. Since the objective function is non-convex, it cannot be solved using the standard tool, e.g., cvx. Is there any way to convert the objective function to be convex?

  • 1
    $\begingroup$ By $|A x|_1$ I presume you mean the $\ell_1$ norm of $Ax$. But that's a number, so what does the outer $| \cdot |_1$ mean? Should it just be $|\cdot|$? $\endgroup$ – Robert Israel Dec 15 '16 at 4:43
  • $\begingroup$ You're right. Fixed it. $\endgroup$ – Schafer Dec 15 '16 at 21:25

I do not think that this can be converted to a convex problem: There are multiple solutions in general and these do not form a convex set: If $c>0$ and $x^*$ is a solution, then $-x^*$ is also one. However, $0$ is convex combination of these solutions, but not optimal. In principle there is the convex relaxation of the problem, which means to replace the objective function by the largest convex function below the objective, but usually this is even more difficult to compute than solving the original problem.

Note that $c\leq 0$ leads to the trivial solution $x^*=0$, so you can assume that $c>0$

If you could solve $$ \max\{|Ax|_1\mid |x|_2\leq b\} $$ with some solution $\bar x$ and observe that the objective $|A\bar x|$ is smaller than $c$, then any solution $\bar x$ of the above problem would be also a solution of the original problem. If $|A\bar x|_2>c$, then find $0<\lambda<1$ such that $c = |A\lambda\bar x|_1 = \lambda|A\bar x|_1$, to get an optimal solution.

It remains to solve the maximization problem (convex function over a convex domain, so the maximum is assumed at the boundary) and this is essentially the computation of the matrix norm of $A$ as a mapping from a space with $\ell^2$-norm to a space with $\ell^1$-norm, denoted $$ \|A\|_{2\to1} = \max\{|Ax|_1\mid |x|_2\leq 1\}. $$ I vaguely remember that this norm (as well as most other mixed induced norms) is hard to compute but can't find a reference right now.


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.