1
$\begingroup$

This cropped up in a research question I'm tackling. I wish to solve the following optimization problem: $$ \text{minimize}\ \sum_{i=1}^\infty f_i \sum_{j=1}^i \sqrt{f_j} \quad\text{subject to}\ \sum_{i=1}^\infty f_i=1\ \text{and}\ f_i \in [0,1]\ \forall i. $$

My attempt was to apply calculus of variation, and adding the normalization constraint with a Lagrange multiplier: $$ S_\lambda := \sum_{i=1}^\infty f_i \sum_{j=1}^i \sqrt{f_j} + \lambda\left(1-\sum_{i=1}^\infty f_i \right) $$ and then vary $$ \frac{\delta S_\lambda}{\delta f_a} = \sum_{j=1}^a \sqrt{f_j} + \frac12 \frac{1}{\sqrt{f_a}} \sum_{i=a}^\infty f_i -\lambda \overset!= 0 \quad\forall a $$ (My first question is: can I even apply calculus of variation in this setting? And, if so, is the expression above correct? I asked a colleague to check who couldn't find any mistake, but you know how it is sometimes.)

Under the assumption that the variation is correct, I then solved the first and last equation via \begin{align} 0= \frac{\delta S_\lambda}{\delta f_1} &= \sqrt{f_1} + \frac12 \frac{1}{\sqrt{f_1}}\underbrace{\sum_{i=1}^\infty f_i}_{=1} - \lambda &\Rightarrow\quad \lambda &= \frac{1+2f_1}{2 \sqrt{f_1}} \\ 0= \lim_{a\rightarrow\infty} \frac{\delta S_\lambda}{\delta f_a} &= - \lambda + \underbrace{\lim_{a\rightarrow\infty} \sum_{i=1}^a \sqrt{f_i}}_{=:A_\infty} + \frac12 \underbrace{\lim_{a\rightarrow\infty}\frac{1}{\sqrt{f_a}} \sum_{i=a}^\infty f_i}_{=:B_\infty} &\Rightarrow\quad \lambda&=A_\infty + B_\infty \end{align} As by the first line we have that $\lambda$ is finite, both limits must exist. The first sum converges when $f_i = o(1/i^2)$, in which case $B_\infty=0$ and $\lambda = A_\infty$.

But how to proceed? I don't see a good way of e.g. solving this set of equations recursively.

I'd be grateful for any pointers!

Improve this question
$\endgroup$
12
  • $\begingroup$ I got something different $0 =\frac{\delta S_\lambda}{\delta f_i} =\frac{\delta}{\delta f_i}(\sum_{i=1}^\infty f_i \sum_{j=1}^i \sqrt{f_j} + \lambda\left(1-\sum_{i=1}^\infty f_i \right)) =\frac{\delta}{\delta f_i}(\sum_{i=1}^\infty [f_i \sum_{j=1}^i \sqrt{f_j}-\lambda f_i] + \lambda) =\sum_{i=1}^\infty \frac{\delta}{\delta f_i}[f_i \sum_{j=1}^i \sqrt{f_j}-\lambda f_i] =\sum_{i=1}^\infty [1\cdot\sum_{j=1}^i \sqrt{f_j}+f_i\frac{\delta}{\delta f_i}[ \sum_{j=1}^i \sqrt{f_j}]-\lambda]$ $\endgroup$
    – Dabed
    Commented Mar 18, 2021 at 23:51
  • $\begingroup$ $=\sum_{i=1}^\infty [\sum_{j=1}^i \sqrt{f_j}+f_i\frac{\delta}{\delta f_i}[ \sqrt{f_i}+\sum_{j=1}^{i-1} \sqrt{f_j}]-\lambda] =\sum_{i=1}^\infty [\sum_{j=1}^i \sqrt{f_j}+\frac{1}{2}\sqrt{f_i}-\lambda]\Rightarrow \sum_{j=1}^i \sqrt{f_j}+\frac{\sqrt{f_i}}{2}-\lambda=0 \Leftrightarrow f_i=[\frac{2}{3}(\lambda-\sum_{j=1}^{i-1}\sqrt{f_i})]^2 $ $\endgroup$
    – Dabed
    Commented Mar 18, 2021 at 23:51
  • $\begingroup$ I think you might be using the same index for the sum and the derivative (i.e., try calculating $\delta S_\lambda / \delta f_a$ to have a distinct index from the sum's running index.) $\endgroup$
    – J Bausch
    Commented Mar 19, 2021 at 9:40
  • 1
    $\begingroup$ The continous analog $$\int_0^\infty f(x) \int_0^x \sqrt{f(y)} \,dy \, dx $$ has Dirac sequences at $0$ as minimizing sequences with value $0$. Regarding the discrete system as a regularization of the continuum one, one might think that $f_1=1$ is a candidate, giving value $1$ for the functional. One can do slightly better by setting $f_i = \gamma^{i-1} (1-\gamma)$ for $\gamma\in (0,1)$, which leads to the value $$\frac{\sqrt{1-\gamma}}{1-\gamma^{\frac{3}{2}}}.$$ The minimizer of this function gives $\gamma=\frac{2-\sqrt{3}}{2}$ with value approximately $0.978593$ as benchmark result. $\endgroup$
    – André Schlichting
    Commented Mar 19, 2021 at 12:13
  • $\begingroup$ As I see it for the continuum case $S=\int_{x_i}^{x_f} L(x, f(x), f '(x))dx+C$ we write $\frac{\partial S}{\partial f(x)}$ instead of $\frac{\partial S}{\partial f(y)}$ so for $S=\sum_{i=1}^\infty f_i \sum_{j=1}^i \sqrt{f_j} + \lambda(1-\sum_{i=1}^\infty f_i)=\sum_{i=1}^\infty [f_i \sum_{j=1}^i \sqrt{f_j}-\lambda f_i] + \lambda=\sum_{i=1}^\infty L(f_i) + \lambda$ one shouldn't take the functional derivative $\frac{\partial S}{\partial f(a)}$ but rather $\frac{\partial S}{\partial f(i)}$ at least I believe but we would be better if we could just put this on wolframalpha to know exactly $\endgroup$
    – Dabed
    Commented Mar 19, 2021 at 13:58

1 Answer 1

Reset to default
1
$\begingroup$

The basic heuristic starts with looking at the continous analog $$ \int_0^\infty f(x) \int_0^x \sqrt{f(y)} \,dy \, dx , $$ which has Dirac sequences at 0 as minimizing sequences with value 0. Regarding the discrete system as a regularization of the continuum one, one might think that $f_1=1$ and $f_i=0$ for $i\geq 2$ is a candidate, giving value $1$ for the functional.

However, the form of the Euler-Lagrange equation shows that one might gain something by distributing the mass around. Hence, a possible ansatz is $f_i =\gamma^{i-1}(1−\gamma)$ for $\gamma\in [0,1)$, containing the case of all mass concentrated in $i=1$ as $\gamma=0$. This ansatz leads to a value of the functional of $$ \frac{\sqrt{1-\gamma}}{1-\gamma^{\frac{3}{2}}}. $$ The minimizer of this function in $\gamma\in [0,1)$ is given by $\gamma=\frac{2-\sqrt{3}}{2}$ with value for the functional of $$ \sqrt{\frac{4}{9}+\frac{8}{9 \sqrt{3}}} = 0.978593 . $$ It is left to verify that this sequence $f_i$ actually satisfies the Euler-Lagrange equation, which I checked via mathematica.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .