Skip to main content
4 of 6
deleted 5 characters in body

How to solve an optimization problem whose optimization variable is a function?

My opimization problem is related to finding an optimal probability density function (PDF) $f$ to minimize the following objective.

$$ \begin{array}{ll} \underset {f} {\text{minimize}} & C \\ \text{subject to} & 1 + \frac{b\cdot\int_{0}^{x}f(t)dt}{x} \leq C, \text{ for any } x \in [0,\infty) \\ & \quad\frac{\int_{0}^{x}(t+b)\cdot f(t)dt+x\cdot\int_{x}^{\infty}f(t)dt}{b}\leq C, \text{ for any }x\in(b,\infty) \\ & \int_{0}^{\infty}f(t)dt=1\end{array} $$

where $b$ is a known constant.

I want to find the optimal PDF to minimize $C$, but do not know how to solve it. Are there any systematic ways or general ideas of dealing with such a functional optimization problem?

$\textbf{My idea:}$
Here I can introduce another optimization variable $B\geq b$ such that the probability density is restricted within the range of $[0,B]$, i.e. $\int_{0}^{B}f(t)dt=1$. Then the original optimization problem can be rewritten as

$\min\limits_{B,f(t)} C$

s.t. $1+\frac{b\cdot\int_{0}^{x}f(t)dt}{x}\leq C, \text{ for any }x\in[0,B]$

$\quad\frac{\int_{0}^{x}(t+b)\cdot f(t)dt+x\cdot\int_{x}^{B}f(t)dt}{b}\leq C, \text{ for any }x\in(b,B]$

$\quad\int_{0}^{B}f(t)dt=1$,

$\quad B\geq b$

We take a look at the second constraint $\frac{\int_{0}^{x}(t+b)\cdot f(t)dt+x\cdot\int_{x}^{B}f(t)dt}{b}\leq C$. Taking the derivative of the left hand side with respect to x, we find that its derivative is $f(x)\geq 0$, which implies that the left hand side is non-decreasing with respect to $x\in (b,B]$. Hence the second constraint can be reduced to $1+\frac{\int_{0}^{B}t\cdot f(t)dt}{b}\leq C$ (by taking $x=B$). Hence the optimization problem can be rewritten as

$\min\limits_{B,f(t)} C$

s.t. $1+\frac{b\cdot\int_{0}^{x}f(t)dt}{x}\leq C, \text{ for any }x\in[0,B]$

$\quad 1+\frac{\int_{0}^{B}t\cdot f(t)dt}{b}\leq C$

$\quad\int_{0}^{B}f(t)dt=1$,

$\quad B\geq b$

$\textbf{The reason why I have this optimization problem:}$ The reason why I have this optimization problem is that I am trying to solve a cost optimization problem for a distributed storage system, constant $b$ here is the cost of transferring the data object among different servers. $f(t)$ here is the pdf of the storage duration of the data copy in a server (and storage cost is proportional to the storage duration, here we assume that the storage cost rate is 1 per unit of time), and after time $t$ the data will be dropped in the server so that there will be no storage cost anymore for our server. So our algorithm is something like a randomized online algorithm, whose target is to find the optimal pdf $f(t)$ to minimized the overall cost of storing and transferring data in the system. Through some simplifications of my modelling, I finally derive this functional optimization problem, but do not know what to do next.

This problem has infinitely many constraints (i.e., for each continuous value $x\in [0,\infty)$, we have constraints like the first and the second constraint), and this is the mainly obstacle of solving this optimization problem.

Erik
  • 21
  • 2