# Trying to prove an statement with unclear premises

## 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?

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.

• 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 5: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 5: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 5: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 5: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 5:31