A derivative-free algorithm for sparse unconstrained optimization problems

Benoit Colson; Philippe Toint

A derivative-free algorithm for sparse unconstrained optimization problems

Research output: Contribution in Book/Catalog/Report/Conference proceeding › Chapter

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.

Original language	English
Title of host publication	Trends in industrial and applied mathematics
Subtitle of host publication	Proceedings of the 1st International conference on industrial and applied mathematics of the Indian subcontinent
Editors	A. H Siddiqi, M Kocvara
Place of Publication	Dordrecht
Publisher	Kluwer Academic Publishers
Pages	131-147
Number of pages	17
Volume	72
Publication status	Published - 2002

Keywords

interpolation models
sparsity
trust-region methods
derivative-free optimization

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 Jun 2017, In: Transactions of the American Methematical Society on Mathematical Software. 44, 1, 28 p., 6.
Research output: Contribution to journal › Article › peer-review

File
27 Downloads (Pure)

2 Active

DFO: Derivative free numerical algorithms for optimization
TOINT, P., COLSON, B., Gratton, S., Tröltzsch, A. & RODRIGUES SAMPAIO, P.
1/03/94 → …
Project: Research
ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization
Sartenaer, A. & TOINT, P.
1/01/87 → …
Project: Research Axis

Trust-region algorithms for derivative-free optimization and nonlinear bilevel programming
Author: Colson, B., 2003
Supervisor: Toint, P. (Supervisor), Henrard, J. (Jury), Sartenaer, A. (Jury), Savard, G. (External person) (Jury) & VICENTE, L. (External person) (Jury)
Student thesis: Doc types › Doctor of Sciences

Cite this

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. editor / A. H Siddiqi ; M Kocvara. Vol. 72 Dordrecht : Kluwer Academic Publishers, 2002. pp. 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",

}

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.

Research output: Contribution in Book/Catalog/Report/Conference proceeding › Chapter

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

Abstract

Keywords

Fingerprint

Research output

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

Projects

DFO: Derivative free numerical algorithms for optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

Student theses

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

Cite this