The optimization problem is \begin{equation} \begin{split} &\text{minimize} \quad Ax_1c \\ &\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 nonconvex, 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 IsraelDec 15, 2016 at 4:43

$\begingroup$ You're right. Fixed it. $\endgroup$– SchaferDec 15, 2016 at 21:25
1 Answer
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 = \lambdaA\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.

1$\begingroup$ I think this is the reference you mention www2.isye.gatech.edu/~nemirovs/Daureen.pdf Specifically Section 1.3 $\endgroup$ Dec 17, 2016 at 14:14

$\begingroup$ I haven't seen that previously, but it's a great reference. $\endgroup$– DirkDec 17, 2016 at 14:37