Basic result in semi-infinite linear programming

Question

Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if this linear program is feasible, then there exists an optimal solution $x^*$ with at most $m$ nonzero entries. My question is: is there a good standard reference that says that the same result holds when $x$ is infinite-dimensional (but we still have only $m$ constraints)? More specifically, say that I'm looking for a measure (Borel, Radon, Lebesgue, whatever is most convenient) $P$ on (say) the unit interval $[0,1]$, and I'd like to find the measure that solves $$\textrm{minimize}_P ~~~~\int_{[0,1]} f ~\mathrm{d}P~~~~ s.t. \\ \int_{[0,1]} g_i ~\mathrm{d}P \leq b_i, i\in \{1,\dots,m\} $$ where $f$ and all $g_i$ are continuous functions. It seems that under most conditions, there should exist an optimal measure $P^*$ that is finite, consisting of at most $m$ points.

Answer 1

The answer is "$m+1$," not "$m$." A generalization of the problem you describe is to find a random vector $X \in \mathcal{X}$, where $\mathcal{X}$ is some multi-dimensional set, to solve:

Problem 1: \begin{align} \mbox{Minimize: } \: \: & E[f(X)] \\ \mbox{Subject to: } \: \: & E[g_i(X)] \leq b_i \: \: \forall i \in \{1, \ldots, m\} \\ & X \in \mathcal{X} \end{align}

An online variation is to find a sequence of random vectors $\{X(0), X(1), X(2), \ldots\}$ to solve:

Problem 2: \begin{align} \mbox{Minimize: } \: \: & \limsup_{t\rightarrow\infty} \frac{1}{t}\sum_{\tau=0}^{t-1} E[f(X(\tau))] \\ \mbox{Subject to: }\: \: & \limsup_{t\rightarrow\infty} \frac{1}{t}\sum_{\tau=0}^{t-1}E[g_i(X(\tau))] \leq b_i \: \: \forall i \in \{1, \ldots, m\} \\ & X(\tau) \in \mathcal{X} \: \: \forall \tau \in \{0, 1, 2,\ldots\} \end{align}

Under mild conditions, optimality is described in the same way for both problems (the only technical issues are minor boundedness and closure type issues). Define the following set: $$ \mathcal{R} = \{(f(x), g_1(x), \ldots, g_m(x)) : x \in \mathcal{X}\} $$ For simplicity assume the set $\mathcal{R}$ is closed and bounded. Define $Conv(\mathcal{R})$ as the convex hull of $\mathcal{R}$ (this is a closed, bounded, and convex set). The problems 1 and 2 are feasible with infimum objective function value $f^*$ if and only if the following problem is feasible with the same minimum objective function value:

Problem 3: \begin{align} \mbox{Minimize: } \: \: & y_0\\ \mbox{Subject to:} \: \: & y_i \leq b_i \: \: \forall i \in \{1, \ldots, m\} \\ \: \: & (y_0, \ldots, y_m) \in Conv(\mathcal{R}) \end{align}

Now assume problem 3 is feasible and let $(y_0^*, \ldots, y_m^*)$ be an optimal solution (such exists by compactness). This is a vector in $Conv(\mathcal{R})$ in $m+1$ dimensional space and hence can be achieved as a convex combination of at most $m+2$ points in $Conv(\mathcal{R})$ (by Caratheodory's theorem). However, it can be shown this vector is on the boundary of $Conv(\mathcal{R})$, and a simple extension of Caratheodory shows it can thus be achieved as a convex combination of at most $m+1$ points.

---

The bound $m+1$ is "tight." An example is a problem with $m=1$ constraint such as this: Let $\mathcal{X} = \{0,1\}$ (consisting of two points). Define $f(x) = x$, $g(x) = -x$. We want to solve: \begin{align} \mbox{Minimize: } \: \: & E[X] \\ \mbox{Subject to: } \: \: & E[-X] \leq -0.5\\ \: \: & X \in \{0, 1\} \end{align} The optimal solution is to allocate according to a random vector with $Pr[X=0]=Pr[X=1]=1/2$. There is $1$ constraint ($m=1$), and here we need a solution with $1+1=2$ points of support.

A similar $m+1$ example can be made with the connected set $\mathcal{X} = [0,1]$ and the continuous functions $g(x)=-x$, $f(x) = \sqrt{x}$. In this case, we have $\mathcal{R} = \{(-x, \sqrt{x}) : x \in [0,1]\}$ and we again need to average over $m+1=2$ extreme points.

---

I have worked a lot with "Problem 2" type problems in stochastic optimization, where the "drift-plus-penalty" algorithm is a nice solver for these problems as well as more complex ones with random state changes. I feel awkward giving two "self-references" but these are directly related to what I describe above:

1) This develops the performance region $Conv(\mathcal{R})$ I allude to above, and gives online solvers:

"Stochastic Network Optimization with Application to Communication and Queueing Systems," Morgan & Claypool, 2010.
http://www.morganclaypool.com/doi/abs/10.2200/S00271ED1V01Y201006CNT007

2) This paper uses the $m+1$ observation, and the footnote on page 13 is the same as my comment above about generalizing Caratheodory's theorem.

"Distributed stochastic optimization via correlated scheduling," IEEE Transactions on Networking.
http://ee.usc.edu/stochastic-nets/docs/distributed-optimization-ton.pdf