Convex Optimization · Problem 7.13

Geometric problems — Boyd & Vandenberghe

Mathematics — Optimization · chebyshev-inequalities-finite-set

Problem

Chebyshev-type inequalities on a finite set. Assume

X

is a random variable taking values in the set

\{\alpha_1, \alpha_2, \ldots, \alpha_m\}

, and let

S

be a subset of

\{\alpha_1, \ldots, \alpha_m\}

. The distribution of

X

is unknown, but we are given the expected values of

n

functions

f_i

\mathbf{E}\, f_i(X) = b_i, \quad i = 1, \ldots, n. \tag{7.32}

Show that the optimal value of the LP

\begin{aligned} \text{minimize} & \quad x_0 + \sum_{i=1}^n b_i x_i \\ \text{subject to} & \quad x_0 + \sum_{i=1}^n f_i(\alpha) x_i \geq 1, \quad \alpha \in S \\ & \quad x_0 + \sum_{i=1}^n f_i(\alpha) x_i \geq 0, \quad \alpha \notin S, \end{aligned}

with variables

x_0, \ldots, x_n

, is an upper bound on

\mathbf{prob}(X \in S)

, valid for all distributions that satisfy (7.32). Show that there always exists a distribution that achieves the upper bound.