4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Are you asking about using the primal or dual solution to the Phase I problem to construct the certificate? $\endgroup$
    – prubin
    Jul 6 at 16:10
  • $\begingroup$ 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. $\endgroup$
    – fmg
    Jul 7 at 16:46

2 Answers 2

5
$\begingroup$

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.

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

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

$\endgroup$

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.