Primal-Dual Algorithm

Primal:

We assume that $b \ge 0$. Otherwise we can flip the $i$ constraints $A^T_i x = b_i$ by $- A^T_i x = -b_i$, where $A^T_i$ is the $i$-th column of matrix $A^T$, i.e, the $i$-th row of matrix $A$.

Dual:

Suppose that we have a feasible solution $y$ for the dual (if $c \ge 0$, then $y = 0$ is a feasible solution). Weak duality states that

Denote $S = \{ i : i \in [n], y^T A_i < c_i \}$ (the set of constraints that have slacks for increments) and $\bar S = [n] \setminus S$ (the set of indexes of tight dual constraints), where $A_i$ is the $i$-th columns of $A$.

By weak duality, if we can find an $x$ such that

1. $x_{S } = 0$, where $x_{S} \doteq (x_i : i \in {S})$.
2. $x_{\bar S} \ge 0$ and $A_{\bar S} x_{\bar S} = b$, where $A_{\bar S}$ is the sub-matrix of $A$ containing only columns in ${\bar S}$.

then both $y$ and $x$ are optimal. However, as $y$ is not necessarily optimal, we have the following relaxed optimization problem, which is called restricted primal

Relaxation:

Note that $x_{\bar S} = 0$ and $\bar x = b$ is a feasible solution as we assume that $b \ge 0$. Therefore, restricted primal is feasible. Further, it is bounded below by $1^{\bar S} 0 = 0$. Indeed, if it achieves optimal solution value $0$, it holds that $\bar x = 0$ so that $A_{\bar S} x_{\bar S} = b$.

Associated with the restricted primal is the restricted dual

By strong duality, it optimal solution $\bar y^T b = 1^T \bar x$. If $1^T \bar x= \bar y^T b > 0$, then we can improve the dual solution $y$ by

for some $\epsilon$. To determine its value, first observe that

Hence it is left to guarantee that

By definition of ${S}$, we have $y^T A_{S} < c_{S}^T$. If that $\bar y^T A_i \le 0$ for $\forall i \in {S}$, then $\epsilon$ can be arbitrary large and the dual is unbounded. Otherwise,