
On the Hardness and Smoothed Complexity of Quasiconcave
Minimization
Jon Kelner & Evdokia Nikolova
Concave minimization is a fundamental problem in optimization. Quasiconcave
minimization is a generalization of the problem which retains the property
that the minimum is attained at an extreme point of the feasible set.
Despite this nice characterization of the minima, extreme points of the
feasible set are typically exponentially many and even minimizing a concave
quadratic function over the unit hypercube is NPhard. In addition no
efficient approximation algorithms exist to date, even for the class of
lowrank quasiconcave functions, whose nonconvexity lies in a lowdimensional
subspace. In this paper, we provide the first smoothed analysis of quasiconcave
minimization. The analysis is based on a smoothed bound for the number
of extreme points of the projection of the feasible polytope onto a kdimensional
subspace, where k is the rank (informally, the dimension of nonconvexity)
of the quasiconcave function. Our smoothed bound is polynomial in the
original dimension of the problem n, the perturbation size and
it is exponential in the rank of the function k. For lowrank functions
with constant k this implies an expected polynomial time algorithm
for quasiconcave minimization. We also prove (log n)hardness
of approximation of general quasiconcave minimization, which shows that
our smoothed bound is tight in a sense that no polynomial smoothed bound
is possible for quasiconcave functions of general rank k.

