Name: Numerical Optimization
ISBN: 9780387400655

Numerical Optimization

Numerical Optimization presents a comprehensive and up-to-date description of the most effective methods in continuous optimization. It responds to the growing interest in optimization in engineering, science, and business by focusing on the methods that are best suited to practical problems. For this new edition the book has been thoroughly updated throughout. There are new chapters on nonlinear interior methods and derivative-free methods for optimization, both of which are used widely in practice and the focus of much current research. Because of the emphasis on practical methods, as well as the extensive illustrations and exercises, the book is accessible to a wide audience. It can be used as a graduate text in engineering, operations research, mathematics, computer science, and business. It also serves as a handbook for researchers and practitioners in the field. The authors have strived to produce a text that is pleasant to read, informative, and rigorous - one that reveals both the beautiful nature of the discipline and its practical side. There is a selected solutions manual for instructors for the new edition.

What Hacker News says

shooApr 2025

I was curious how well the simple momentum step-size approach shown in the first interactive example compares to alternative methods. The example function featured in the first interactive example is named bananaf ("Rosenbrok Function banana function"), defined as

  var s = 3
  var x = xy[0]; var y = xy[1]*s
  var fx   = (1-x)*(1-x) + 20*(y - x*x )*(y - x*x )
  var dfx  = [-2*(1-x) - 80*x*(-x*x + y), s*40*(-x*x + y)]

The interactive example uses an initial guess of [-1.21, 0.853] and a fixed 150 iterations, with no convergence test.

From manually fiddling with (step-size) alpha & (momentum) beta parameters, and editing the code to specify a smaller number of iterations, it seems quite difficult to tune this momentum-based approach to get near the minima and stay there without bouncing away in 50 iterations or fewer.

Out of curiosity, I compared minimising this bananaf function with scipy.optimize.minimize, using the same initial guess.

If we force scipy.optimize.minimize to use method='cg', leaving all other parameters as defaults, it converges to the optimal solution of [1.0, 1./3.] requiring 43 evaluations of fx and dfx,

If we allow scipy.optimize.minimize to use all defaults -- including the default method='bfgs', it converges to the optimal solution after only 34 evaluations of fx and dfx.

Under the hood, scipy's method='cg' and method='bfgs' solvers do not use a fixed step size or momentum to determine the step size, but instead solve a line search problem. The line search problem is to identify a step size that satisfies a sufficient decrease condition and a curvature condition - see Wolfe conditions [1]. Scipy's default line search method -- used for cg and bfgs -- is a python port [2] of the dcsrch routine from MINPACK2. A good reference covering line search methods & BFGS is Nocedal & Wright's 2006 book Numerical Optimization.

[1] https://en.wikipedia.org/wiki/Wolfe_conditions [2] https://github.com/scipy/scipy/blob/main/scipy/optimize/_dcs...

thread

sfpotterMar 2025

Another good approach can be to start by prototyping something in MATLAB, numpy/scipy, or Julia, and then consult their docs when whatever you're doing is falling short in some way. All of these computing environments have extensive references. Look up the function you're using in their docs and you'll find links to papers and books with more context. Being able to "help yourself" in numerical methods basically requires that you're comfortable in the literature. This assumes that you have a very sophisticated and precise need which is not satisfied by what existing libraries offer.

If you have some quick one-off need, copying something from Numerical Recipes is a bad idea. Bugs in numerical methods can be very subtle and difficult to diagnose in a way that normal discrete algorithms aren't. If you've never heard of the asymptotic order of convergence of a numerical algorithm, how are you possibly going to detect that you have a bug there, let alone fix it? In my experience, most people who have one-off needs don't have the requisite background in numerical analysis to get themselves out of trouble when things go wrong. A better approach is to just use a library. There are lots of options for simple stuff.

If you do have a sophisticated need, you will outgrow what Numerical Recipes offers very quickly. There are some good books in the list you linked, but that list is also very outdated. Notably absent: any of Trefethen's books (ATAP in particular), Nocedal and Wright's "Numerical Optimization", Stoer & Bulirsch, anything about convex optimization, anything about the finite element method, anything about geometry or CAD, anything about Monte Carlo, anything about special functions, and on and on...

thread

eklerakiJul 2022

My point was not backprop, but time of publication.

However, "reverse-mode" AD is not as simple as just caching results.

> BP’s continuous form was derived in the early 1960s (Kelley, 1960; Bryson, 1961; Bryson and Ho, 1969). Dreyfus (1962) published the elegant derivation of BP based on the chain rule only.

> explicit, efficient error backpropagation (BP) in arbitrary, discrete, possibly sparsely connected, NN-like networks

But that wasn't close enough to current BP

> BP’s modern efficient version for discrete sparse networks (including FORTRAN code) was published by Linnainmaa (1970). Here the complexity of computing the derivatives of the output error with respect to each weight is proportional to the number of weights. That’s the method still used today.

See [1] for more details.

I do not know the exact implementation details of Linnainmaa's BP, but there are all sorts of improvements to plain reverse mode auto-grad through stuff like Jacobian-Vector products that save an enormous amount of memory.

Nocedal's "Numerical Optimization" covers a great deal on how to implement autograd, and I can easily recommend it to anyone interested.

[1] https://www.reddit.com/r/MachineLearning/comments/e5vzun/d_j...

thread

dkshdkjshdkJul 2021

He said "your #1", making reference to the first book in OPs list: "Numerical Optimization" by Jorge Nocedal and Stephen J. Wright.

It's pretty fun to read.

thread

kxyvrNov 2017

Alright, so I do research in and produce optimization tools professionally. From my biased point of view, someone is better off learning generic optimization theory and algorithms rather than specialized versions like convex or stochastic optimization. Generally speaking, generic nonlinear optimization methods form the foundation for everything and then there's a series of tricks to specialize the algorithm.

Very specifically, there are two books that I think provide a good foundation. First, is Convex Functional Analysis by Kurdila and Zabarankin. Not many people know about this book, but essentially it provides a self-contained background to prove the Generalized Weirstrass Theorem, which details the conditions necessary for the existence and/or uniqueness of an optimization problem. This is important because even convex problems don't necessarily have a minimum. For example, min exp(-x) doesn't have one, but it does have an infimum. The background necessary to understand this book is real analysis and as a quick aside I think Rudin's Principles of Mathematical Analysis is the best for this. Second, is Nocedal and Wright's Numerical Optimization book. It provides a good overview of the powerful algorithms in optimization that we should be using. Now, it's weakness is that it often cheats and uses a stronger constraint qualification than we're afforded in practice. Candidly, I find that the derivative of the constraints will not remain full rank and we will likely violate the LICQ. Further, it covers a number of algorithms that really shouldn't be used in practice, ever. That said, it does cover the good algorithms and it generally has the best presentation out of the other books.

Sadly, I don't know of any killer books for numerical linear algebra. And, yes, I've read cover to cover things like Saad's Iterative Methods for Sparse Linear Systems, Trefethen and Bau's Numerical Linear Algebra, and Golub and van Loan's Matrix Computations. They're valuable and well-written, but don't quite cover what I end up having to do to make linear algebra work on my solvers.

Anyway, this is all biased and opinion, so take what you will. If someone else has some of their favorite references for optimization or numerical linear algebra, I'd love to hear.

thread

kxyvrJun 2016

I'm glad there's more free material online for optimization modeling and algorithms. Personally, here's my favorite list for algorithms and modeling for optimization:

For learning the simplex method, Linear Programming by Vasek Chvatal (first 10 chapters): https://books.google.com/books?id=DN20_tW_BV0C&printsec=fron...

For learning branch and bound, Integer Programming by Laurence A. Wolsey https://books.google.com/books?id=x7RvQgAACAAJ

For odd modeling tricks for integer programming, Logic and Integer Programming by Williams, H. Paul https://www.springer.com/us/book/9780387922799

For modeling tricks for convex programming, Convex Optimization by Stephen Boyd and Lieven Vandenberghe https://stanford.edu/~boyd/cvxbook/

For basic nonlinear optimization algorithms, Numerical Optimization by Nocedal, Jorge, Wright, S. https://www.springer.com/us/book/9780387303031

I've never really found the ultimate optimization book, but the references above tend to have the right modeling techniques, algorithms, and references. I've found they're a good place to get the right idea and the right words to search for more material.

thread