0
$\begingroup$

I am trying to understand the dual simplex method and after reading a few different books I got stuck when trying to understand the primal variable to dual constraint correspondence. A lot of sources simply state the following table as the definition of the dual problem:

  1. primal $x_j = 0$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} <> c_j$
  2. primal $x_j \geq 0$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} \leq c_j$
  3. primal $x_j \leq 0$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} \geq c_j$
  4. primal free variable $x_j$ corresponds to a dual constraint $\mathbf{a}^T_j \mathbf{y} = c_j.$

The $<>$ simply means the variable is unrestricted (aka free). I understand the derivation of the dual objective as the bound on the primal objective and where the constraints come from in the dual, but I'm struggling to see why the signs of the constraints change the way they do.

Can someone please help explain how to get a better intuition and understanding of the correspondence between primal variable types and the dual constraint types?

Thanks!

EDIT:

I decided to clarify the question based on the comments. Following the Lagrangian approach I decided to take a look at simple examples and see what their tightest dual bounds should be. Please see case 2 for an example of my wrong result.

  1. First scenario $$min\ x\\s.t.\ x = b.$$ Lagrangian is $$\mathcal{L} = x + \lambda (x - b)$$

Since $x = b,$ and $\mathcal{L} = b.$ No constraints on the $\lambda$ appear and it is a free variable.

  1. Second scenario: $$ min\ x\\ s.t.\ x \geq k. $$ Introduce slack variable $s \leq 0$ into $x \geq k$ to get $$ min\ x\\ s.t.\ x + s = k,\\ -s \geq 0 $$

This results in Lagrangian $$ \mathcal{L} = x + \lambda_1 (x + s -k) + \lambda_2 s = \\ \qquad = (1 + \lambda_1)x + s\lambda_1 - k\lambda_1 + s\lambda_2. $$

Again, $\frac{\partial\mathcal{L}}{\partial x} = 0 \rightarrow \lambda_1 = -1$.

This introduces a constraint on $\lambda_1 = -1$ and $\lambda_2$ is free.

This contradicts every single source I read on this subject so I am doing something wrong, but not sure what. Please advise.

  1. Third scenario: It's pretty much the same as above.

  2. Fourth scenario: (free x) $$min\ x\\s.t.\ x.$$ Lagrangian is $$\mathcal{L} = x + \lambda x = (1 + \lambda)x.$$ Minimum of the function is obtained when $1+\lambda=0$ so $\lambda=-1.$ We obtain the constant $c_j$ for the constraint.

$\endgroup$
  • $\begingroup$ Your notation is somewhat unclear- what exactly do you mean by (1) compared with (2), (3), and (4). In general, you can prove these by starting with a single primal-dual pair and then using the rules of algebra to turn other primal forms into the standard primal. It's a good exercise. $\endgroup$ – Brian Borchers Aug 15 '18 at 3:20
  • $\begingroup$ If $<>$ denotes $\neq$ then the "dual constraint" in 1. is not linear... $\endgroup$ – Math1000 Aug 15 '18 at 4:02
  • 1
    $\begingroup$ The most important part is to write the Lagrangian so that it provides an appropriate bound (lower/upper depending on whether you are minimizing/maximizing) and then everything pops out automatically and you never ever have to remember the signs, rules, etc. and you have no chance of making a mistake. For a brief exposition with examples see docs.mosek.com/modeling-cookbook/… $\endgroup$ – Michal Adamaszek Aug 15 '18 at 7:23
  • $\begingroup$ Thanks for your comments. I looked at the Mosek documents provided by @MichalAdamaszek and they were useful. I also provided some reasoning in the updated post and clarified the notation. I am still getting the wrong result in case of scenario 2 and 3. Please advise what I'm doing wrong. $\endgroup$ – M B Aug 15 '18 at 23:36
  • $\begingroup$ In your second scenario $\lambda_2$ is not free because you forgot to include the partial derivative over $s$. $\endgroup$ – Michal Adamaszek Aug 16 '18 at 6:56

Your Answer

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

Browse other questions tagged or ask your own question.