0
$\begingroup$

Similar "help me solve this"-question has been asked dosens of time here. The closest things I was able to google is this post that says that "the last part is complicated". There are plenty of examples on the web, that are like "because where we have that, we can use the following trick" but I could not find any algebraic formula, or a system of equations, or a general algorithm for finding a solution of a primal problem given a solution of a dual. To be more concrete:

$$ \min c^T x \quad \text{s.t. } Ax-b=0, x\geq 0$$ and its dual $$ \max b^T y \quad \text{s.t. } c-A^Ty - s = 0, s \geq 0$$

That is clear that given the optimal $(y*, s*)$:

  1. $c^T x = b^T y^*$
  2. $x_i s_i = 0 $

Thank you!

but we need more and I can not find the general

$\endgroup$
1
$\begingroup$

We'll use what's called the Complementary Slackness Theorem, from here.

Theorem. Suppose a primal linear programming problem $\mathcal{P}$ and its dual $\mathcal{D}$ have solutions $x^*$ and $y^*$ respectively.

  • If $x^*_j > 0$, then the $j$-th constraint of $\mathcal{D}$ is binding.
  • If the $i$-th constraint of $\mathcal{P}$ is not binding, i.e. the equality does not hold, then $y^*_i = 0$.

Equivalent statements follow from contraposition.

If you want to use the theorem, then you'll first need to use your dual solution to determine which dual constraints are not binding. Those tell you which primal variables are zero. Use that information, and the fact that binding dual constraints correspond to positive primal variables. It will amount to solving a system of equations.

$\endgroup$
  • $\begingroup$ Thank you! Right, but isn't it same as "2." in the question body? What is gives us is: 1) $c^t x = C$, where $C$ is some constant + 2) information on which components of $x$ are greater then zero from dual slack variables. That does not seem to be enough to uniquely identify $x$, right? $\endgroup$ – Ben Usman Jul 13 '17 at 6:21
  • $\begingroup$ Ah! I guess I got it! We can additionally use $Ax=b$ - should it be enough now? And if it wasn't equality, but inequality, we would take rows from this inequality that correspond to $y_j \neq 0$, right? $\endgroup$ – Ben Usman Jul 13 '17 at 6:25
  • $\begingroup$ Would it be enough now? I mean, if we have just $k$ equality constraints on $x$ of dim $n$ ($A$ is $k \times n$), +1 equality from dual=primal, and assume that only $m$ of $n$ slack variables $s_j$ turn out to be zero, so we have to estimate $n-m$ values, then what if $k+1 < n-m$? $\endgroup$ – Ben Usman Jul 13 '17 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.