21
$\begingroup$

I need to find the minimum of a function. Reading the docs at http://docs.scipy.org/doc/scipy/reference/optimize.html I see that there are several algorithms that do the same thing, i.e. find the minimum. How do I know which one I should choose?

some of the algorithm listed

  • Minimize a function using the downhill simplex algorithm.
  • Minimize a function using the BFGS algorithm.
  • Minimize a function with nonlinear conjugate gradient algorithm.
  • Minimize the function f using the Newton-CG method.
  • Minimize a function using modified Powell's method.

My function is linear. dimensionality is around 232750(this is how many different gradients I have to compute each time), it takes about 2 mins to compute the gradient and the cost once, so not cheap. I don't think I have constraints. it is deterministic and continuous.

Improve this question
$\endgroup$
5
  • $\begingroup$ Well you have to investigate the nature of your problem: Is it linear or not? What is the dimensionality of it? Is your cost function cheap to evaluate? Can you evaluate your derivative(s) analytically and/or cheaply? Do you have constraints? If you have constraints can you write your problem easily as being unconstrained? Please elaborate on these matters more. $\endgroup$
    – usεr11852
    Apr 5, 2013 at 15:28
  • $\begingroup$ @user11852 It is linear. dimensionality is around 50 features, it takes about 2 mins to compute the gradient and the cost once, so not cheap. I don't think I have constraints. $\endgroup$
    – siamii
    Apr 5, 2013 at 15:45
  • $\begingroup$ I'm not sure what you mean by "linear" here. If your problem is linear, the gradient is constant and cheap to compute. If your objective function is linear and doesn't have constraints, the minimum is -infinity (or perhaps 0). $\endgroup$
    – paul
    Apr 5, 2013 at 17:25
  • $\begingroup$ @paul : In optimization linearity usually refers to the constraints, not to the function itself. I (erroneously granted) referred to "linearity" in relation with the smoothness of the function and I think that is what the OP also referred at. In my answer I was mostly based on the fact he said "continuous" afterwards anyway. $\endgroup$
    – usεr11852
    Apr 5, 2013 at 23:27
  • $\begingroup$ I'm the author of the HumpDay package which you can use to choose a global optimizer (see blog article) but I must say I'm very confused about what your optimization problem is. How can it be linear and yet require effort to compute gradients? Is the dimension 50 as the other answer infers. Peter $\endgroup$
    – Peter Cotton
    Feb 18, 2021 at 22:17

2 Answers 2

Reset to default
19
$\begingroup$

Based on what you said: I assume you have to optimize for 50 variables; I also assume that you are having a situation that it is very expensive to find analytical derivatives (let alone get numericals out) and that your optimization is unconstrained.

Let me stress, you are a bit unluckily cause between 25-30 and 100 variables it is a bit of twilight zone when it comes to choosing between large or small scale optimization routines. Having said that though, nothing is lost.

Given that even first order derivative are expensive to get that kind off kills the idea of Newton's method. You might have some luck with Quasi-Newton (BFGS) though if your Hessian is slightly diagonal like to start with. C-G is usually a bit slower than BFGS so probably that won't be improve things a lot; use it if memory is also an issue (or just go for L-BFGS in that case). Additionally given how slow it is to evaluate your function, a simple steepest descent/line search algorithm would be tortuously slow; same things goes with Simulated Annealing and other random search variants (I assume you don't have access to HMC and all that jazz).

So, when you need the best bang for your buck when it comes to a single function evaluation: Go with Powell's method and also test COBYLA; despite being a constrained optimization algorithm because it will internally linear approximate your function's gradient to speed up things, it will be able to take advantage of your function's linearity. Also definitely try NLopt for Python. They have a lot of gradient-free optimizers; try UOBYQA; it's Powell's brainchild also (Unconstrained Optimization BY Quadratic Approximations).

Very briefly : The N-CG algorithms depends on computing the Hessian, and your Hessian seems very expensive to compute. NLCG and BFGS don't require it although the might try to try compute it once in their first step.

I left out the simplex algorithm on purpose because it's a totally different beast; nothing to do with gradients as such. Try it but I can't really comment on it; it is really dependent on your problem's nature.

For a first good reference on numerical optimization C.T.Kelly's book Iterative Methods for Optimization will get you quite far, quite nicely.

Improve this answer
$\endgroup$
5
  • $\begingroup$ For future reference: you might be interested to check the Computational Science beta on Stackexchange for similar questions. $\endgroup$
    – usεr11852
    Apr 5, 2013 at 16:56
  • $\begingroup$ thanks for the answer. Actually, my dimensionality is 232,750. This is the number of gradients I calculate each time. I do the function evaluation and gradient computation on the GPU. Would that be compatible with NLopt? $\endgroup$
    – siamii
    Apr 6, 2013 at 11:47
  • $\begingroup$ I have not used NLopt on GPUs but I see no obvious reason why it should be a problem regarding compatibility. I might question thought the issue though of frequent I/O operation from and to the GPU. $\endgroup$
    – usεr11852
    Apr 6, 2013 at 15:28
  • $\begingroup$ @usεr11852, Can also discuss the comparison of gradient descent & QR decomposition methods for minimization of linear regression cost function? Do I need to ask a separate question? $\endgroup$
    – Dr Nisha Arora
    Aug 10, 2019 at 4:30
  • $\begingroup$ @DrNishaArora: Yes. That would be appropriate for a separate question. Please see the thread Why use gradient descent for linear regression, when a closed-form math solution is available? to make sure you avoid duplication! $\endgroup$
    – usεr11852
    Aug 10, 2019 at 10:00
1
$\begingroup$

Maybe you should get yourself an introductory book about numerical optimization. You will need to take into account your function in order to decide for the algorithm.

Among the algorithms you mention, important differences are whether the Jacobian or Hessian is needed or only the function itself.

Considering that this is a statistics Q&A site and thus deals with random variables: make sure your function is deterministic can be evaluated in a way that yields continuous results over the search space.

Improve this answer
$\endgroup$
1
  • $\begingroup$ it is deterministic and continuous. $\endgroup$
    – siamii
    Apr 5, 2013 at 15:46

Your Answer

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

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