Basic result in semi-infinite linear programming 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.
 A: 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
