Convert non-convex function (norm of a norm) to convex

Question

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?

Answer 1

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.