[proofplan]
We prove both directions of the equivalence. For the forward direction, if $(P)$ is feasible, we exhibit a Phase I solution with objective value $0$ and argue that $0$ is the global minimum. For the converse, if the Phase I optimum is $0$, we extract the $x$-component of the optimal Phase I solution and verify it satisfies the original constraints.
[/proofplan]
[step:Recall the Phase I construction]
Given the linear program $(P)$: minimise $c^\top x$ subject to $Ax = b$, $x \geq 0$, the Phase I problem is
\begin{align*}
\min_{x, y} \quad & \sum_{i=1}^{m} y_i \\
\text{subject to} \quad & Ax + y = b, \\
& x \geq 0, \quad y \geq 0,
\end{align*}
where $y \in \mathbb{R}^m$ is the vector of artificial variables. We assume WLOG that $b \geq 0$ (if $b_i < 0$, multiply the $i$-th constraint by $-1$).
[guided]
The Phase I method introduces one artificial variable $y_i \geq 0$ per equality constraint. The artificial variables serve as a "crutch": the point $(x, y) = (0, b)$ is always feasible for the Phase I problem (since $A \cdot 0 + b = b$ and $b \geq 0$ after sign adjustment). The Phase I objective $\sum_i y_i$ penalises the use of artificial variables. The original system $Ax = b$, $x \geq 0$ is feasible if and only if we can drive all artificial variables to zero, which happens precisely when the Phase I optimum equals $0$.
[/guided]
[/step]
[step:Prove that feasibility of $(P)$ implies the Phase I optimum is $0$]
Suppose $(P)$ is feasible. Then there exists $x^* \geq 0$ with $Ax^* = b$. Consider the point $(x^*, 0)$ in the Phase I problem. We verify feasibility: $Ax^* + 0 = b$ holds, $x^* \geq 0$, and $0 \geq 0$. The Phase I objective at this point is $\sum_{i=1}^{m} 0 = 0$.
Since $y_i \geq 0$ for all $i$, the Phase I objective $\sum_i y_i \geq 0$ for every feasible Phase I solution. Therefore $0$ is a lower bound on the Phase I optimal value. Since we have exhibited a feasible point achieving $0$, the Phase I optimal value is exactly $0$.
[guided]
Suppose $(P)$ is feasible, so there exists $x^* \in \mathbb{R}^n$ with $Ax^* = b$ and $x^* \geq 0$. We construct a Phase I feasible point by setting the artificial variables to zero: $(x, y) = (x^*, 0)$.
**Feasibility check**: $Ax^* + 0 = Ax^* = b$ (since $x^*$ solves the original system), $x^* \geq 0$ (given), and $y = 0 \geq 0$. So $(x^*, 0)$ is feasible for the Phase I problem.
**Objective value**: $\sum_{i=1}^{m} y_i = \sum_{i=1}^{m} 0 = 0$.
**Optimality**: can we do better than $0$? No. Every feasible Phase I solution satisfies $y_i \geq 0$ for all $i$, so $\sum_i y_i \geq 0$. The value $0$ is therefore the minimum possible, and $(x^*, 0)$ achieves it.
[/guided]
[/step]
[step:Prove that a Phase I optimum of $0$ implies feasibility of $(P)$]
Conversely, suppose the Phase I problem has optimal value $0$. Let $(x^*, y^*)$ be an optimal Phase I solution. Then
\begin{align*}
\sum_{i=1}^{m} y_i^* = 0.
\end{align*}
Since $y_i^* \geq 0$ for each $i$, the only way their sum can equal $0$ is if $y_i^* = 0$ for all $i = 1, \ldots, m$. Therefore $y^* = 0$.
Substituting $y^* = 0$ into the Phase I constraint $Ax^* + y^* = b$ yields $Ax^* = b$. Since $x^* \geq 0$ is also guaranteed by Phase I feasibility, the point $x^*$ satisfies $Ax^* = b$ and $x^* \geq 0$, which means $x^*$ is feasible for $(P)$.
[guided]
Now suppose the Phase I optimum equals $0$, and let $(x^*, y^*)$ be an optimal solution.
**Artificial variables vanish**: the optimal objective value is $\sum_i y_i^* = 0$. Each $y_i^*$ is constrained to be non-negative, so a sum of non-negative terms equalling zero forces every term to vanish: $y_i^* = 0$ for all $i$.
Why is this step important? If even one $y_i^* > 0$ at the optimum, the Phase I optimal value would be strictly positive, contradicting our assumption. The vanishing of $y^*$ is the mechanism by which Phase I "certifies" feasibility.
**Recovering a feasible point for $(P)$**: with $y^* = 0$, the Phase I constraint becomes $Ax^* + 0 = b$, i.e., $Ax^* = b$. The constraint $x^* \geq 0$ is part of Phase I feasibility. Together, $Ax^* = b$ and $x^* \geq 0$ mean that $x^*$ is feasible for the original problem $(P)$.
[/guided]
[/step]
[step:Combine both directions to conclude the equivalence]
We have shown:
- If $(P)$ is feasible, then the Phase I optimal value is $0$.
- If the Phase I optimal value is $0$, then $(P)$ is feasible.
Therefore $(P)$ is feasible if and only if the Phase I problem has optimal value $0$. Equivalently, $(P)$ is infeasible if and only if the Phase I optimal value is strictly positive.
[/step]
