Is there an approximate version of the strong duality theorem for linear programming?

Question

Consider the following dual linear programs: $$ \min \mathbf{c^T x} ~~ \text{s.t.} ~~ A \mathbf{x} \geq \mathbf{b}, \mathbf{x}\geq 0; \\ \max \mathbf{b^T y} ~~ \text{s.t.} ~~ A^T \mathbf{y} \leq \mathbf{c}, \mathbf{y}\geq 0. $$ By the strong duality theorem, if there is an optimal solution $\mathbf{y^*}$ to the dual problem, then the primal problem has an optimal solution $\mathbf{x^*}$ with $\mathbf{c^T x^*} = \mathbf{b^T y^*}$.

Suppose now that the dual problem is very large, and I can solve it only approximately. Specifically, I can find a vector $\mathbf{y'}$ such that:

• $A^T \mathbf{y'} \leq (1+\epsilon)\cdot \mathbf{c}$ - the constraints are only approximately satisfied;
• $\mathbf{b^T y'} \geq \mathbf{b^T y}$ for any vector $\mathbf{y}$ that satisfies the original constraints $\mathbf{y} \leq \mathbf{c}$.

So $\mathbf{y'}$ is optimal for the original constraints, but it may violate these constraints a bit.

QUESTION: Can I draw from this, any conclusion regarding the optimal (or approximately-optimal) solution of the primal LP?

NOTE: It is easy to prove a variant of the weak duality theorem for this setting. If $\mathbf{x}$ is any feasible solution to the primal, then:

$$ \mathbf{c^T x} = \mathbf{x^T c} \geq \\ \geq \mathbf{x^T}\cdot A^T\mathbf{y'}/(1+\epsilon) \\ = (A\mathbf{x})^T\cdot \mathbf{y'}/(1+\epsilon) \\ \geq \mathbf{b^T y'}/(1+\epsilon). $$

So a candidate for a variant of the strong duality theorem is: the primal LP has a solution $\mathbf{x^*}$ for which: $$ \mathbf{b^T y'} \cdot (1+\epsilon) \geq \mathbf{c^T x^*} \geq b^T \mathbf{y'}/(1+\epsilon) $$ Is this true?

If so, is there an algorithm for finding such $\mathbf{x^*}$, given the vector $\mathbf{y'}$?

Answer 1

A candidate for a variant of the strong duality theorem is: the primal LP has a solution $\mathbf{x^*}$ for which: $$ \mathbf{b^T y'} \cdot (1+\epsilon) \geq \mathbf{c^T x^*} \geq b^T \mathbf{y'}/(1+\epsilon) $$ Is this true?

The answer is yes (assuming the optimal solution has non-negative cost, e.g. $c\ge \mathbf 0$), simply by strong duality. Let $(x^*, y^*)$ be an optimal primal-dual pair. Then

1. $c \cdot x^* = b\cdot y^* \le b\cdot y' \le (1+\epsilon) b\cdot y'$ (by your assumption on $y'$, and $b\cdot y^*\ge 0$), and
2. $c\cdot x^* \ge b\cdot y'/(1+\epsilon)$ (by weak duality, as you point out, as $y'/(1+\epsilon)$ is a feasible dual solution)

So, in this case, technically, this $x^*$ answers your question affirmatively.

(I assume you don't intend to consider the case that the optimal cost is negative, because this case requires $c \not\ge \mathbf 0$, and then your condition $A^T y' \le (1+\epsilon) c$ is not actually a relaxation of $A^T y' \le c$.)

Is there an algorithm for finding such $x^*$ given $y'$?

The answer is yes. One can compute $x^*$ (given $y'$, or not) in poly-time by solving the LP.

Okay, but is there a faster way? No, not in general. Even having an optimal feasible dual solution does not always make it easy to compute an approximately optimal primal solution. Consider any primal problem of the form $$\min \{ 0 : Ax\ge b, x\ge 0\}.$$ The problem of finding an optimal or approximately optimal primal solution is equivalent to the problem of finding a feasible primal solution, as $c=\mathbf 0$. Assuming the primal is feasible, the dual solution $y = \mathbf 0$ is optimal, and gives no information about how to find the primal solution.

For a concrete example, consider the problem of finding a perfect matching in a given bipartite graph $G$. This can be formulated in the above form, as $\min \{c\cdot x : Ax\ge b, x\ge 0\}$ with $c = \mathbf 0$, using a variable $x_e\ge 0$ for each edge $e$, and encoding the perfect-matching constraints $(\forall v) \sum_{e \text{ inc } v} x_e = 1$ in the matrix constraints $Ax\ge b$, as $B x \ge 1$ and $-Bx \ge -1$ where $B_v x = \sum_{e\text{ inc } v} x_e$. If $G$ has a perfect matching, then the dual solution $y_v = 0$ is optimal, and gives no information about how to compute any feasible (and therefore optimal or approximately optimal) perfect matching.