2013 Poster Sessions : Sigmoidal Programming

Student Name : Madeleine Udell
Advisor : Stephen Boyd
Research Areas: Information Systems
Abstract:
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 across operations research, including in mathematical marketing and auction bid optimization. After defining the general problem, we describe some of its mathematical properties, and then discuss various applications. We show that the general problem is NP-hard to approximate. We propose a branch and bound algorithm that finds a globally optimal approximate solution to the problem. This algorithm has (order-optimal) exponential worst-case complexity, and on problems of interest often delivers (provably) good approximate solutions in reasonable time.

Bio:
Madeleine Udell is a 4th year PhD student in Computational & Mathematical Engineering at Stanford University, working with Professor Stephen Boyd in Electrical Engineering. She completed her undergraduate studies at Yale University, with a degree in Mathematics and Physics. At Stanford, her research interests are driven by the framework of convex optimization and of graph theory, which provide powerful tools for formalizing objectives in statistics and machine learning. Most recently, she has developed a method to maximize a sum of sigmoidal functions, inspired by the venerable spatial theory of voting from political science.