1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – James Sep 15 '18 at 5:25
  • $\begingroup$ $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^*$. $\endgroup$ – Siong Thye Goh Sep 15 '18 at 5:26
  • $\begingroup$ 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 $ ? $\endgroup$ – James Sep 15 '18 at 5:28
  • $\begingroup$ $D_1 = \{ x: Ax \ge b, x \ge 0\}, D_2 =\{x : Ax \ge b, a^Tx \ge \beta, x \ge 0\}$. $\endgroup$ – Siong Thye Goh Sep 15 '18 at 5:30
  • $\begingroup$ 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 $\endgroup$ – James Sep 15 '18 at 5:31

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.