algorithm in nonlinear optimization

[Hanyou_Chu]

What's the algorithm used in nonlinear least squares optimization routine? Earlier manual claims that it is trust region algorithm. Is it based on the package TRON? How is the Hessian computed? I needed to know before I decide whether I should test it.

[mecej4]

There are ready-to-run examples in C and Fortran in the MKL examples/solverc and examples/solverf directories.

Typically, nonlinear least-squares routines avoid the expensive calculation of the Hessian. This is one of the reasons why we should not apply a general multivariate optimization routine to a least-squares problem.

[Hanyou_Chu]

I wasn't asking how to use it or what problems it tries to solve. I want to know the internal details so that I can decide whether I should use it to replace other packages I am using. For example if it is simply using J^T J for the Hessian at every step of the iteration, it's not even worthy of considering.

[Nikita_S_Intel · Accepted solution]

The solver for nonlinear least squares problem is based on trust-region algorithm and doesnt calculate Hessian matrix directly. It makes approximation by H = J^TJ.

[mecej4]

> if it is simply using J^T J for the Hessian at every step of the iteration, it's not even worth{y} of considering

That statement is probably based on a literal interpretation of a mathematical description of what is done in the MKL routines.

Typically, instead of forming the normal equations J^T(x_k) J(x_k) s_k = -J^T(x_k) r(x_k) and solving them, as compact mathematical notation in algorithm descriptions may indicate, the overdetermined equations J(x_k) s_k = -r(x_k) are solved using orthogonal factorization. A similar situation: we may write the solution of (n linear equations in n unknowns) A x = b as x = A^-1 b, but in software the inverse is never formed and used this way.

[Hanyou_Chu]

Thanks. I am curious, is it based on TRON? I tried TRON over 10 years ago and wasn't happy with it. With the right choice of initial trust region parameter, it at best matches MINPACK performance.