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.



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


