0

I have the question regarding the expression of the dual formulation of a linear program. I think it is very simple but I just dont get (1) below

$ \min \ c^Tx \\ \text{s.t.} \ \ Ax \le b $

$L(x,\lambda) = c^Tx + \lambda(Ax-b)$

$g(\lambda) = \inf_x ((c + A^T\lambda)^Tx - b^T\lambda) \\ = -b^T\lambda \ \ \text{if} \ \ A^T\lambda + c = 0 \\ = -\infty \ \ \ \ \text{otherwise} $

It is said that $ g(\lambda) \le c^Tx$.

(1) Why is $-b^T\lambda \le c^Tx$ ?

Kong
  • 884
  • @amWhy Kong visited this website multiple times but hadn't provided feedback on my answer. I left this community for close to a year due to questioners with (imo) poor manners. And you know what? If I can't raise that issue without being called out, I'm waving goodbye again. – LinAlg Mar 21 '18 at 01:06
  • 2
    @LinAlg I understand the frustration. Believe me, I've experienced the same. The best thing to do when dealing with users, like kong, with bad manners is refuse to answer any more of their questions. I wouldn't leave again, though I have felt (and frequently feel) the need to wave goodby, too. But, inevitably I come back. Don't let one rude asker (or a number of them) determine whether you stay or go. That's giving such a user too much power. I will now delete my comment. Thanks for responding. – amWhy Mar 21 '18 at 01:10
  • 2
    Another suggestion is avoiding mere problem statement question with no effort by the asker. Those are the askers that are most likely to ask, get the answer to complete their homework, and run. Some times, though, it's a tough call. – amWhy Mar 21 '18 at 01:14

1 Answers1

2

This is a standard proof for weak duality.

Multiply the constraints in the primal by $\lambda$ (to $\lambda^T Ax \leq b^T \lambda$) and in the dual by $x$ (to $\lambda^TAx + c^T x = 0$) to get $-c^Tx \leq b^T \lambda$.

amWhy
  • 209,954
LinAlg
  • 19,822