<blockquote>
<p>A candidate for a variant of the strong duality theorem is: the primal LP has a solution <span class="math-container">$\mathbf{x^*}$</span> for which:
<span class="math-container">$$
\mathbf{b^T y'} \cdot (1+\epsilon) \geq \mathbf{c^T x^*} \geq b^T \mathbf{y'}/(1+\epsilon)
$$</span>
Is this true?</p>
</blockquote>
<p><strong>The answer is yes</strong> (assuming the optimal solution has non-negative cost, e.g. <span class="math-container">$c\ge \mathbf 0$</span>), simply by strong duality.  Let <span class="math-container">$(x^*, y^*)$</span> be an optimal primal-dual pair.  Then</p>
<ol>
<li><span class="math-container">$c \cdot x^* = b\cdot y^* \le b\cdot y' \le (1+\epsilon) b\cdot y'$</span> (by your assumption on <span class="math-container">$y'$</span>, and <span class="math-container">$b\cdot y^*\ge 0$</span>), and</li>
<li><span class="math-container">$c\cdot x^* \ge b\cdot y'/(1+\epsilon)$</span> (by weak duality, as you point out, as <span class="math-container">$y'/(1+\epsilon)$</span> is a feasible dual solution)</li>
</ol>
<p>So, in this case, technically, this <span class="math-container">$x^*$</span> answers your question affirmatively.</p>
<p>(I assume you don't intend to consider the case that the optimal cost is negative, because this case requires <span class="math-container">$c \not\ge \mathbf 0$</span>, and then your condition <span class="math-container">$A^T y' \le (1+\epsilon) c$</span> is not actually a relaxation of <span class="math-container">$A^T y' \le c$</span>.)</p>
<blockquote>
<p>Is there an algorithm for finding such <span class="math-container">$x^*$</span> given <span class="math-container">$y'$</span>?</p>
</blockquote>
<p><strong>The answer is yes.</strong>  One can compute <span class="math-container">$x^*$</span> (given <span class="math-container">$y'$</span>, or not) in poly-time by solving the LP.</p>
<p><strong>Okay, but is there a faster way?</strong>  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
<span class="math-container">$$\min \{ 0 : Ax\ge b, x\ge 0\}.$$</span>
The problem of finding an optimal or approximately optimal primal solution is equivalent to the problem of finding a <em>feasible</em> primal solution, as <span class="math-container">$c=\mathbf 0$</span>.
Assuming the primal is feasible, the dual solution <span class="math-container">$y = \mathbf 0$</span> is optimal, and gives no information about how to find the primal solution.</p>
<p>For a concrete example, consider the problem of finding a perfect matching in a given bipartite graph <span class="math-container">$G$</span>.  This can be formulated in the above form, as <span class="math-container">$\min \{c\cdot x : Ax\ge b, x\ge 0\}$</span> with <span class="math-container">$c = \mathbf 0$</span>, using a variable <span class="math-container">$x_e\ge 0$</span> for each edge <span class="math-container">$e$</span>, and encoding the perfect-matching constraints <span class="math-container">$(\forall v) \sum_{e \text{ inc } v} x_e = 1$</span> in the matrix constraints <span class="math-container">$Ax\ge b$</span>, as <span class="math-container">$B x \ge 1$</span> and <span class="math-container">$-Bx \ge -1$</span> where <span class="math-container">$B_v x = \sum_{e\text{ inc } v} x_e$</span>.  If <span class="math-container">$G$</span> has a perfect matching, then the dual solution <span class="math-container">$y_v = 0$</span> is optimal, and gives no information about how to compute any feasible (and therefore optimal or approximately optimal) perfect matching.</p>

CC BY-SA 4.0
2022-03-15T21:54:50.630Z
I do wonder about the special case of packing and covering, that is, when all entries of $A$ are non-negative.
Neal Young
CC BY-SA 4.0
2022-03-15T14:25:12.360Z
2022-03-15T14:31:56.053Z
2022-03-15T14:31:56.053Z
Neal Young
<p>Consider the following dual linear programs:
<span class="math-container">$$
\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.
$$</span>
By the strong duality theorem, if there is an optimal solution <span class="math-container">$\mathbf{y^*}$</span> to the dual problem, then the primal problem has an optimal solution <span class="math-container">$\mathbf{x^*}$</span> with <span class="math-container">$\mathbf{c^T x^*} = \mathbf{b^T y^*}$</span>.</p>
<p>Suppose now that the dual problem is very large, and I can solve it only approximately. Specifically, I can find a vector <span class="math-container">$\mathbf{y'}$</span> such that:</p>
<ul>
<li><span class="math-container">$A^T \mathbf{y'} \leq (1+\epsilon)\cdot \mathbf{c}$</span> - the constraints are only approximately satisfied;</li>
<li><span class="math-container">$\mathbf{b^T y'} \geq \mathbf{b^T y}$</span> for any vector <span class="math-container">$\mathbf{y}$</span> that satisfies the original constraints <span class="math-container">$\mathbf{y} \leq \mathbf{c}$</span>.</li>
</ul>
<p>So <span class="math-container">$\mathbf{y'}$</span> is optimal for the original constraints, but it may violate these constraints a bit.</p>
<p>QUESTION: Can I draw from this, any conclusion regarding the optimal (or approximately-optimal) solution of the primal LP?</p>
<p>NOTE: It is easy to prove a variant of the weak duality theorem for this setting. If <span class="math-container">$\mathbf{x}$</span> is any feasible solution to the primal, then:</p>
<p><span class="math-container">$$
\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).
$$</span></p>
<p>So a candidate for a variant of the strong duality theorem is: the primal LP has a solution <span class="math-container">$\mathbf{x^*}$</span> for which:
<span class="math-container">$$
\mathbf{b^T y'} \cdot (1+\epsilon) \geq \mathbf{c^T x^*} \geq b^T \mathbf{y'}/(1+\epsilon)
$$</span>
Is this true?</p>
<p>If so, is there an algorithm for finding such <span class="math-container">$\mathbf{x^*}$</span>, given the vector <span class="math-container">$\mathbf{y'}$</span>?</p>

<optimization><linear-programming><primal-dual>
Is there an approximate version of the strong duality theorem for linear programming?
Erel Segal-Halevi
# Is there an approximate version of the strong duality theorem for linear programming?

(Asked by: username_0 on 2022-03-15)

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

**Tags:** optimization, linear-programming, primal-dual

---

## 1 answers

### Answer by username_1 on 2022-03-15. Score: 6 | Accepted answer

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

> **Comments:**
> **username_1**: I do wonder about the special case of packing and covering, that is, when all entries of $A$ are non-negative.  

---

