topic algorithm in nonlinear optimization in Intel® oneAPI Math Kernel Library

algorithm in nonlinear optimization

Hanyou_Chu — Thu, 05 Apr 2012 18:58:17 GMT

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.

algorithm in nonlinear optimization

mecej4 — Thu, 05 Apr 2012 19:34:46 GMT

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.

algorithm in nonlinear optimization

Hanyou_Chu — Thu, 05 Apr 2012 20:11:08 GMT

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.

algorithm in nonlinear optimization

Nikita_S_Intel — Fri, 06 Apr 2012 07:41:43 GMT

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.

algorithm in nonlinear optimization

mecej4 — Fri, 06 Apr 2012 10:42:53 GMT

> 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.

algorithm in nonlinear optimization

Hanyou_Chu — Sat, 07 Apr 2012 00:20:05 GMT

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.