A derivative-free algorithm for sparse unconstrained optimization problems

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceChapitre

Résumé

On considère le problème de la minimisation d'une fonction dont les dérivées ne sont pas disponibles. Cet article présente d'abord un algorithme pour résoudre des problèmes de cette classe en utilisant des polynômes d'interpolation et des techniques de régions de confiance. Nous montrons ensuite comment la structure de données et le procédure permettant de construire les polynômes d'interpolation peuvent être adaptées à des problèmes dont la matrice Hessienne est creuse de façon générale. Le bon comportement de l'algorithme résultant est confirmé par des tests numériques qui illustrent les avantages en termes d'espace mémoire, de vitesse et de nombre d'évaluations de fonctions, ce dernier critère étant particulièrement important dans le contexte de l'optimisation sans dérivées.
langue originaleAnglais
titreTrends in industrial and applied mathematics
Sous-titreProceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent
rédacteurs en chefA. H Siddiqi, M Kocvara
Lieu de publicationDordrecht
EditeurKluwer Academic Publishers
Pages131-147
Nombre de pages17
Volume72
étatPublié - 2002

Empreinte digitale

Derivative-free
Unconstrained Optimization
Derivative-free Optimization
Optimization Problem
Trust Region
Hessian matrix
Polynomial Interpolation
Evaluation Function
Sparsity
Data Structures
Numerical Experiment
Derivative
Polynomial
Framework
Class

Citer ceci

Colson, B., & Toint, P. (2002). A derivative-free algorithm for sparse unconstrained optimization problems. Dans A. H. Siddiqi, & M. Kocvara (eds.), Trends in industrial and applied mathematics: Proceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent (Vol 72, p. 131-147). Dordrecht: Kluwer Academic Publishers.
Colson, Benoit ; Toint, Philippe. / A derivative-free algorithm for sparse unconstrained optimization problems. Trends in industrial and applied mathematics: Proceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent. Editeur / A. H Siddiqi ; M Kocvara. Vol 72 Dordrecht : Kluwer Academic Publishers, 2002. p. 131-147
@inbook{81fd1274dc9d4eb68a4a83e4be69b3eb,
title = "A derivative-free algorithm for sparse unconstrained optimization problems",
abstract = "We consider the problem of minimizing a function whose derivatives are not available. This paper first presents an algorithm for solving problems of this class using interpolation polynomials and trust-region techniques. We then show how both the data structure and the procedure allowing to build the interpolating polynomials may be adapted in a suitable way to consider problems for which the Hessian matrix is known to be sparse with a general sparsity pattern. The favourable behaviour of the resulting algorithm is confirmed with numerical experiments illustrating the advantages of the method in terms of storage, speed and function evaluations, the latter criterion being particularly important in the framework of derivative-free optimization.",
keywords = "interpolation models, sparsity, trust-region methods, derivative-free optimization",
author = "Benoit Colson and Philippe Toint",
note = "Publication code : **RES. ACAD. Publication editors : A. H. Siddiqi and M. Kocvara",
year = "2002",
language = "English",
volume = "72",
pages = "131--147",
editor = "Siddiqi, {A. H} and M Kocvara",
booktitle = "Trends in industrial and applied mathematics",
publisher = "Kluwer Academic Publishers",

}

Colson, B & Toint, P 2002, A derivative-free algorithm for sparse unconstrained optimization problems. Dans AH Siddiqi & M Kocvara (eds), Trends in industrial and applied mathematics: Proceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent. VOL. 72, Kluwer Academic Publishers, Dordrecht, p. 131-147.

A derivative-free algorithm for sparse unconstrained optimization problems. / Colson, Benoit; Toint, Philippe.

Trends in industrial and applied mathematics: Proceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent. Ed. / A. H Siddiqi; M Kocvara. Vol 72 Dordrecht : Kluwer Academic Publishers, 2002. p. 131-147.

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceChapitre

TY - CHAP

T1 - A derivative-free algorithm for sparse unconstrained optimization problems

AU - Colson, Benoit

AU - Toint, Philippe

N1 - Publication code : **RES. ACAD. Publication editors : A. H. Siddiqi and M. Kocvara

PY - 2002

Y1 - 2002

N2 - We consider the problem of minimizing a function whose derivatives are not available. This paper first presents an algorithm for solving problems of this class using interpolation polynomials and trust-region techniques. We then show how both the data structure and the procedure allowing to build the interpolating polynomials may be adapted in a suitable way to consider problems for which the Hessian matrix is known to be sparse with a general sparsity pattern. The favourable behaviour of the resulting algorithm is confirmed with numerical experiments illustrating the advantages of the method in terms of storage, speed and function evaluations, the latter criterion being particularly important in the framework of derivative-free optimization.

AB - We consider the problem of minimizing a function whose derivatives are not available. This paper first presents an algorithm for solving problems of this class using interpolation polynomials and trust-region techniques. We then show how both the data structure and the procedure allowing to build the interpolating polynomials may be adapted in a suitable way to consider problems for which the Hessian matrix is known to be sparse with a general sparsity pattern. The favourable behaviour of the resulting algorithm is confirmed with numerical experiments illustrating the advantages of the method in terms of storage, speed and function evaluations, the latter criterion being particularly important in the framework of derivative-free optimization.

KW - interpolation models

KW - sparsity

KW - trust-region methods

KW - derivative-free optimization

M3 - Chapter

VL - 72

SP - 131

EP - 147

BT - Trends in industrial and applied mathematics

A2 - Siddiqi, A. H

A2 - Kocvara, M

PB - Kluwer Academic Publishers

CY - Dordrecht

ER -

Colson B, Toint P. A derivative-free algorithm for sparse unconstrained optimization problems. Dans Siddiqi AH, Kocvara M, rédacteurs en chef, Trends in industrial and applied mathematics: Proceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent. Vol 72. Dordrecht: Kluwer Academic Publishers. 2002. p. 131-147