1

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

\begin{equation} \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} \end{equation}

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 ?

David M.
  • 2,623
Qwerto
  • 969
  • 6
  • 20

1 Answers1

2

Hint:

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...

David M.
  • 2,623
  • So if B has negative entries is possible to create disconnected feasible regions ? If yes, it's still not clear how it happens... – Qwerto Jul 11 '18 at 17:15
  • 1
    @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
  • Now it's clear. Instead, what will happen if the entries of c and A are negatives ? – Qwerto Jul 11 '18 at 17:25
  • Lots of things could happen. You would have to be a little more specific. – David M. Jul 11 '18 at 17:26
  • To me, if c can assume negative values there is the risk of a unbounded solution. Instead do you think that if A has negative values similar problems can arise ? – Qwerto Jul 11 '18 at 17:30
  • @Qwerto Try playing with examples in one dimension and see what you can create – David M. Jul 12 '18 at 00:32
  • I want to explicitly add that if you have 2 disconnected feasible regions, you must search both to find a global minimum. If you search only 1 and find the minimum, that same minimum may be in the other. So the minimum you found is either the global (but you only know by checking the other feasible region), the same minimum as the other region (so local is global minimum), or its the global minimum (but you only know by finding the minimum of the other region which would be a local for that region.) – Avedis Sep 17 '20 at 13:29