Change search
ReferencesLink to record
Permanent link

Direct link
Derivate Free Optimization
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2014 (English)Report (Other academic)
Abstract [en]

During the last ten years, the speaker has developed Fortran software for minimizing general objective functions when first derivatives are not available. He has released two packages, namely NEWUOA and UOBYQA, for the unconstrained case and for simple upper and lower bounds on the variables, respectively. His current research addresses general linear constraints on the variables, which is intended to provide the new LINCOA package. These algorithms require only of magnitude n squared operations on a typical iteration, where n is the number of variables, which has allowed them to be applied when n is in the hundreds. No attention is given to sparsity.

Some excellent numerical results have been achieved, which certainly depend on the use of the symmetric Broyden updating formula. That formula when derivatives are not available is the subject of Lecture 1. It supplies the solution to the following variational problem. Some values of the objective function and a quadratic approximation to the objective function are given, where usually the approximation does not interpolate all the given function values. A new quadratic approximation is required that does interpolate the given function values. The freedom that remains in the new approximation is taken up by making as small as possible the Frobenius norm of the change to the second derivative  matrix of the approximation.

A trust region in the space of the variables is the set of all points that are within a prescribed distance of the best point so far. A typical change to the vector of variables is a move from the best point so far to a new point within the trust region, the new point being chosen to provide a relatively small value of the current quadratic approximation to the objective function. The calculation of the new point is the subject of Lecture 2. A version of truncated conjugate gradients is employed, in order that the amount of work is only of magnitude n2. Several decisions had to be taken to specify an algorithm. They are particularly interesting for the LINCOA software, due to the linear constraints on the variables.

Lectures 1 and 2 describe vital ingredients of the software that has been mentioned. A few more details are addressed in Lecture 3, to complete an outline of how the algorithms work. The numerical results from several test problems are considered too. The accuracy and efficiency are much better than expected if one takes the view that the second derivative matrix of the quadratic approximation should become close to the second derivative matrix of the objective function. We find clearly that this view is wrong. Also the numerical results show that good accuracy is achieved eventually, although the number of iterations is sometimes very sensitive to effects from computer rounding errors.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2014. , 26 p.
LiTH-MAT-R, ISSN 0348-2960 ; 2014:02
National Category
URN: urn:nbn:se:liu:diva-104548ISRN: LiTH-MAT-R--2014/02--SEOAI: diva2:697412
Available from: 2014-02-18 Created: 2014-02-18 Last updated: 2014-02-20Bibliographically approved

Open Access in DiVA

LiTH-MAT-R--2014/02--SE(1104 kB)126 downloads
File information
File name FULLTEXT03.pdfFile size 1104 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Optimization The Institute of Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 126 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 243 hits
ReferencesLink to record
Permanent link

Direct link