Optimization over subsets of $\mathbb{R}$

Question

I have a problem which has the form $$ \begin{align*} \min_{\mathcal{A}} \quad & \int_\mathcal{A} f(x)\; dx \\ \text{s.t.} \quad & \int_\mathcal{A} g(x)\; dx = C \\ & \mathcal{A} \subseteq [a, b] \\ & f, g \text{ integrable over } [a,b] \end{align*} $$

This is clearly an equality-constrained infinite-dimensional problem, but I'm wondering how to describe it more precisely -- I tried searching "uncountable set optimization", "optimization over subsets of R", etc. but I couldn't find any relevant literature. Would appreciate if someone can point me in the right direction.

Answer 1

Indeed, the optimal set is usually of the form $A = \{x : f(x) < \kappa g(x)\}$, where $\kappa$ is chosen so that $\int_A g = C$. The problem here is that if $f/g$ is flat on positive-measure subsets, such a $\kappa$ may not exist. To handle this problem, we define things in the following way: \begin{align*} \kappa^* = \sup\Bigl\{\kappa : \int_{\{f < \kappa g\}} g \leq C\Bigr\}, \\ \end{align*} then, if $\mu(\{x : f(x) < \kappa^* g(x)\}) < C$ (for $\mu$ the Lebesgue measure), the optimal $A$ is not unique, and we define \begin{align*} A^* = \{x : f(x) < \kappa^* g(x)\} \cup D^*, \end{align*} where $D^* \subseteq \{x : f(x) = \kappa^* g(x)\}$ is any set that satisfies \begin{align*} \int_{D^*} g = C - \mu(\{x : f(x) < \kappa^* g(x)\}), \end{align*} (which is guaranteed to exist since the measure defined by integration against $g$ is absolutely continuous). Now, we have that $\int_{A^*} g = C$.

To see that any such $A^*$ is optimal, let $B$ be another set such that $\int_B g = C$. In particular, $f \leq \kappa^* g$ on $A^*$ and $f \geq \kappa^* g$ on $(A^*)^c$. This allows us to compute \begin{align*} \int_{A^*} f - \int_B f = \int_{A^*\setminus B} f - \int_{B\setminus A} f \leq \int_{A^*\setminus B} \kappa^* g - \int_{B\setminus A^*} \kappa^* g = \kappa \Bigl[\int_A^* g - \int_B g\Bigr] = 0, \end{align*} so that the objective is indeed minimised at $A^*$

Answer 2

This is a draft proof (I am not strong on integration theory, and it's already 1 a.m here) that $\mathcal{A}$ is the pre-image by $\frac f g$ of some $]-\infty, M]$. It can be refined, notably on the hypotheses which are stronger than necessary.

Assume $\mathcal{A}$ can be any union of closed intervals in $[a,b]$.
Suppose $f$ and $g$ are continuous, and $g$ is never null. We then define $h =\frac f g$.
(If $g$ has null values but not $f$, the same reasoning can be done with $\frac g f$).

Then $\exists M$ such that $\min_{\mathcal{A}} \int_\mathcal{A} f(x) dx$ with $\int_\mathcal{A} f(x) dx = C$
is attained for $\mathcal{A} = h^{-1}(]-\infty, M])$.

Proof by contradiction: suppose $\mathcal{B}$ is not of the form $h^{-1}(]-\infty, M])$.
Call $N=\max_{x \in \mathcal{B}}\; h(x)$. Then, $h$ being continuous:
$\exists [c_1, c_2] \subset \mathcal{B},\quad \exists [d_1, d_2], \; [d_1,d_2] \cap \mathcal{B} = \emptyset,$
$\forall x \in [c_1,c_2], \forall y \in [d_1, d_2], h(y) < h(x) < N$.

Then define $\mathcal{D} = \mathcal{B}$ plus some part of $[d_1, d_2]$ minus some part of [c_1, c_2], such that $\int_\mathcal{D} g(x) dx = \int_\mathcal{B} g(x) dx = C$ and
$\int_\mathcal{D} f(x) dx < \int_\mathcal{B} f(x) dx$
This is possible because $\frac {f(x)} {g(x)}$ is lower in $[d_1, d_2]$ than in $[c_1, c_2]$.

Notes:

• Numerical resolution is then linear in $M$ and can be done e.g. by dichotomy.
• This reminds of the knapsack optimization problem; where choosing objects that minimize the weight/value ratio is a good heuristics. However it is only an heuristics because each object can only be taken entirely or not at all, and the knapsack has a weight limit. Here however, by using integrals, we are in a perfect case, so the heuristics is optimal.
• If $\mathcal{A}$ is restricted to be an interval (my question in comments) $[c,d]$, the same kind of argument can probably be used to show that $\frac {f(c)} {g(c)} = \frac {f(d)} {g(d)}$ (assuming $f$ and $g$ continuous). The numerical resolution is then also linear in this value of $\frac {f(c)} {g(c)}$, although there can be a combinatorial explosion if the number of level sets for $\frac f g$ is high, or worse, infinite. So restricting $\mathcal{A}$ to be an interval is actually more difficult.