# Linear Programming problem with absolute values

Consider a linear optimization problem, with absolute values, of the following form:

$$\begin{array}{rl} \text{minimize}\ &\mathbf{c'x}+\mathbf{d'y}\\ \text{subject to}\ &\mathbf{Ax}+\mathbf{By}\leq\mathbf{b}\\ &y_i=|x_i|, \end{array}$$

Assume that all entries of B and d are nonnegative.

I have to provide an example to show that if B has negative entries, the problem may have a local minimum that is not a global minimum, but I have really not idea how to it. Can you help me ?

ps: what will happen if the entries of c and A are negatives ?

• I'd start with the case of scalar $x,y$. – hardmath Jul 9 '18 at 16:04
• how do you define a local minimum in constrained optimization? – LinAlg Jul 9 '18 at 16:20

The set of $x\in\mathbb{R}$ which satisfy $1\leqslant|x|\leqslant2$ can be written as $[-2,-1]\cup[1,2]$. This constraint divides the feasible region into two disconnected components...
• @Qwerto Yes, that’s what I’m hinting at here. We have the constraints $-|x|\leqslant-1$ and $|x|\leqslant2$, which is equivalent to $Ax+By\leqslant b$ with $A=0$, $B=(-1,1)^\text{T}$ and $b=(-1,2)^\text{T}$ – David M. Jul 11 '18 at 17:19