4
$\begingroup$

Consider a linear programming (LP) problem \begin{align} M(b) \in \arg\min_x \{ c^\top x : Ax=b, x \ge 0 \}. \end{align} Suppose the LP is feasible and bounded for all values of $b$. We know that $M(b)$ may not be a function, as $M(b)$ may not be unique. If at a given $b$, the LP has a unique solution, then "locally" M(b) is a linear function of $b$. This is because the basic feasible solution is $x_{B}=B^{-1}b$, where $B$ is the optimal basis. So, for sufficiently small changes in $b$, the optimal basis $B$ does not change, so the optimal solution will be $M(b+\hat{b})=B^{-1}b + B^{-1}\hat{b}$, where $\hat{b}$ is a small perturbation in $b$.

My question is what can be said for more global changes where the optimal basis changes? Does $M(b)$ have a piecewise linear behaviour?

$\endgroup$
1
  • 1
    $\begingroup$ You need to be a bit careful with the idea of "unique" solution. If the solution for a particular $b$ is degenerate, then the optimal value of $x$ for that $b$ may be unique but the basis is not. So perturbations in some directions, no matter how small, may change the basis. $\endgroup$ – prubin Oct 27 '20 at 19:11
3
$\begingroup$

In general, if the LP is bounded, the optimal set $M(b)$ is a face of the feasible set $P = \{ x | Ax = b, x \geq 0\}$ (which is a polyhedral set). In fact, $M$ is a function, but one that maps a vector $b \in \mathbb{R}^{m}$ to a set of points $M(b) \subseteq \mathbb{R}^{n}$.

Thus, in order to talk about piece-wise linearity of $M$, you must define what you mean by piece-wise linearity of such a function.

The objective function of an LP is a piece-wise linear function of $b$, though.

That being said, take the example \begin{align} \min_{x, y} \ \ \ & -x - y\\ \text{s.t.} \ \ \ & x + y = b\\ & x, y \geq 0 \end{align}

Here,

  • If $b < 0$, the LP is infeasible.
  • $M(0) = \{(0, 0)\}$ (a singleton)
  • $M(b > 0) = \{(x, y) \geq 0 \ | \ x + y = b\}$ (a one-dimensional segment)

so the dimension of $M(b)$ may change for small variations in $b$.

Two side remarks:

  • depending on the data $A, c$, there may exist values of $b$ for which the LP is unbounded or infeasible, so the assumption that $LP$ is bounded and feasible for all values of $b$ may not hold in practice.
  • Changing the primal right-hand side corresponds to changing the dual objective. This perspective may simplify the analysis.
$\endgroup$
1
  • $\begingroup$ Thanks @mtanneau. This is a nice discussion. $\endgroup$ – Arthur Oct 27 '20 at 19:53

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.