4
$\begingroup$

I am new to Optimization so I think the following question may be very easy, but I'm not sure how to solve it.

The dual of an LP is an LP. If we solve the dual LP, we can get the optimal value for the primal problem. But:

  1. How do we get the optimal decision variables for the primal?

  2. Does it make a difference if we only relax some of the constraints?

My Work for Finding Dual of LP

\begin{align*} &\text{min } &c^Tx \\ &\text{s.t. } &Ax = b \\ &&Bx \le d \\ \end{align*}

We form the Lagrangian ($\mu \ge 0$): \begin{align*} L(x, \lambda, \mu) &= c^Tx + \lambda^T (Ax - b) + \mu^T (Bx - d) \\ &= (c + A^T \lambda + B^T \mu)^Tx - \lambda^Tb - \mu^Td \end{align*}

Thus we see that the dual function is $$d(\lambda, \mu) = \inf_x L(x, \lambda, \mu) = \begin{cases} - \lambda^Tb - \mu^Td \ \ \ &\text{if } \ \ \ c + A^T \lambda + B^T \mu = 0 \\ - \infty & \text{otherwise} \end{cases}$$ and therefore the dual problem is \begin{align*} &\text{max } &-\lambda^Tb - \mu^Td \\ &\text{s.t. } &c + A^T \lambda + B^T \mu = 0\\ \end{align*}

$\endgroup$
4
  • $\begingroup$ @Rob Thanks for the suggestion. Your link answers the question of how to find the dual; but I know how to do this, as I demonstrated in the OP. My question is about how to deduce the primal solution from the dual solution. $\endgroup$
    – Helix
    Aug 23, 2022 at 15:28
  • $\begingroup$ Please note that there are some answers here: stackexchange.com/… - and you are allowed to answer your own question. $\endgroup$
    – Rob
    Aug 23, 2022 at 17:09
  • $\begingroup$ Cross-posted: math.stackexchange.com/questions/4517235/… $\endgroup$
    – RobPratt
    Aug 24, 2022 at 3:15
  • $\begingroup$ @Helix Please, consider that the dual problem actually is \begin{align*} &\text{max } &\lambda^Tb - \mu^Td \\ &\text{s.t. } & A^T \lambda + B^T \mu - c \le 0\\ \end{align*} $\endgroup$ Jan 3 at 11:33

3 Answers 3

6
$\begingroup$

The duals or shadow prices of the dual model give you a primal solution. See http://yetanothermathprogrammingconsultant.blogspot.com/2022/08/primal-dual-and-equilibrium-format-of.html for a simple example.

$\endgroup$
2
  • $\begingroup$ Is this your website? If so, that should be disclosed. (kudos to you if it is yours, looks good!) $\endgroup$ Aug 23, 2022 at 22:55
  • 5
    $\begingroup$ Clearly, this is a website of Erwin and that is not hidden. See his SE profile. $\endgroup$ Aug 24, 2022 at 9:17
2
$\begingroup$

an intuitive transformation

I'm also interested in this problem. I think the transformation between the dual solution and the primal solution must be related to KKT conditions, so I give my intuitive solution.

$\endgroup$
1
0
$\begingroup$

If in primal problem the variable $\mathbf x$ was a vector of dimension $n$ and constraints were made of $m+p$ equations, in dual problem we should have $n$ equations in $m+p$ variables. It is common practice to solve the dual problem especially when its resolution is easier and quicker than the primary problem: it is the case when $ m+p > n $ and Rocuhe-Capelli theorem holds so that there are more than one single solution.

At the optimum, the equality of the values of the objective functions in primal and dual problems holds, so that it is possible to evaluate the quality of an admissible point in the primal problem without having to solve the last one exactly.

In order to assess the goodness of an admissible point under examination $\mathbf x'$ we can simply compare the value $f(\mathbf x')=\sum_{i=1}^n c_i x'_i $ with $f(\mathbf x^*)$, where $f(\mathbf x^*)$ is equal to the optimal value of the objective function of the dual: $f(\mathbf x^*)=h(\mathbf y^*)$.

In a minimum cost problem if it turns out that $ 0 < f(\mathbf x') - f(\mathbf x^*) \leq \varepsilon $, then we could be content with approximating $\mathbf x^*$ with $\mathbf x'$ confident in the fact that the additional cost to be incurred for choosing a sub-optimal solution $\mathbf x'$ is certainly not greater than $\varepsilon$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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