News for hackers. Stuff that matters.

A comment on Solving a linear optimization problem on incentive allocation.

Re:Solving a linear optimization problem on incentive alloca... by s_Hogg on Wednesday October 23, 2019 @06:52AM (#21333264)
It's not the most accessible, but it's pretty interesting. Turning a problem into its dual has always been a bit of a dark art to me, but this article makes the benefits of doing so reasonably clear.
[ Parent | on HN ]
Re:Solving a linear optimization problem on incentive alloca... by benrbray on Wednesday October 23, 2019 @04:03PM (#21338366)
I really recommend Tim Roughgarden's notes for understanding duality!

* L7 (Intro): http://timroughgarden.org/w16/l/l7.pdf

* L8 (Duality I): http://timroughgarden.org/w16/l/l8.pdf

* L9 (Duality II: http://timroughgarden.org/w16/l/l9.pdf

[ Parent | on HN ]
Re:Solving a linear optimization problem on incentive alloca... by LolWolf on Wednesday October 23, 2019 @12:13PM (#21336071)
Turning a problem into a dual version is mostly a mechanical thing—you can immediately write it down in the case of LPs, for example[0], and many other convex cases [1].

——

[0] https://en.m.wikipedia.org/wiki/Dual_linear_program

[1] http://www.seas.ucla.edu/~vandenbe/236C/lectures/conj.pdf slide 23 on down.

[ Parent | on HN ]
Re:Solving a linear optimization problem on incentive alloca... by joker3 on Wednesday October 23, 2019 @12:45PM (#21336404)
The procedure is mechanical, but understanding why it works is quite a bit harder.
[ Parent | on HN ]
Re:Solving a linear optimization problem on incentive alloca... by LolWolf on Wednesday October 23, 2019 @12:50PM (#21336462)
Oh sure, I agree with that. For more context, I highly recommend chapter 5 in B&V.[0]

——

[0] http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page229

[ Parent | on HN ]