Limit partially-separable function

[paraynaud]

@dpo, I made a successful limit function:

$$ \sum_{j=1}^{\frac{n}{\sqrt{n}}} \left (\sum_{i= (j-1) \sqrt{n}}^{j \sqrt{n}} \frac{i * x_i}{x_j} \right )^2 + \sum_{j=1}^{\frac{n}{\sqrt{n}}-1} \left (\sum_{i= (j-1) \sqrt{n}+5}^{j \sqrt{n}+5} \frac{i * x_i}{x_j} \right )^2 $$

where each element's size is div=Int(floor(sqrt(n))) $\approx\sqrt(n)$, which makes $n_i$ grow as $n$ increases but not too much.
For example, when n is set to 5000, rounded to n=4970, $f$ considers 139 element functions depending on $70 \leq n_i \leq 73$ elemental variables.
The function is not quadratic anymore, but stays positive.
The second sum term is to doubled the number of element functions.

In Julia, it gives:

function limit(x; n=length(x), div=Int(floor(sqrt(n))))
  f = Int(floor(n/div))
  sub(range) = sum(i * x[i] for i in range)^2
  sum( sub((i-1)*f+1:i*f)/(x[i]^2) for i in 1:div) + sum( sub((i-1)*f+5:i*f+5)/(x[n-i]^2) for i in 1:div-1) 
end

function start_limit(n :: Int; div=Int(floor(sqrt(n)))) 
  f = Int(floor(n/div))
  _n = f*div
  10 .* ones(_n)
end

This numerical result should take place after the performances profiles, so I kept only the best methods: LBFGS (linesearch), PSR1 and PLSE.
I chopped the curve of LBFGS because it reached at some point max_time=900. for any n greater to 5000, making the curve of iter falls without solving the problem.
We can observe that PLSE make more iterations than PSR1, but as n increases, the amount of computation from PSR1 exceeds the gain obtained by realizing less iterations!

Let me know what you think of those graphs:
time.pdf
iter.pdf