Maximizing a Sum of SigmoidsM. Udell, S. Boyd
Working draft.
The problem of maximizing a sum of sigmoidal functions over a convex constraint set arises in many application areas. This objective captures the idea of decreasing marginal returns to investment, and has applications in mathematical marketing, network bandwidth allocation, revenue optimization, optimal bidding, and lottery design. We define the sigmoidal programming problem and show how it arises in each of these application areas. We show that the general problem is NP-hard to approximate, and propose an approximation algorithm (using a branch and bound method) to find a globally optimal approximate solution to the problem. This algorithm has exponential worst-case complexity, but we show on a set of numerical examples that it often finds approximate solutions in reasonable time. To illustrate the power of this approach, we compute the optimal positions which might have allowed the candidates in the 2008 United States presidential election to maximize their vote shares. |