1

enter image description here

Attempt

First of all, I am confused as to the wording of the problem, they say the new constrain is $a^T x \geq \beta$, but they didnt say what $a$ is. Can we assume is a row of $A$?

IF so, then here is what I can do:

Since $x^*$ is feasible to the new constraint, then we know so far that $a^T x^* \geq \beta $. To prove optimality, i Need to problem that $c^T x^* \leq c^T x $ for all $x$ that satisfies all the constrains including the new one. We know however that

$$ c^T x^* \leq c^T y $$

where $ y $ satisfies the old constrains: $Ay \geq b $ and $y \geq 0 $. Here Is where I get stuck. Am I on the right track to prove this proposition?

Update:

If we argue by contradiction. Suppose $x^*$ is not optimal to new added constrain so there is some $x'$ so that $c^T x' > c^T x^*$.

Here, if $x'$ also satisfies $Ax' \geq b $ and $x' \geq 0$ then that would be a contradiction since that means we would have found another point in the feasible region that is bigger than the smallest value.

But, I am still haveing trouble understanding why is this $x'$ also belongs to the old constraint. What am I missing here?

Community
  • 1
James
  • 3,997

1 Answers1

2

You can view the problem as $\hat{A} = \begin{bmatrix} A \\ a^T \end{bmatrix}$ and $\hat{b} = \begin{bmatrix} b \\ \beta\end{bmatrix}$ and the new LP is

$$\min \{ c^Tx | \hat{A}x \ge \hat{b}, x \ge 0\}$$

In general suppose we have two optimization problem where the first problem is

$$ \min\{ f(x)|x \in D_1\}$$ and the second problem is

$$ \min\{ f(x)|x \in D_2\}.$$

$D_2 \subseteq D_1$ and $x^*$ is an optimal solution to the first problem, if $x^* \in D_2$, then we can conclude that $x^*$ is an optimal solution to the second problem as well.

The reason is suppose it is not optimal, then $\exists y \in D_2$ such that $f(y) <f(x^*)$ but $y \in D_1$, hence $y$ is a better solution compared to $x^*$, violating the condiion that $x^*$ is optimal in the first problem, which is a contradiction.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Thanks for your reply! Ive made an update with the insight you gave me. I am still having hard time understanding how would this new point in the new contraint would also satisfy the old constraint. – James Sep 15 '18 at 05:25
  • $D_2 \subset D_1$ isn't it? hence if $y \in D_2$, we know that $y \in D_1$. Also, since we are working with minimization problem, a better solution would satisfies $c^Tx' < c^Tx^*$. – Siong Thye Goh Sep 15 '18 at 05:26
  • I dont know why is that true though. I see $D_1 = { x : Ax \geq b, x \geq 0 } $ and $D_2 = { x : a^T x \geq \beta } $. IF $a^T x \geq \beta $, how can this imply that $A x \geq b $ and $x \geq 0 $ ? – James Sep 15 '18 at 05:28
  • $D_1 = { x: Ax \ge b, x \ge 0}, D_2 ={x : Ax \ge b, a^Tx \ge \beta, x \ge 0}$. – Siong Thye Goh Sep 15 '18 at 05:30
  • I understand now. I misread the problem. Sorry I always have trouble with reading the statement. I got it now. Now I see this problem becomes really simple then – James Sep 15 '18 at 05:31