Finite Sample Behaviour of an Ergodically Fast Line-Search Algorithm

In order to represent a line-search algorithm as a non-convergent dynamic system, we perform a renormalisation of the uncertainty interval at each iteration. Its ergodic behaviour can then be studied, and it happens that, for locally symmetric functions, the asymptotic performances of the algorithm...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 1999-07, Vol.14 (1), p.75-86
Main Authors: Pronzato, L, Wynn, H P, Zhigljavsky, A A
Format: Article
Language:English
Subjects:
Algorithms
Codes
Linear programming
Mathematical analysis
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In order to represent a line-search algorithm as a non-convergent dynamic system, we perform a renormalisation of the uncertainty interval at each iteration. Its ergodic behaviour can then be studied, and it happens that, for locally symmetric functions, the asymptotic performances of the algorithm suggested are far better than those of the well-known GoldenSection algorithm. A proper tuning of internal parameters is then performed to obtain good performances for a finite number of iterations. The case of a function symmetric with respect to its optimum is considered first. An algorithm is presented, that only uses function comparisons, with a significant reduction of the number of comparisons required to reach a given precision when compared to the Golden Section algorithm. The robustness of these performances with respect to non-symmetry of the function is then checked by numerical simulations. [PUBLICATION ABSTRACT]
ISSN:0926-6003
1573-2894
DOI:10.1023/A:1008757012582