5
$\begingroup$

Suppose I am minimizing the following function:

$$g(\alpha)=\sum_{i=1}^n(y_i-f(x_i,\alpha))^2,$$

where $y_i$ and $x_i$ are data, $f$ is a known non-linear function and $\alpha$ parameter (of dimension larger than 1) of interest. Is it better to minimise

$$\frac{g(\alpha)}{n}$$

instead in order to guard against round-off errors, etc? In my case I get conflicting results, for some problems normalisation leads to a vast improvement in proportion of achieved convergence (I do MC simulations so I know the true value $\alpha$) in other cases not so much. Maybe there is some kind of an algorithm or a general advice when to choose the scaling and when not to?

I use R's optim function for optimisation. I tried method=Nelder-Mead, "CG" and "BFGS". Results are different for CG and BFGS and the same for Nelder-Mead. The differences are slight, but measurable especially for BFGS. Naturally I use the same starting values and the same data for each optimisation run.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Without more information, it's not necessarily clear if scaling is a problem here. For convex least-squares problems, it is helpful to scale a problem so that the linear solves used in algorithms are well-conditioned; many solvers already do this automatically. If your problem is nonconvex and you are using a convex solver without supplying an initial guess, the solver heuristics may select different initial guesses, and converge to different local minima. $\endgroup$
    – Geoff Oxberry
    Commented Jul 11, 2013 at 18:56
  • $\begingroup$ I've updated the question with more details. I think though that my optimisation problems are ill-posed. The problem is that I'm developing a software where $f$ can be anything, so I'm trying to find the best solution probably among only the bad ones. $\endgroup$
    – mpiktas
    Commented Jul 12, 2013 at 8:43
  • $\begingroup$ Nelder-Mead isn't guaranteed to converge if your parameter vector has dimension greater than 1. Given that it uses scalar multiplications of parameters that are usually around one and vector additions/subtractions, unless your vector of parameters is very badly scaled, it's unlikely that scaling will affect it (except possibly with an absolute convergence criterion, and even then, not by much). The non-convexity of $f$ and initial guesses could still be an issue. Could you describe what you mean by "conflicting results" and give us a typical choice of $f$? If you can, be quantitative. $\endgroup$
    – Geoff Oxberry
    Commented Jul 12, 2013 at 19:53

2 Answers 2

Reset to default
4
$\begingroup$

The difficulty in optimization is finding the location of the minimum, not the value at this point. This is why your scaling makes no difference: the location is exactly the same. Furthermore, every reasonable optimization algorithm should produce exactly the same sequence of intermediate points (iterates) whether you scale the objective function or not. This is, for example, easy to see for Newton's method.

Of course, if you are using your own minimizer and it doesn't possess the property that the sequence of iterates is the same whether the function is scaled or not, then you are in trouble. However, this mostly just indicates a problem with the design of the algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I use R's optim, with method="BFGS" and scaling does lead to different estimates in my case. I suspect the problem is not with the algorithm, but with my optimisation problem. $\endgroup$
    – mpiktas
    Commented Jul 12, 2013 at 8:18
1
$\begingroup$

if Nelder-Mead is consistent but the gradient-based methods aren't, it might be that the gradient is badly scaled. Eg. a unit change in parameter n affects the objective function very differently than a unit change in parameter m. Try scaling the parameters (what's f btw?) to (approximately) the same range, or if you can even better so that if you change any single parameter by a given amount the objective function will change similarly. (eg. http://www.alglib.net/optimization/scaling.php)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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