Requirement of Convexity to Linearize the Absolute Value Minimization Problem

30 Views Asked by At

Let us consider that we have to minimize $\sum_{i=1}^{n} c_i \lvert x_i \rvert$ such that $\mathbf{Ax} \geq \mathbf{b}$ where $\mathbf{A} \in \mathbb{R}^{m \times n}$ and $m<n$.

Clearly, it is a convex problem if $c_i$'s are all positive.

The problem can be linearized by using the fact that $\lvert x_i\rvert \leq z_i$. So, we put this as constraints and rewrite the objective function as $\sum_{i=1}^{n} c_i z_i$.

But, I am not able to realize where we need the fact that $c_i$'s are positive if we are trying to solve the following optimization problem:

\begin{eqnarray*} & \min_{\mathbf{x},\mathbf{z} \in \mathbb{R}^n} & \sum_{i=1}^{n} c_i z_i\\ & \text{s.t.} & \mathbf{Ax} \geq \mathbf{b}\\ & & x_i \leq z_i \text{ and } -x_i \leq z_i, \forall i= 1, \dots,n. \end{eqnarray*}