Linear programming: Which extreme point is chosen when a constraint is added? I have a linear objective function $V'x$ I'm trying to maximize on a cell, $x \in [0,1]^n$. So obviously, I have one of the extreme points as the optimum. Now suppose I add a constraint of the form $A_1x \geq 0$, such that the existing optimum is no longer feasible. My question is: Is it possible that the new optimum is one of the old extreme points (i.e. one of the extreme points of $[0,1]^n$ other than the old optimum) rather than one of the newly created ones (by adding $A_1x \geq 0$)? We can assume away rare cases like $A_1x =0$ passes through one of the extreme points of $[0,1]^n$.
Thanks in advance.
 A: The new optimum must lie on $A_1x = 0$, assuming the original optimal solution was unique.
To see this, let $x^*$ be the original optimal solution (with $A_1 x^* < 0$) and let $y$ be any extreme point of $[0,1]^n$ with $A_1 y > 0$. Then along the line segment from $y$ to $x^*$:

*

*The objective value must be increasing, since $x^*$ has a better objective value than $y$.

*The points are all in $[0,1]^n$, since $[0,1]^n$ is convex.

Since $A_1x^* < 0$ and $A_1y > 0$, there is a point $tx^* + (1-t)y$ at which $A_1(tx^* + (1-t)y) = 0$. That point is a better point than $y$, therefore $y$ cannot be the optimal solution.
Therefore no extreme points of the new region with $A_1x < 0$ can be optimal solutions, and the optimal solution must satisfy $A_1x = 0$: it must lie on the newly added constraint.

If the original optimal solution was not unique, then it's possible that we cut off some but not all optimal solutions, in which case some points with $A_1x > 0$ might still be optimal. Even in that case, by moving towards $x^*$ from such a solution, we can find another optimal solution on the hyperplane $A_1 x= 0$.
