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'<c'x$. 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<c'A'$. 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<c'A'$. 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)$.

  • $\begingroup$ 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? $\endgroup$ – Boy Wonder Sep 9 '19 at 3:13
  • $\begingroup$ 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 $\endgroup$ – Boy Wonder Sep 9 '19 at 3:14
  • $\begingroup$ 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. $\endgroup$ – Siong Thye Goh Sep 9 '19 at 3:23
  • $\begingroup$ 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 $\endgroup$ – Boy Wonder Sep 9 '19 at 3:33
  • $\begingroup$ 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. $\endgroup$ – Siong Thye Goh Sep 9 '19 at 3:41

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.