Discretising variational problems through linear programming

50 Views Asked by At

Suppose we have the following variational problem. Given $\mu>1$ and the function $g \in C[0,1]$,

$$ \begin{array}{ll} \underset{f \in C[0,1]}{\text{maximize}} & \overbrace{\displaystyle\int_0^1 x f(x) \, {\rm d} x}^{=: I(f)} \\ \text{subject to} & \displaystyle\int_0^1f(x) \, {\rm d} x = 1 \\ & 0 \leq f(x)\leq \mu g(x), \quad \forall x\in[0,1] \end{array} $$

If we write the integrals as Riemann sums, discretised with equal steps $1/n$ the interval $[0,1]$, we can see that the problem can be seen as maximising over all $f\in C[0,1]$ the limiting problem, as $n$ goes to infinity, $\sum_{i=1}^n\frac{i}{n^2}f(i/n)$ constrained on $\sum_{i=1}^n\frac{f(i/n)}{n}=1$ and $0\leq f(x)\leq \mu g(x)$.

Let us now swap the limit with the maximisation, that is, let us consider a linear program defined as follows: let $y_i$ replace $f(i/n)$, and maximise, over all coordinates $(y_1,\ldots,y_n)$, $\sum_{i=1}^n\frac{i}{n^2}y_i$ constrained on $\sum_{i=1}^n\frac{y_i}{n}=1$ and $0\leq y_i\leq \mu g(i/n)$ for all $1\leq i\leq n$. Assume that the solution exists and denote it as $y^n$.

I am curious about the following:

  1. Intuitively, since we discretised the variational problem, as $n$ grows large we would expect that the linear program yields an approximation of the maximal value $I^*$ of the original objective. Is it true, under mild assumptions, that as $n$ tends to infinity, the value yielded by the solution of the linear program, say $I^n$, tends to $I^*$? If yes, how does one prove so?

  2. Say that $I^*$ is yielded by some functions. Is it true that the step function corresponding to the values of the coordinates of the vector $y^n$, which maximises the linear program, tends to one of these functions as $n$ tends to infinity?

The problem above is just a toy example. Essentially, the question is if discretising a simple variational problem yields solutions of the original problem, under mild assumptions. It is essentially a question about exchanging the order of the maximisation over functions and the limit of the discretisation.