3
$\begingroup$

I have the following problem: The functions $a_i(x) > 0$ and $b_i(x) > 0$ for $x\in I \subset \mathbb{R}$, $I$ compact, and $i=1,\ldots,n$ are given. The objective is to find functions $f_i(x)$ such that \begin{align} f_i(x) &\geq 0 \qquad \text{ for all $x$}\\ \sum_{i=1}^n f_i(x) &\leq 1 \qquad \text{ for all $x$}\\ \int_I f_i(x) \cdot a_i(x) \, dx &= 1 \qquad \text{ for all $i$}\\ \sum_{i=1}^n \int_I f_i(x) \cdot b_i(x) \, dx &\to \min \\ \end{align}

(None of the functions $a_i,b_i,f_i$ need to be continuous.) I know that a solution exists because I have a set of functions $\tilde{f}_i(x)$ satisfying the three constraints. My background in optimisation is close to negligible (am I right that the problem is convex?), which is why what would help me a lot is if you could (1) tell me if this problem is part of a larger well-studied class, possibly even with emough theory to derive the solution analytically and/or (2) point me in the right direction in terms of how to tackle the problem numerically.

If $n=1$ (only one function to find), the problem seems trivial, the basic idea being to start setting $f(x)=1$ in points $x$ where $b(x)$ is lowest, to continue doing so until the third constraint is reached, and to set $f(x)=0$ elsewhere (i.e. in points where $b(x)$ is high).

$\endgroup$
  • $\begingroup$ The problem is even linear, just infinite dimensional. If $f_i$ isn't continuous, you might want say from which space it is. Otherwise the integrals make no sense. $\endgroup$ – user251257 Feb 24 '17 at 1:11
  • $\begingroup$ The linearity is a very good point that I actually missed. As for the spaces, the functions $a_i, b_i, f_i$ are actually step-functions on $I$ (with constant values on grid cells that make up $I$), that's why I didn't even think of integrability when stating the problem. But let's say they and their products are all in $L^1$. Knowing that it's infinite dimensional linear convex, how would you go about solving it? Simply use a standard algorithm for convex linear programming and use it to find $f_i(x_j)$ on a number of points $x_j \in I$? Or is there a more efficient way? $\endgroup$ – user90855 Feb 24 '17 at 10:44
  • $\begingroup$ If the space isn't finite dimensional, your feasible set is liked not compact and thus guaranteeing a minimum is much more cumbersome. If you use a subspace of $L^1$ notice that point wise evaluation isn't continuous. You need to be more careful. $\endgroup$ – user251257 Feb 24 '17 at 10:48
  • $\begingroup$ Could you please tell where did you see this problem? Does it have any aplication ? $\endgroup$ – Red shoes May 25 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.