I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as when the Jacobian is sparse).

For example, the DFO-LS (Derivative-Free Optimizer for Least-Squares) solver documentation makes no mention of conditioning, whereas other solvers which use methods such as truncated SVD or Tikhonov regularisation never include good derivative free methods.

If none exist, is it maybe the case that the trust-region framework can already deal well with an ill-conditioned Jacobian and so something like DFO-LS is still worth trying, or is there no good way of solving such a case?

  • $\begingroup$ You're asking for a derivative-free solver but then mention the Jacobian? The Jacobian by definition is the derivative of the objective function residuals. The TSVD and Tikhonov methods would require a Jacobian matrix. So do you have a Jacobian available or not? $\endgroup$ – vibe Aug 4 '20 at 17:02
  • $\begingroup$ Many derivative-free solvers still have to come up with some estimate for the Jacobian (e.g. DFO-LS is based on the Gauss-Newton method) and I am saying that this estimate would be quite sparse. $\endgroup$ – Alex Ghorbal Aug 4 '20 at 17:15
  • $\begingroup$ A derivative free method will probably be even more expensive for an already expensive model, as an rather high amount of evaluations are needed (e.g. genetic algorithm, swarm optimization, etc...). Have you considered automatic differentiation? That could make a lot of sense for an expensive model, and calculate the (sparse) Jacobian at comparably littele additional computations cost. $\endgroup$ – Andreas H. Aug 4 '20 at 17:27
  • $\begingroup$ Is automatic differentiation really as good as it sounds? If so it would be perfect, but are there any obvious drawbacks? $\endgroup$ – Alex Ghorbal Aug 4 '20 at 18:47
  • 1
    $\begingroup$ What does sparsity have to do with the ill-conditioning of the Jacobian? $\endgroup$ – Brian Borchers Aug 4 '20 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.