I have the following optimization problem on the variables $a_1, ..., a_n$:
$$ minimize \frac{\sum_{k=1}^{n}\max(k\cdot a_{k},1)}{\sum_{k=1}^{n}a_{k}} $$ $$ such\ that\ \ 0\leq a_k\leq 1\ \ \ (k=1, ..., n)$$
My current solution is as follows:
The ratio is minimized when the denominator increases and the nominator decreases.
The denominator increases when the $a_{k}$'s increase, but then the nominator also increases. To minimize the ratio we should make $a_{k}$ large when $k$ is small and small when $k$ is large.
So suppose there is an integer $l$ such that:
- For $k=1,...,l, a_{k}$ has the maximum possible value of 1 (to maximize the denominator);
- For $k=l+1,...,n, a_{k}$ has the maximum value that makes the "max" function in the nominator select the value "1" (to minimize the nominator). This value is: $a_{k}=\frac{1}{k}$.
Now the ratio becomes:
$$ \frac{(\sum_{k=1}^{l}k)+(\sum_{k=l+1}^{n}1)}{(\sum_{k=1}^{l}1)+(\sum_{k=l+1}^{n}\frac{1}{k})}=\frac{\frac{1}{2}l(l+1)+(n-l)}{l+(H_{n}-H_{l})}>\frac{l^{2}-l+2n}{2(l+H_{n})} $$
Where $H_{n}$ is the n-th harmonic number. The last step results from removing the term $H_l$ from the denominator, which only makes the denominator larger.
I will skip the details of finding the $l$ which minimizes the above expression. It is $O(\sqrt n)$, which makes the nominator $O(n)$ and the denominator $O(\sqrt n)$, so the total minimum ratio is $O(\sqrt n)$.
MY QUESTION IS: Is my reasoning correct? I am especially worried about my assumption that the sequence $a_1, ..., a_k$ has the specific format that I described above (i.e. starts with $a_k=1$ and then changes to $a_k={1 \over k}$). It makes sense, but I could not prove it. Can you help?
Let $l$ be the number of $a_k > 1/k.$ You should obviously make those $a_k$ equal to $1,$ and let $k_1, \dots, k_{n-l}$ be the indices of the other $a_k.$ Keep the subset $k_1, \dots, k_{n-l}$ fixed, and minimize your function. What is the best assignment of the $a_k?$ To do this, I think the easiest thing is to fix the sum of the $a$s, (call it $x$) and use lagrange multipliers, which will tell you that $a_{k_i}$ is proportional to $1/k_i$. This should make it clear that the best choice of the $k_i$ (given the sum $x$) is the one you suggest, and then you can optimize $x$ (given $l$), and then $l.$ When the smoke clears, I am pretty sure you get your solution.