Phase I of the simplex method and Farkas certificates

Question

Phase I of the simplex method solves an auxiliary optimization problem to determine an initial basic feasible solution, or concludes that no such exists. Is there a way to use the solution of this auxiliary problem to construct a Farkas certificate for the infeasibility of the original (assume standard form), i.e., a vector $p$ such that $p^TA \geq 0$ and $p^Tb < 0$?

Answer 1

If the phase 1 problem proves the problem is primal infeasible, then the optimal dual solution is a Farkas certificate. That was the conclusion I made during research when I wrote:

https://link.springer.com/article/10.1023/A:1011259103627

Indeed in Section 3 this is proved for one specific phase 1 problem.

Answer 2

Let me add a few details of @ErlingMOSEK's answer, so the thread is self-contained.

Suppose $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$. To determine the feasibility of $Ax=b$, $x\geq 0$, we solve the auxiliary problem $$ \text{minimize}\quad y_1+\cdots + y_m\quad\text{subject to}\quad Ax + y = b,\; x,y\geq 0. $$ (This is "Phase I" of the simplex method.)

It's easy to see that the original problem $Ax=b$, $x\geq 0$ is feasible if and only if the auxiliary problem has optimal objective value $0$.

Suppose the original problem is infeasible. Then the optimal value of the auxiliary problem is strictly positive. By strong duality, this strictly positive value is also the optimal objective value of the dual of the auxiliary problem: $$ \text{maximize}\quad p^Tb\quad\text{subject to}\quad p^T\begin{pmatrix}A& I_{m\times m}\end{pmatrix}\leq \begin{pmatrix}0_n&1_m\end{pmatrix} $$ If $p$ realizes the strictly positive optimal value, then $p^Tb > 0$ and $p^TA\leq 0$, giving a Farkas certificate for the infeasibility of $Ax=b$, $x\geq 0$.