Consider the linear program $$\max\limits_x c^t x \quad \text{s.t} \quad Ax=b, x\geq 0. $$ I would like to determine whether a specific basis feasible solution (BFS) $x$ is optimal. (I am not interested in the optimal solution.)
I have two leads.
The KKT conditions characterize optimality. A BFS is optimal if and only if it satisfies the KKT conditions. For a given basis, they are easy to verify (solving a linear system and then checking the inequality constraints, as described in the link). What if there are multiple bases that represent a degenerate BFS? Is it enough to check all possible bases that represent this BFS? Is there anything more efficient, particularly if $x=0$ is to be checked (when $b=0$)?
According to Lemma 4 of these lecture notes, the following statement holds.
Let $x$ be a basic feasible solution and let $B$ be the associated basis. If there is a solution $y$ to the system $A^t y = c_B$ such that $A^t y \leq c$, then $x$ is optimal.
That is a wonderful result. How should it be read for degenerate basic feasible solutions? There are many bases $B$ that might represent the basic feasible solution. My sense is that it implies
If one has a basis for which there exists a solution y to the system $A^t y = c_B$ such that $A^t y \leq c$, then $x$ is optimal.
Is one of the following statements also true?
Let $x$ be a basic feasible solution. If, for a certain basis $B$ that represents $x$, there exists no solution y to the system $A^t y = c_B$ such that $A^t y \leq c$, then $x$ is not optimal.
Let $x$ be a basic feasible solution. If, for any bases $B$ that represents $x$, there exists no solution y to the system $A^t y = c_B$ such that $A^t y \leq c$, then $x$ not optimal.