On optimizing a submodular utility function Part1

The Johns Hopkins University Applied Mathematics & Statistics Department Seminar series from Thursday September 21st 2017

by Alper Atamturk from Berkeley University

Title : On optimizing a submodular utility function

Abstract:
This talk has two related parts. Part one is on the maximization of a particular submodular utility function, whereas part two is on its minimization. Both problems arise naturally in combinatorial optimization with risk aversion, including estimation of project duration with stochastic task times, in reliability models, multinomial logit models, competitive facility location, combinatorial auctions, as well as in portfolio optimization.

Part 1: Given a monotone concave univariate function g, and two vectors c and d, we consider the discrete optimization problem of finding a vertex of a polytope maximizing the utility function c'x + g(d'x). The problem is NP-hard for any strictly concave function g even for simple polytopes, such as the uniform matroid, assignment and path polytopes. We give a 1/2-approximation algorithm for it and improvements for special cases, where g is the square root, log utility, negative exponential utility and multinomial logit probability function. In particular, for the square root function, the approximation ratio improves to 4/5. Although the worst case bounds are tight, computational experiments indicate that the approximation algorithm finds solutions within 1-2% optimality gap for most of the instances very quickly and can be considerably faster than the existing alternatives.

Part 2: We consider a mixed 0-1 conic quadratic optimization problem with indicator variables arising in mean-risk optimization. The indicator variables are often used to model non-convexities such as fixed charges or cardinality constraints. Observing that the problem reduces to a submodular function minimization for its binary restriction, we derive three classes of strong convex valid inequalities by lifting the polymatroid inequalities on the binary variables. Computational experiments demonstrate the effectiveness of the inequalities in strengthening the convex relaxations and, thereby, improving the solution times for mean-risk problems with fixed charges and cardinality constraints significantly.