en>Dthomsen8: clean up, added orphan tag, typo(s) fixed: , → , (3) using AWB

2014-01-06T03:20:13Z

clean up, added orphan tag, typo(s) fixed: , → , (3) using AWB

New page

'''NEWUOA'''<ref name="report">{{Cite report |author= Powell, M. J. D. |date= November 2004 | title=The NEWUOA software for unconstrained optimization without derivatives | url=http://www.damtp.cam.ac.uk/user/na/NA_papers/NA2004_08.pdf |publisher=Department of Applied Mathematics and Theoretical Physics, Cambridge University |docket=DAMTP 2004/NA05|accessdate= 2014-01-14}}</ref> is a [[numerical analysis|numerical]] [[optimization (mathematics)|optimization]] [[algorithm]] by [[Michael J. D. Powell]]. It is also the name of [[Michael J. D. Powell|Powell]]'s [[Fortran#FORTRAN 77|Fortran 77]] implementation of the algorithm.

NEWUOA solves unconstrained [[optimization (mathematics)|optimization]] problems without using [[derivatives]], which makes it a [[derivative-free optimization|derivative-free]] algorithm. The algorithm is [[Iterative method|iterative]], and exploits [[trust region]] technique. On each iteration, the algorithm establishes a model function <math> Q_k </math> by [[quadratic]] [[interpolation]], and then minimizes <math> Q_k </math> within a [[trust region]].

One important feature of NEWUOA algorithm is the least [[Frobenius norm]] updating <ref>{{cite journal|last=Powell|first=M. J. D. |title=Least Frobenius norm updating of quadratic models that satisfy interpolation conditions |journal=Mathematical Programming |publisher= Springer |year=2004 |volume=100 |pages=183–215|doi=10.1007/s10107-003-0490-7}}</ref> technique. Suppose that the [[Optimization problem|objective function]] <math> f </math> has <math> n </math> variables, and one wants to uniquely determine the quadratic model <math> Q_k </math> by purely [[interpolation|interpolating]] the function values of <math> f </math>, then it is necessary to evaluate <math> f </math> at <math> (n+1)(n+2)/2 </math> points. But this is impractical when <math> n </math> is large, because the function values are supposed to be expensive in [[derivative-free optimization]]. In NEWUOA, the model <math> Q_k </math> [[interpolation|interpolates]] only <math> m </math> (an integer between <math> n+2 </math> and <math> (n+1)(n+2)/2 </math>, typically of [[Orders of approximation|order]] <math> n </math>) function values of <math> f </math>, and the remaining degree of freedom is taken up by minimizing the [[Frobenius norm]] of <math> \nabla^2 Q_k -\nabla^2 Q_{k-1}</math>. This technique mimics the least change secant updates <ref>{{cite journal |last= Dennis, Jr. |first= J. E. |last2= Schnabel|first2= R. B.|year= 1979 |title=Least Change Secant Updates for Quasi-Newton Methods |url= http://www.jstor.org/stable/2030103 |journal= SIAM Review |publisher= SIAM |volume= 21 |pages= 443–459 |accessdate=2014-01-14}}</ref> for [[Quasi-Newton methods]], and can be considered as the derivative-free version of [[PSB update]] ([[Michael J. D. Powell|Powell]]'s Symmetric [[Charles George Broyden|Broyden]] update).<ref>{{cite journal|last=Powell|first=M. J. D. |title=Beyond symmetric Broyden for updating quadratic models in minimization without derivatives |journal=Mathematical Programming |publisher= Springer |year=2013 |volume=138 |pages=475–500 |doi=10.1007/s10107-011-0510-y}}</ref>

To construct the models, NEWUOA maintains a set of [[interpolation]] points throughout the iterations. The update of this set is another feature of NEWUOA.<ref name="report"/>

NEWUOA algorithm was developed from [[UOBYQA]] (Unconstrained Optimization BY Quadratic Approximation).<ref>{{cite journal|last=Powell|first=M. J. D. |title= UOBYQA: unconstrained optimization by quadratic approximation|journal=Mathematical Programming |publisher= Springer|year=2002 |volume=92 |pages=555–582 |doi=10.1007/s101070100290}}</ref><ref name="code"/> A major difference between them is that [[UOBYQA]] constructs quadratic models by [[interpolation|interpolating]] the [[Optimization problem|objective function]] at <math> (n+1)(n+2)/2 </math> points.

NEWUOA software was released on December 16, 2004.<ref name="depository">{{cite web|url=http://mat.uc.pt/~zhang/software.html |title=A depository of Powell's software |publisher= |date= |accessdate=2014-01-14}}</ref> It can solve unconstrained optimization problems of a few hundreds variables to high precision without using [[derivatives]].<ref name="report"/> In the software, <math> m </math> is set to <math> 2n+1 </math> by default.<ref name="code">{{cite web|url=http://mat.uc.pt/~zhang/software/newuoa.zip |title=Source code of NEWUOA software |publisher= |date= |accessdate=2014-01-14}}</ref>

Other [[derivative-free optimization]] algorithms by [[Michael J. D. Powell|Powell]] include [[COBYLA]], [[UOBYQA]], [[BOBYQA]], and [[LINCOA]].<ref name="depository"/> [[BOBYQA]] and [[LINCOA]] are extensions of NEWUOA to bound constrained and linearly [[constrained optimization]] respectively.

[[Michael J. D. Powell|Powell]] did not explain how he coined the name "NEWUOA" either in the introducing report <ref name="report"/> or in the software,<ref name="code"/> although [[COBYLA]], [[UOBYQA]], [[BOBYQA]] and [[LINCOA]] are all named by [[acronyms]].

==See also==
*[[COBYLA]]
*[[LINCOA]]

==References==
{{Reflist}}

==External links==
*[http://mat.uc.pt/~zhang/software.html Source code of NEWUOA software]

{{optimization algorithms}}

[[Category:Optimization algorithms and methods]]

State-Transition Equation - Revision history

en>Dthomsen8: clean up, added orphan tag, typo(s) fixed: , → , (3) using AWB