Title: The discrete moment problem with nonconvex shape constraints,
Abstract: The discrete moment problem is a foundational problem in distribution-free
robust optimization, where the goal is to find a worst-case distribution that
satisfies a given set of moments. This paper studies the discrete moment
problems with additional "shape constraints" that guarantee the worst case
distribution is either log-concave or has an increasing failure rate. These
classes of shape constraints have not previously been studied in the
literature, in part due to their inherent nonconvexities. Nonetheless, these
classes of distributions are useful in practice. We characterize the structure
of optimal extreme point distributions by developing new results in reverse
convex optimization, a lesser-known tool previously employed in designing
global optimization algorithms. We are able to show, for example, that an
optimal extreme point solution to a moment problem with $m$ moments and
log-concave shape constraints is piecewise geometric with at most $m$ pieces.
Moreover, this structure allows us to design an exact algorithm for computing
optimal solutions in a low-dimensional space of parameters. Moreover, We
describe a computational approach to solving these low-dimensional problems,
including numerical results for a representative set of instances.