# Proving optimal solution for Linear Programming

Suppose we have a standard optimization problem. $$A'$$ is an optimal solution to the problem. If we add a constraint to our original optimization problem, and $$A'$$ satisfies the new constraint, then is $$A'$$ still optimal for the new optimization problem? If so, prove it.

My solution: Yes, $$A'$$ is still optimal for the new optimization problem. By contradiction, suppose it wasn't optimal for the new problem.

WLOG, assume the original problem was a minimization one, we have for the original problem for all $$x$$ in the original feasible region, $$O$$, $$c' A'. Since $$A'$$ is not optimal for the new problem, there exists some $$x_1$$ in the new feasible region, $$N$$, such that $$c'x_1. However, since we just added a constraint and kept all the previous constraints, the new feasible region must be a subset of the original feasible region. Thus $$x_1 \in$$ O. But, this means that $$A'$$ is not optimal for the original problem, since $$x_1$$ is in the original feasible region, $$O$$ but $$c'x_1. Thus, we have reached a contradiction.

Is this proof correct? Or is it incorrect or perhaps not rigorous enough? For reference the knowledge we have at our disposal is Bertsimas: Linear Optimization Chapter 1. Thanks.

Yes, you have gotten the main idea if the standard optimization problem is a linear one.

Minor comment if the problem is restricted to linear programming:

If $$A'$$ is optimal, then we can write $$c'A' \color{blue}\le c'x.$$

Suppose not, let $$f$$ be the objective function and rather than $$c'x$$, write $$f(x)$$.

• thanks. I forgot that I should put $\leq$ and not $<$. The equals part slightly confuses me. What happens, in the case of equality if $c'A'=c'x$ then no contradiction is reached? – Boy Wonder Sep 9 '19 at 3:13
• actually nevermind so in the first inequality I should write $c'A' \leq c'x$, but the second inequality in the proof is correct with $c'x_1<c'A'$? thanks – Boy Wonder Sep 9 '19 at 3:14
• including the equality because it is possibel that $x=A'$ and also there can be multiple solution. Yes, suppose it is not optimal, then we can find $x_1$ that performs strictly better. – Siong Thye Goh Sep 9 '19 at 3:23
• this might not be a proper question, but what happens if the new optimization problem has no optimal solutions, then supposing A' is not optimal, how can i be sure that i can find $x_1$ that performs better. now again im slightly confused. thanks – Boy Wonder Sep 9 '19 at 3:33
• when we say that $A'$ is feasible but not optimal, it means there is a better solution, the optimal solution need not exists for the argument to work. In layman term, if you are a participant in a contest but not the best, means someone beat you, that person who beat you need not be the champion. – Siong Thye Goh Sep 9 '19 at 3:41