NEWUOA

NEWUOA is a numerical optimization algorithm by Michael J. D. Powell. It is also the name of Powell's Fortran 77 implementation of the algorithm.

NEWUOA solves unconstrained optimization problems without using derivatives, which makes it a derivative-free algorithm. The algorithm is iterative and exploits trust-region technique. On each iteration, the algorithm establishes a model function ${\displaystyle Q_{k}}$ by quadratic interpolation and then minimizes ${\displaystyle Q_{k}}$ within a trust region.

One important feature of NEWUOA algorithm is the least Frobenius norm updating technique. Suppose that the objective function ${\displaystyle f}$ has ${\displaystyle n}$ variables, and one wants to uniquely determine the quadratic model ${\displaystyle Q_{k}}$ by purely interpolating the function values of ${\displaystyle f}$, then it is necessary to evaluate ${\displaystyle f}$ at ${\displaystyle (n+1)(n+2)/2}$ points, as a quadratic polynomial of ${\displaystyle n}$ variables has this amount of independent coefficients. But this is impractical when ${\displaystyle n}$ is large, because the function values are supposed to be expensive in derivative-free optimization. In NEWUOA, the model ${\displaystyle Q_{k}}$ interpolates only ${\displaystyle m}$ (an integer between ${\displaystyle n+2}$ and ${\displaystyle (n+1)(n+2)/2}$, typically of order ${\displaystyle n}$) function values of ${\displaystyle f}$, and the remaining degrees of freedom are taken up by minimizing the Frobenius norm of ${\displaystyle \nabla ^{2}Q_{k}-\nabla ^{2}Q_{k-1}}$. This technique mimics the least-change secant updates for quasi-Newton methods and can be considered as the derivative-free version of PSB update (Powell's symmetric Broyden update).

...
Wikipedia