Physics 212, 2019: Lecture 15

Back to the main Teaching page.

Back to Physics 212, 2019: Computational Modeling.

Optimization is hard

While a lot more can be added here (see the appropriate section of the Numerical Recipes book), it suffices to say that optimization is hard. And the more dimensional the optimization problem is, the harder it is, generally. Overall, this in because

• In large dimensions, the volume of the parameter space grows quickly. If one needs to find the minimum to the accuracy $\Delta x$, and the typical size of the system along each dimension is $L$, then there are $(L/\Delta x)^{d}$ spaces to explore in $d$ dimensions, which very quickly becomes hard even for relatively small $d$.
• There's usually just one global minimum, but many local minima that we are not interested in. The optimizers get stuck in the local minima and can't escape them to find the global ones. This is more likely in large dimensional problems.
• There are also regions of space where the loss function ${\cal {L}}$ is nearly flat, so that the optimizer does not know which way to go towards the minimum. Again, this is more likely in higher dimensions.
• In higher dimensions there are a lot of other exotic situations, such as valleys, narrow canyons, funnels, discontinuous walls -- and all those make optimization harder.

There are some exceptions -- problems like the multivariate linear regression one -- that are known as "convex", which means that there's just one minimum (global or local), and there are no flat regions, and so one can easily find the minimum. Nonetheless, even in non-convex problems, one often can find at least a local minimum by simply following the gradient, and sliding downhill. We will explore this in the later lectures.

1-d optimization

1-d optimization is special. While for larger-dimensional problems finding a minimum is never guaranteed, in 1-d we are guaranteed to find a minimum if we bracketed it (that is, know the value of the function in three points, and the value is higher for the two exterior points than the interior one). This can be done with the golden mean 1-d search

• Multi-dimensional linear regression (no derivations) using numpy.linalg.lstsq http://docs.scipy.org/doc/numpy-1.10.0/reference/generated/numpy.linalg.lstsq.html
• General considerations for nonlinear minimization (with and without derivatives; with and without second derivatives)
• Golden mean 1-d search
• Parabolic interpolation
• Newton method

Your turn

Write down a parabolic interpolation or Newton method minimizer of 1-d functions. Minimize a ${\rm {cosh}}x$ using your minimizer. Do you get the expected result?

• Submit your work.