A derivative-free algorithm for sparse unconstrained optimization problems

Benoit Colson; Philippe Toint

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érence › Chapitre

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 originale	Anglais
titre	Trends in industrial and applied mathematics
Sous-titre	Proceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent
rédacteurs en chef	A. H Siddiqi, M Kocvara
Lieu de publication	Dordrecht
Editeur	Kluwer Academic Publishers
Pages	131-147
Nombre de pages	17
Volume	72
Etat de la publication	Publié - 2002

1 Article

BFO, a trainable derivative-free Brute Force Optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables
Porcelli, M. & Toint, P., 30 juin 2017, Dans: Transactions of the American Methematical Society on Mathematical Software. 44, 1, 28 p., 6.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

File
47 Téléchargements (Pure)

2 Actif

DFO: Algorithmes d'optimisation numérique sans dérivées
TOINT, P., COLSON, B., Gratton, S., Tröltzsch, A. & RODRIGUES SAMPAIO, P.
1/03/94 → …
Projet: Recherche
ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. & TOINT, P.
1/01/87 → …
Projet: Axe de recherche

Trust-region algorithms for derivative-free optimization and nonlinear bilevel programming
Auteur: Colson, B., 2003
Superviseur: Toint, P. (Promoteur), Henrard, J. (Jury), Sartenaer, A. (Jury), Savard, G. (Personne externe) (Jury) & VICENTE, L. (Personne externe) (Jury)
Student thesis: Doc types › Docteur en Sciences

Contient cette citation

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",

address = "Netherlands",

}

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érence › Chapitre

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 -

A derivative-free algorithm for sparse unconstrained optimization problems

Résumé

Empreinte digitale

Résultat de recherche

BFO, a trainable derivative-free Brute Force Optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables

Projets

DFO: Algorithmes d'optimisation numérique sans dérivées

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire

Thèses de l'étudiant

Trust-region algorithms for derivative-free optimization and nonlinear bilevel programming

Contient cette citation