<p>Yes, in some sense at least.  See the following paper: </p>

<p>Megiddo, Nimrod. "On finding primal-and dual-optimal bases." ORSA Journal on Computing 3.1 (1991): 63-65. PDF available <a href="http://theory.stanford.edu/~megiddo/pdf/bases.pdf" rel="nofollow">here</a>.</p>

<p>It shows that:</p>

<blockquote>
  <p>if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and
  the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for
  the general linear programming problem. </p>
</blockquote>

<p>(Note the details of the result though: it is about finding an optimal <strong>basis</strong> and deals with <strong>strongly</strong> polynomial-time algorithms.)</p>

CC BY-SA 3.0
2015-04-22T15:43:01.350Z
Looking at the paper more carefully, my impression is that the techniques in this paper can be used to give a *yes* answer to the OP's questions. But right now, I don't want to take the time to do it.
Peter Shor 
CC BY-SA 3.0
2015-04-21T17:12:30.483Z
2015-04-21T17:12:30.483Z
Rahul Savani
<p>Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions <a href="https://cstheory.stackexchange.com/questions/24892/intuitively-why-is-the-complementary-slackness-condition-true">[1]</a> can be used in non-degenerate cases to produce a dual optimum solution.</p>

<p>For instance, if we have an LP of the form $\max c^Tx, Ax\le b, x \ge 0$ with $m$ constraints and $n$ variables, and we are given a vertex optimum solution such that at least $m$ primal slack values and primal optimum coordinates are strictly positive, then it is easy to use Gaussian elimination to produce the optimum solution of the dual.</p>

<p>However, many degenerate cases can happen: an optimum vertex can be placed on many more constraints, or many variables can be set to 0, meaning that in such degenerate cases, complementary slackness does not seem to lead to a fast way of getting a dual optimum solution.</p>

<p>Is there an argument showing that the problem of computing any dual solution in such degenerate cases, while knowing the optimum, is equivalent (in complexity) to solving LP from scratch?</p>

<optimization><linear-programming>
Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?
M. B.
# Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?

(Asked by: username_0 on 2015-04-21)

Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [[1]](https://cstheory.stackexchange.com/questions/24892/intuitively-why-is-the-complementary-slackness-condition-true) can be used in non-degenerate cases to produce a dual optimum solution.

For instance, if we have an LP of the form $\max c^Tx, Ax\le b, x \ge 0$ with $m$ constraints and $n$ variables, and we are given a vertex optimum solution such that at least $m$ primal slack values and primal optimum coordinates are strictly positive, then it is easy to use Gaussian elimination to produce the optimum solution of the dual.

However, many degenerate cases can happen: an optimum vertex can be placed on many more constraints, or many variables can be set to 0, meaning that in such degenerate cases, complementary slackness does not seem to lead to a fast way of getting a dual optimum solution.

Is there an argument showing that the problem of computing any dual solution in such degenerate cases, while knowing the optimum, is equivalent (in complexity) to solving LP from scratch?

**Tags:** optimization, linear-programming


---

## 1 answers

### Answer by username_1 on 2015-04-21. Score: 2

Yes, in some sense at least. See the following paper:

Megiddo, Nimrod. "On finding primal-and dual-optimal bases." ORSA Journal on Computing 3.1 (1991): 63-65. PDF available [here](http://theory.stanford.edu/~megiddo/pdf/bases.pdf).

It shows that:

> if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and
> the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for
> the general linear programming problem.

(Note the details of the result though: it is about finding an optimal **basis** and deals with **strongly** polynomial-time algorithms.)

> **Comments:**
> **username_2**: Looking at the paper more carefully, my impression is that the techniques in this paper can be used to give a *yes* answer to the OP's questions. But right now, I don't want to take the time to do it.  

---

