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?

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

  • $\begingroup$ 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. $\endgroup$ – Rahul Apr 20 at 13:34
  • $\begingroup$ @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. $\endgroup$ – Rodrigo de Azevedo Apr 21 at 17:11
  • $\begingroup$ @RodrigodeAzevedo Can I know how exactly to obtain the DNF forms in the convex polytopes and further how is it solved? $\endgroup$ – vi11 Apr 22 at 6:34
  • $\begingroup$ @vi11 I will update my answer when I find time. How big is your $m$? Are all $b_i$'s positive? $\endgroup$ – Rodrigo de Azevedo Apr 22 at 19:36
  • $\begingroup$ Yes all $b_i$'s are positive. $m$ could be large too. $\endgroup$ – vi11 Apr 23 at 5:00

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.