I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the convex space is piecewise curved -- that is, it has faces, edges, and vertices, but the edges aren't straight and the faces aren't flat. Instead of being specified by a finite number of linear inequalities, I have a continuously infinite number. I'm interested in estimating solutions numerically, and my current method is to approximate the surface by a polytope, which means discretizing the continuously infinite number of constraints into a very large finite number of constraints. Unfortunately, typical linear programming algorithms run in something like cubic-time in the number of constraints, so I'm getting a huge performance hit as I make the discretization finer. Firstly, I'm interested to know if this kind of problem has been studied before, and what's been done. Secondly, I'm looking for good strategies for approaching my problem numerically (good LP packages, suggested algorithms, optimizations, etc.).

For concreteness, here is a simplified version of the problem I'm trying to solve:

I have $N$ fixed functions $f_i:[0,\infty]\to \mathbb{R}$. I want to find $x_i$ $(i=1,\dots,N)$ that minimize $\sum_{i=1}^N x_i f_i(0)$, subject to the constraints:

$\sum_{i=1}^N x_i f_i(1) = 1$, and

$\sum_{i=1}^N x_i f_i(y) \geq 0$ for all $y>2$

More succinctly, if we define the function $F(y)=\sum_{i=1}^N x_i f_i(y)$, then I want to minimize $F(0)$ subject to the condition that $F(1)=1$, and $F(y)$ is positive on the entire interval $[2,\infty)$. Note that this latter positivity condition is really an infinite number of linear constraints on the $x_i$'s, one for each $y$. A specific $y_0$ restricts me to the half-space $F(y_0) \geq 0$ in the space of $x_i$'s. As I vary $y_0$ between 2 and infinity, these half-spaces change continuously, carving out a curved convex shape. The geometry of this shape depends implicitly (and in a complicated way) on the functions $f_i$.

The reason I suspect there should be an approach that's better than just discretizing the number of constraints is that continuity of the $f_i$'s implies a kind of local structure on the space of constraints that becomes invisible under discretization. If we sit on the boundary of our convex space (so that at least N constraints are saturated, corresponding to some $y_k$), and we want to move along the boundary, then generically only those constraints corresponding to small neighborhoods of the $y_k$ are important. Sometimes when the function $F(y)$ develops a new zero, new $y$ can become important, but this is nongeneric.

NOTE: I asked this question first on stackoverflow.net, and was told it was a nonstandard enough CS problem that I should ask about it here.