Solving a linear optimization problem on incentive allocation
1–10 of 24 posts
Re: Solving a linear optimization problem on incentive allocation
#2It'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.
Re: Solving a linear optimization problem on incentive allocation
#3It'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.
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.
Re: Solving a linear optimization problem on incentive allocation
#4It'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.
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.
The procedure is mechanical, but understanding why it works is quite a bit harder.
Re: Solving a linear optimization problem on incentive allocation
#5Earlier quoted context omitted.
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.
The procedure is mechanical, but understanding why it works is quite a bit harder.
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
Re: Solving a linear optimization problem on incentive allocation
#6Isn't this a textbook assignment problem? https://en.wikipedia.org/wiki/Assignment_problem
Re: Solving a linear optimization problem on incentive allocation
#7Since their budget is much larger than each individual incentive, isn't the greedy solution within epsilon of the optimal assignment? I.e. sort by v/c descending and take while sum(c) < B.
Re: Solving a linear optimization problem on incentive allocation
#8Since their budget is much larger than each individual incentive, isn't the greedy solution within epsilon of the optimal assignment? I.e. sort by v/c descending and take while sum(c) < B.
Given there are no overlapping subproblems, I think greedy is optimal[1]. The point was to show primal I(L)P with dual decomposition.
1. You're right, a counter example for greedy (with 2 appox) looks something like: c1=.5+eps, v1=1, c2=.5, v2=.5+eps, B=2.
Re: Solving a linear optimization problem on incentive allocation
#9Not very interesting. You see allocation problems solved all of the time in finance, and this blog post doesn't have anything new.
I also doubt that it's optimal. An implementation using Hierarchical Risk Parity for instance would be more interesting. I assume you can model risk/uncertainty here.
By the way, Google has an OR tools framework that implements these kind of solvers for you:
Re: Solving a linear optimization problem on incentive allocation
#10Not very interesting. You see allocation problems solved all of the time in finance, and this blog post doesn't have anything new. I also doubt that it's optimal. An implementation using Hierarchical Risk Parity for instance would be more interesting. I assume you can model risk/uncertainty here. By the way, Google has an OR tools framework that implements these kind of solvers for you: https://developers.google.com/…
Uninteresting comment. You see critical, speculative comments that offer no technical insight on Hacker News all the time. I also doubt the article was read. Demonstrating actual effort and understanding would be more interesting.