0
$\begingroup$

A typical linear program is written as L0: $min_{x \geq 0; A^T x \leq b}$ $c^Tx$. Here, $x \in \mathcal{R}^n$, $c \in \mathcal{R}^n$, $A \in \mathcal{R}^{m \times n}$, and $b \in \mathcal{R}^m$.

Now consider a matrix $M \in \mathcal{R}^{m \times m}$ which is multiplied on both sides of the inequality constraints such that the problem becomes L1: $min_{x \geq 0; MA^T x \leq Mb}$ $c^Tx$.

What should be the constraints on M such that L0 and L1 have the same

  1. feasible region
  2. and/or the same solutions

The answer is somewhat clear in the case of equality - M should be an invertible matrix (I might be wrong here too).

What mathematical concepts should I use to reason about the above problem? Any help is highly appreciated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.