NEWUOA

NEWUOA^[1] 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 $Q_{k}$ by quadratic interpolation, and then minimizes $Q_{k}$ within a trust region.

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

To construct the models, NEWUOA maintains a set of interpolation points throughout the iterations. The update of this set is another feature of NEWUOA.^[1]

NEWUOA algorithm was developed from UOBYQA (Unconstrained Optimization BY Quadratic Approximation).^[5]^[6] A major difference between them is that UOBYQA constructs quadratic models by interpolating the objective function at $(n+1)(n+2)/2$ points.

NEWUOA software was released on December 16, 2004.^[7] It can solve unconstrained optimization problems of a few hundreds variables to high precision without using derivatives.^[1] In the software, $m$ is set to $2n+1$ by default.^[6]

Other derivative-free optimization algorithms by Powell include COBYLA, UOBYQA, BOBYQA, and LINCOA.^[7] BOBYQA and LINCOA are extensions of NEWUOA to bound constrained and linearly constrained optimization respectively.

Powell did not explain how he coined the name "NEWUOA" either in the introducing report ^[1] or in the software,^[6] although COBYLA, UOBYQA, BOBYQA and LINCOA are all named by acronyms. Probably "NEWUOA" means "NEW Unconstrained Optimization Algorithm".

The NEWUOA software is distributed under The GNU Lesser General Public License (LGPL).^[6]

References

1 2 3 4 Powell, M. J. D. (November 2004). The NEWUOA software for unconstrained optimization without derivatives (PDF) (Report). Department of Applied Mathematics and Theoretical Physics, Cambridge University. DAMTP 2004/NA05. Retrieved 2014-01-14.
↑ Powell, M. J. D. (2004). "Least Frobenius norm updating of quadratic models that satisfy interpolation conditions". Mathematical Programming. Springer. 100: 183–215. doi:10.1007/s10107-003-0490-7.
↑ Dennis, Jr., J. E.; Schnabel, R. B. (1979). "Least Change Secant Updates for Quasi-Newton Methods". SIAM Review. SIAM. 21: 443–459. doi:10.1137/1021091. JSTOR 2030103.
↑ Powell, M. J. D. (2013). "Beyond symmetric Broyden for updating quadratic models in minimization without derivatives". Mathematical Programming. Springer. 138: 475–500. doi:10.1007/s10107-011-0510-y.
↑ Powell, M. J. D. (2002). "UOBYQA: unconstrained optimization by quadratic approximation". Mathematical Programming. Springer. 92: 555–582. doi:10.1007/s101070100290.
1 2 3 4 "Source code of NEWUOA software". Retrieved 2014-01-14.
1 2 "A repository of Professor M. J. D. Powell's software". Retrieved 2014-01-14.

External links

Optimization software by Professor M. J. D. Powell at CCPForge

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear: Methods calling …

… functions

… and gradients

Convergence	Trust region Wolfe conditions

Quasi–Newton	BFGS and L-BFGS DFP Symmetric rank-one (SR1)

Other methods	Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient Truncated Newton

… and Hessians

Newton's method

The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.

Constrained nonlinear

General	Barrier methods Penalty methods

Differentiable	Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization

Convex
minimization

Linear and
quadratic

Interior point	Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar

Basis-Exchange	Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial

Paradigms

Graph
algorithms

Minimum spanning tree	Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal

Network flows

Metaheuristics

Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search

Categories
- Algorithms and methods
- Heuristics
Software

This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

NEWUOA

See also

References

External links