Let $|Ax|$ be the element-wise absolute value of $A x$, i.e., $|Ax|_i = |A(i,:)x|$. The inequalities are element-wise inequalities, i.e., $|A(:,i)x| \geq b(i)$. Also, let $\|x\|$ denote the $2$-norm of $x$.
The constraint $|Ax| \leq b$ is convex. However, $|Ax| \geq b$ is not convex. Is there a way to solve the following optimization problem?
$$\begin{array}{ll} \text{minimize} & \|x\|^2\\ \text{subject to} & |Ax| \geq b\end{array}$$
I have used $\|x\|$ so that the solution can be bounded. How can the above problem be solved?
Suppose we are given $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm b \in \mathbb R^m$. Let $\mathrm a_k \in \mathbb R^n$ denote the $k$-th row of matrix $\rm A$, i.e.,
$$\mathrm A = \begin{bmatrix} — \mathrm a_1^\top —\\ — \mathrm a_2^\top —\\ \vdots\\ — \mathrm a_m^\top — \end{bmatrix}$$
Thus, $|\rm A x| \geq b$ is equivalent to
$$\bigwedge_{i=1}^m \left(|\mathrm a_i^\top \mathrm x| \geq b_i\right) \equiv \bigwedge_{i=1}^m \left( \left( \mathrm a_i^\top \mathrm x \geq b_i \right) \lor \left( \mathrm a_i^\top \mathrm x \leq -b_i \right) \right)$$
which is in CNF. Converting it to DNF, we then obtain a union of convex polytopes. The optimization problem we are given seeks the point in this union that is closest to the origin in the Euclidean sense.