Timeline for What are the differences between the different gradient-based numerical optimization methods?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 7, 2017 at 11:14 | comment | added | Eduardo J. Sanchez | "Why some people want to motivate an optimization algorithm by mentioning a linear solver is a question only they can answer" -- As I read Nocedal and Wright's famous book on numerical optimization, I came through this quote: "Conjugate gradient methods were originally designed to solve systems of linear equations Ax = b where the coefficient matrix A is symmetric and positive-definite." | |
| May 30, 2017 at 11:27 | comment | added | Richard Zhang | Actually, for nonquadratic objectives, NCG is quite a bit less robust than steepest descent; quasi-Newton methods (e.g. BFGS) work much better. It is interesting to note that these also reduce to CG (and hence accelerated Nesterov) under the linear limit and certain assumptions. Nocedal & Wright make a nice comparison between NCG and quasi-Newton in their book. | |
| May 29, 2017 at 20:06 | comment | added | Royi | Such a lovely answer. Where could one read about the equivalency of Nesterov Accelerated Gradient Descent and Conjugate Gradient? | |
| May 25, 2017 at 13:34 | comment | added | Mark L. Stone | Steepest descent can be line search or trust region (or no search). | |
| May 25, 2017 at 8:20 | history | edited | Christian Clason | CC BY-SA 3.0 |
added 37 characters in body
|
| May 25, 2017 at 8:19 | comment | added | Christian Clason | @MarkL.Stone Well, straining things a bit you could argue that they do: if you consider the trust region step as a combined choice of $\tau_k d^k$ -- notice that I didn't treat the choice of $\tau_k$ at all. (I personally think that trust region methods are a much better choice than the usual line searches.) But that's beside the point here -- I only wanted to give a framework that covers the methods the OP listed, not argue that it is the (only or best) framework for optimization. Even in that framework, the list can certainly be extended. I've edited the answer to make that clear(er). | |
| May 25, 2017 at 1:15 | comment | added | Mark L. Stone | So you don't consider trust region versions to be among "most methods"? | |
| May 24, 2017 at 12:57 | vote | accept | Eduardo J. Sanchez | ||
| May 24, 2017 at 10:25 | history | edited | Christian Clason | CC BY-SA 3.0 |
added 12 characters in body
|
| May 24, 2017 at 10:24 | comment | added | Christian Clason | Of course, but there the context is explicitly about solving linear systems, not optimization as in this question. That was exactly my point: horses for courses. | |
| May 24, 2017 at 10:20 | comment | added | origimbo | For a fair number of numerical methods for PDEs textbooks the motivation question is clearly close to the inverse of the point you make. They already have an invertible, symmetric positive definite linear system to solve, and don't want to get too distracted talking about optimisation. A classic example would be Numerical Recipes by Press et al., where the chapter ordering puts linear systems first. | |
| May 24, 2017 at 10:09 | history | answered | Christian Clason | CC BY-SA 3.0 |