Minimizing $2$-norm subject to non-convex constraints

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?

• $Ax$ is a vector, so what does $|Ax|$ denote? You're using a different symbol $\| \cdot \|$ to denote a norm. – littleO Apr 19 at 10:36
• @TonyS.F. But which norm? Am I allowed to assume it's the Euclidean norm? – littleO Apr 19 at 10:54
• That's a fair point, it's ambiguous whether it's the $\ell^1$ or the euclidean. – Tony S.F. Apr 19 at 10:55
• $|Ax|$ is taking elementwise absolute values of the vector $Ax$. I will add this in the question. – vi11 Apr 19 at 11:26

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.

• You will then have to find the closest point to the origin in $2^m$ different polytopes though -- one for each choice of each of the $m$ disjunctions. So this would be very expensive for $m>20$ or so. – Rahul Apr 20 at 13:34
• @Rahul I am wondering what happens when vector $\rm b$ has non-positive entries. For example, let us suppose that $b_1 \leq 0$; then, $|\mathrm a_1^\top \mathrm x| \geq b_1$ is satisfied for all $\mathrm x \in \mathbb R^n$ and we are left with $m-1$ conjuncts. Hence, there should be at most $2^p$ polytopes, where $p$ is the number of positive entries of vector $\rm b$. However, there may be symmetry to be exploited and, thus, the exponential may not be all that bad. – Rodrigo de Azevedo Apr 21 at 17:11
• @RodrigodeAzevedo Can I know how exactly to obtain the DNF forms in the convex polytopes and further how is it solved? – vi11 Apr 22 at 6:34
• @vi11 I will update my answer when I find time. How big is your $m$? Are all $b_i$'s positive? – Rodrigo de Azevedo Apr 22 at 19:36
• Yes all $b_i$'s are positive. $m$ could be large too. – vi11 Apr 23 at 5:00