Robust nonlinear regression in scipy

The last feature I was working on is robust loss functions support. The results are again available as IPython Notebook, look here (I’m struggling to get “&” work correctly in LaTeX blocks, so the formatting is a bit off at the moment). The plan is to provide this example as tutorial for scipy.

Large-Scale Bundle Adjustment

As a demonstration of large-scale capabilities of the new least-squares algorithms we decided to provide an example of solving a real industry problem called bundle adjustment. The most convenient form is IPython Notebook, later it will serve as an example/tutorial for scipy (perhaps hosted on some server). Here I just give a link to the static version

Algorithm Benchmarks

This post was updated to improve its clarity and to incorporate new information about “leastsqbound”.

Before I present the results I want to make a few notes.

  1. Initially I wanted to find a very accurate reference optimal value for each problem and measure the accuracy of an optimization process by comparison with it. I abandoned this idea for several reasons. a) In local optimization there isn’t a single correct minimum, all local minima are equivalently good. So ideally we should find all local minima which can be hard and comparison logic with several minima becomes awkward. b) Sources with problem descriptions often provide inaccurate (or plain incorrect) reference values or provide them with single precision, or doesn’t provide them at all. Finding optimal values with MATLAB (for example) is cumbersome and still we can’t 100% assure the required accuracy.
  2. It is desirable to compare algorithms with identical termination conditions. But this requirement is never satisfied in practice as we work with already implemented algorithms. Also there is no one correct way to specify termination condition. So the termination conditions for all algorithms will be somewhat different, but nothing we can do about it.

Continue reading Algorithm Benchmarks

Trust Region Reflective Algorithm

The most relevant description of this algorithm can be found in the paper “A subspace, interior and conjugate gradient method for large-scale bound-constrained minimization problems” by Coleman and Li, some insights on its implementation can be found in MATLAB documentation here and here. The difficulty was that the algorithm incorporates several ideas, but it was not very clear how to combine them all together in the actual code. I will describe each idea separately and then outline the algorithm in general. I will consider the algorithm applied to a problem with known Hessian, in least squares we replace it by J^T J. I won’t give any explanation or motivation for some things, if you are really interesting try digging into the original papers.

Continue reading Trust Region Reflective Algorithm

Basic Algorithms for Nonlinear Least Squares

Hi! The last two weeks in GSoC I spent time developing algorithm drafts, testing and tuning them. It is an addicting process and I spent perhaps already too much time on it. The results are pretty good, but now I seriously need to stop it and start writing production quality code and so on.

The first thing we decided I should do is to provide a plain English description of the methods I studied and implemented. To make it more understandable I decided to make this post as an introduction to nonlinear least-squares optimization. So here I start.

Continue reading Basic Algorithms for Nonlinear Least Squares