# Phase I of the simplex method and Farkas certificates

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$$?

• Are you asking about using the primal or dual solution to the Phase I problem to construct the certificate?
– prubin
Jul 6 at 16:10
• By @ErlingMOSEK's answer, the information is contained in the dual solution to the Phase I problem that is accessible if the problem is solved using, e.g., the revised simplex method.
– fmg
Jul 7 at 16:46

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:

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

• I'm including a few details of @ErlingMOSEK's answer below, for others who stumble upon this thread.
– fmg
Jul 7 at 16:44

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$$.