4
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ For intuition on why the stochastic problem gives $m+1$ while the LP gives $m$, notice that the LP has no constraint of the form $\sum_i x_i = 1$, while the stochastic problem implicitly has such a constraint since we must allocate according to a valid probability distribution. So, one perspective is to view this as one additional constraint. $\endgroup$
    – Michael
    Jul 12, 2015 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.