Skip to main content
Formatting
Source Link
Kaveh
  • 22.5k
  • 4
  • 52
  • 112

Probably not. ThereHere is a conceptual argument, which is based on

Farkas AlternativeFarkas Lemma: Exactly Exactly one of $Ax\le b$, $x\ge 0$ or $y^TA\ge 0$ $y^Tb < 0$the following alternatives has a solution.:

  1. $Ax \le b$ and $x \ge 0$
  2. $y^TA\ge 0$ and $y^Tb < 0$

Assuming this, takeNow let $\delta$ to be the optimal objective value of the primal in an optimal solution. Define Let $\epsilon > 0$ be arbitrary. Let $A'$ to be the matrix that is $A$ with an additional $-c^T$ as the last row and. Let $b'$ to be the vector $(b, -\delta - \epsilon)$. For any$b$ with an additional $\epsilon > 0$,$-\delta - \epsilon$ as the last value.

The system $A'x'\le b'$ has no solution, so according to. By Farkas, there is a $y' = (y,\alpha)$ such that $y^TA\le \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$. Moreover, $\alpha > 0$, since, when:

$y^TA\ge \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$.

Note that if $\epsilon = 0$ we are in the other alternative of Farkas. Therefore $\alpha > 0$.

To finish up, just scaleScale $y'$ so that $\alpha = 1$. Now   $y$ is dual feasible, so. The weak duality implies $\delta \le y^Tb < \delta + \epsilon$, and we are done.

Probably not. There is a conceptual argument, which is based on

Farkas Alternative: Exactly one of $Ax\le b$, $x\ge 0$ or $y^TA\ge 0$ $y^Tb < 0$ has a solution.

Assuming this, take $\delta$ to be the objective value of the primal in an optimal solution. Define $A'$ to be the matrix that is $A$ with $-c^T$ as the last row and $b'$ to be the vector $(b, -\delta - \epsilon)$. For any $\epsilon > 0$, the system $A'x'\le b'$ has no solution, so according to Farkas, there is a $y' = (y,\alpha)$ such that $y^TA\le \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$. Moreover, $\alpha > 0$, since, when $\epsilon = 0$ we are in the other alternative of Farkas.

To finish up, just scale $y'$ so that $\alpha = 1$. Now $y$ is dual feasible, so weak duality implies $\delta \le y^Tb < \delta + \epsilon$, and we are done.

Probably not. Here is a conceptual argument based on

Farkas Lemma: Exactly one of the following alternatives has a solution:

  1. $Ax \le b$ and $x \ge 0$
  2. $y^TA\ge 0$ and $y^Tb < 0$

Now let $\delta$ be the optimal objective value of the primal. Let $\epsilon > 0$ be arbitrary. Let $A'$ to be $A$ with an additional $-c^T$ as the last row. Let $b'$ to be $b$ with an additional $-\delta - \epsilon$ as the last value.

The system $A'x'\le b'$ has no solution. By Farkas, there is a $y' = (y,\alpha)$ such that:

$y^TA\ge \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$.

Note that if $\epsilon = 0$ we are in the other alternative of Farkas. Therefore $\alpha > 0$.

Scale $y'$ so that $\alpha = 1$.  $y$ is dual feasible. The weak duality implies $\delta \le y^Tb < \delta + \epsilon$.

Source Link
Louis
  • 2.9k
  • 16
  • 25

Probably not. There is a conceptual argument, which is based on

Farkas Alternative: Exactly one of $Ax\le b$, $x\ge 0$ or $y^TA\ge 0$ $y^Tb < 0$ has a solution.

Assuming this, take $\delta$ to be the objective value of the primal in an optimal solution. Define $A'$ to be the matrix that is $A$ with $-c^T$ as the last row and $b'$ to be the vector $(b, -\delta - \epsilon)$. For any $\epsilon > 0$, the system $A'x'\le b'$ has no solution, so according to Farkas, there is a $y' = (y,\alpha)$ such that $y^TA\le \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$. Moreover, $\alpha > 0$, since, when $\epsilon = 0$ we are in the other alternative of Farkas.

To finish up, just scale $y'$ so that $\alpha = 1$. Now $y$ is dual feasible, so weak duality implies $\delta \le y^Tb < \delta + \epsilon$, and we are done.