<p>We wish to solve an LP in the standard form</p>
<blockquote>
<p>Choose vector <span class="math-container">$x$</span> to maximize <span class="math-container">$c^T x$</span> subject to <span class="math-container">$Ax \le b$</span>.</p>
</blockquote>
<p>Let <span class="math-container">$x^*$</span> be a feasible point.  By LP duality, <span class="math-container">$x^*$</span> solves the LP iff we can write the objective vector <span class="math-container">$c$</span> as a positive linear combination of the constraints that are tight at <span class="math-container">$x^*$</span>.  Formally:</p>
<blockquote>
<p><strong>Theorem (LP Duality):</strong> Let <span class="math-container">$R^*$</span> be the set of row vectors <span class="math-container">$r_i$</span> in <span class="math-container">$A$</span> for which <span class="math-container">$r_i x^* = b_i$</span>.  Then <span class="math-container">$x^*$</span> is an optimal solution to the LP if and only if <span class="math-container">$c^T \in \text{posspan}(R^*)$</span>.</p>
</blockquote>
<p>I am looking for a relaxed version of this theorem statement, where we verify <span class="math-container">$x^*$</span> by handling some constraints in <span class="math-container">$R^*$</span> in a dual manner as above, and the rest in a primal manner.  My ideal theorem statement looks something like the following:</p>
<blockquote>
<p><strong>Theorem I am looking for:</strong> Let <span class="math-container">$R^* = R^*_1 \cup R^*_2$</span> be a partition of <span class="math-container">$R^*$</span>, and suppose that <span class="math-container">$x^*$</span> maximizes the LP over the subset of feasible points in which all constraints in <span class="math-container">$R^*_1$</span> are tight.  Then <span class="math-container">$x^*$</span> is an optimal solution to the LP if and only if <em>[some conditions hold that depend only on <span class="math-container">$R^*_2$</span>]</em>.</p>
</blockquote>
<p>Is a theorem statement of this form known, or is there anything morally related (such as [conditions] that depend on <span class="math-container">$R^*_1$</span> only in a relaxed or simplified way)?</p>

CC BY-SA 4.0
2023-06-27T11:36:07.257Z
This scenario arises with Lagrangian-relaxation (multiplicative-weights update) algorithms.  I believe the classical name for it is "surrogate duality".  Roughly, order the constraints in any order, then take the first $k$ constraints for some $k$ and relax these by removing them from the LP and replacing them by a single constraint that is a linear combination of them, with coefficients given by some vector $\mu\in\mathbb R^k$.  The theorem is that, for the best choice of $\mu$, this relaxed problem has the same value as the original problem (the relaxation gap is zero)...
Neal Young
CC BY-SA 4.0
2023-07-02T01:58:20.683Z
Maybe something like the "Duality Theorem" at the bottom of page 446 of https://leeds-faculty.colorado.edu/glover/fred%20pubs/60%20-%20surrogate%20-%20theory%20-%20OR%2075.pdf ?  (DOI: https://doi.org/10.1287/opre.23.3.434)
Neal Young
CC BY-SA 4.0
2023-07-02T15:16:28.037Z
Thanks Neal - this will take me a minute to parse, but at a glance it looks very helpful.
GMB
CC BY-SA 4.0
2023-07-03T22:03:27.107Z
No problem, let me know if you'd like to discuss more.
Neal Young
<linear-programming><primal-dual>
Verifying LP solutions using primal-dual hybrids
GMB
# Verifying LP solutions using primal-dual hybrids

(Asked by: username_0 on 2023-06-26)

We wish to solve an LP in the standard form

> Choose vector $x$ to maximize $c^T x$ subject to $Ax \le b$.

Let $x^\*$ be a feasible point. By LP duality, $x^\*$ solves the LP iff we can write the objective vector $c$ as a positive linear combination of the constraints that are tight at $x^\*$. Formally:

> **Theorem (LP Duality):** Let $R^\*$ be the set of row vectors $r\_i$ in $A$ for which $r\_i x^\* = b\_i$. Then $x^\*$ is an optimal solution to the LP if and only if $c^T \in \text{posspan}(R^\*)$.

I am looking for a relaxed version of this theorem statement, where we verify $x^\*$ by handling some constraints in $R^\*$ in a dual manner as above, and the rest in a primal manner. My ideal theorem statement looks something like the following:

> **Theorem I am looking for:** Let $R^\* = R^\*\_1 \cup R^\*\_2$ be a partition of $R^\*$, and suppose that $x^\*$ maximizes the LP over the subset of feasible points in which all constraints in $R^\*\_1$ are tight. Then $x^\*$ is an optimal solution to the LP if and only if *[some conditions hold that depend only on $R^\*\_2$]*.

Is a theorem statement of this form known, or is there anything morally related (such as [conditions] that depend on $R^\*\_1$ only in a relaxed or simplified way)?

**Tags:** linear-programming, primal-dual
> **Comments:**
> **username_1**: This scenario arises with Lagrangian-relaxation (multiplicative-weights update) algorithms.  I believe the classical name for it is "surrogate duality".  Roughly, order the constraints in any order, then take the first $k$ constraints for some $k$ and relax these by removing them from the LP and replacing them by a single constraint that is a linear combination of them, with coefficients given by some vector $\mu\in\mathbb R^k$.  The theorem is that, for the best choice of $\mu$, this relaxed problem has the same value as the original problem (the relaxation gap is zero)...  
> **username_1**: Maybe something like the "Duality Theorem" at the bottom of page 446 of https://leeds-faculty.colorado.edu/glover/fred%20pubs/60%20-%20surrogate%20-%20theory%20-%20OR%2075.pdf ?  (DOI: https://doi.org/10.1287/opre.23.3.434)  
> **username_0**: Thanks Neal - this will take me a minute to parse, but at a glance it looks very helpful.  
> **username_1**: No problem, let me know if you'd like to discuss more.  

---

## 0 answers

