An infeasibility certificate is a point $(\hat{\lambda}, \hat{\mu})$ which certifies that a system of equations has no solution. In particular, it is a point in the feasible set of the dual of the following problem which makes the dual function positive.
$$ \begin{align*} \min_{x \in \R^n} \space & 0 \\ \text{subject to} \space & f_i(x) \le 0, \space i \in [m] \\ & h_j(x) = 0, \space j \in [k] \end{align*} \space \xleftrightarrow{\hspace{15pt}} \space \begin{align*} \max_{\lambda \in \R^m, \space \mu \in \R^k} \space & d(\lambda, \mu) \\ \text{subject to} \space & \lambda \geq 0 \\ & \end{align*} \implies d(\hat{\lambda}, \hat{\mu})>0 $$
The reason why such a point certifies there is no solution is because the optimal objective value is either $0$ or $\infty$ when the problem is feasible and infeasible respectively. Weak duality allows us to assert that any instance of $d >0$ implies that $p^* \geq d^* > 0$, i.e. $p^* = \infty$.
$$ p^* \geq d^* \geq d(\hat{\lambda}, \hat{\mu}) >0 \implies p^* >0 \implies p^* = \infty \implies \mathcal{X} = \empty $$
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Farka’s Lemma. Consider the following linear system:
$$ \begin{cases} Ax= b \hspace{15pt} A \in \R^{m \times n}\\ x \geq 0 \end{cases} $$
The system has no solution iff there exists $\hat{\mu} \in \R^m$ such that $A^T \hat{\mu} \geq 0$ and $b^T \hat{\mu} < 0$.
Given a solution $x^$ to an optimization problem, an inequality constraint $f_i$ is said to be active at $x^$ if $f_i(x^) = 0$ and inactive if $f_i(x^) < 0$. Let $A(x^)$ be the indices of inequality constraints which are active at $x^$ and consider the constraint elimination:
$$
\begin{align*}
\min_{x \in \R^n} \space & f_0(x) \\
\text{subject to} \space & f_i(x) \le 0, \space i \in [m] \\
& h_j(x) = 0, \space j \in [k]
\end{align*} \hspace{10pt} \rightsquigarrow \hspace{10pt} \begin{align*}
\min_{x \in \R^n} \space & f_0(x) \\
\text{subject to} \space & f_i(x) \le 0, \space i \in A(x^) \\
& h_j(x) = 0, \space j \in [k]
\end{align}
$$
Clearly, $x^*$ is a solution to this new optimization problem, so the optimal objective values are the same, however solutions to the reduced problem may be infeasible in the original problem.
Consider an optimization problem and its associated, perturbed problem:
$$
\begin{align*}
\min_{x \in \R^n} \space & f_0(x) \\
\text{subject to} \space & f_i(x) \le 0, \space i \in [m] \\
& h_j(x) = 0, \space j \in [k]
\end{align*} \hspace{10pt} \rightsquigarrow \hspace{10pt} \begin{align*}
\min_{x \in \R^n} \space & f_0(x) \\
\text{subject to} \space & f_i(x) \le v_i, \space i \in [m] \\
& h_j(x) = w_j, \space j \in [k]
\end{align*}
$$
Suppose that $p^(v, w)$ is differentiable at the origin. Take $\lambda^$ and $\mu^*$ to be the following:
$$ \lambda_i ^* := -\frac{\partial p^}{\partial v_i} \bigg| _{(v, w ) =(0,0)} \hspace{25pt} \mu_j^ := -\frac{\partial p^*}{\partial w_j} \bigg| _{(v, w ) =(0,0)} $$
Then, we have the following first-order Taylor expansion for $p^*(v, w)$: