Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Derivate Free Optimization
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
##### 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.

##### Series
LiTH-MAT-R, ISSN 0348-2960 ; 2014:02
Mathematics
##### Identifiers
ISRN: LiTH-MAT-R--2014/02--SEOAI: oai:DiVA.org:liu-104548DiVA, id: diva2:697412
Available from: 2014-02-18 Created: 2014-02-18 Last updated: 2014-02-20Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT03.pdfFile size 1104 kBChecksum SHA-512
8ec6158a131b4cf47d9e5a408d30b0537916d0be0364cb3520a40c817e498877594714e74fcdfd29a59cb994926c899dd5c1fe4a0e70e2dfae6c0ab1d62d61e4
Type fulltextMimetype application/pdf
##### By organisation
Optimization The Institute of Technology
Mathematics

#### Search outside of DiVA

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
urn-nbn

#### Altmetric score

urn-nbn
Total: 337 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
v. 2.33.0
|