1
$\begingroup$

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 ?

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

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

$\endgroup$
  • $\begingroup$ So if B has negative entries is possible to create disconnected feasible regions ? If yes, it's still not clear how it happens... $\endgroup$ – Qwerto Jul 11 '18 at 17:15
  • 1
    $\begingroup$ @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}$ $\endgroup$ – David M. Jul 11 '18 at 17:19
  • $\begingroup$ Now it's clear. Instead, what will happen if the entries of c and A are negatives ? $\endgroup$ – Qwerto Jul 11 '18 at 17:25
  • $\begingroup$ Lots of things could happen. You would have to be a little more specific. $\endgroup$ – David M. Jul 11 '18 at 17:26
  • $\begingroup$ 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 ? $\endgroup$ – Qwerto Jul 11 '18 at 17:30

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.