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.

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

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

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.

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. "Distributed stochastic optimization via correlated scheduling," IEEE Transactions on Networking.

http://ee.usc.edu/stochastic-nets/docs/distributed-optimization-ton.pdf

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.

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.

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