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.