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!

$\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
    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
    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
    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$ 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
    Mar 19, 2021 at 13:58

1 Answer 1

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.