Randomized simplicial Hessian update

Arpad Bürmen (Author), Tadej Tuma (Author), Jernej Olenšek (Author)

Abstract

Recently, a derivative-free optimization algorithm was proposed that utilizes a minimum Frobenius norm (MFN) Hessian update for estimating the second derivative information, which in turn is used for accelerating the search. The proposed update formula relies only on computed function values and is a closed-form expression for a special case of a more general approach first published by Powell. This paper analyzes the convergence of the proposed update formula under the assumption that the points from $\mathbb{R}^n$ where the function value is known are random. The analysis assumes that the N + 2 points used by the update formula are obtained by adding N + 1 vectors to a central point. The vectors are obtained by transforming a prototype set of N + 1 vectors with a random orthogonal matrix from the Haar measure. The prototype set must positively span a N ≤ n dimensional subspace. Because the update is random by nature we can estimate a lower bound on the expected improvement of the approximate Hessian. This lower bound was derived for a special case of the proposed update by Leventhal and Lewis. We generalize their result and show that the amount of improvement greatly depends on N as well as the choice of the vectors in the prototype set. The obtained result is then used for analyzing the performance of the update based on various commonly used prototype sets. One of the results obtained by this analysis states that a regular n-simplex is a bad choice for a prototype set because it does not guarantee any improvement of the approximate Hessian.

Keywords

otimizacija brez uporabe odvodov;posodabljanje Hessejeve matrike;naključne matrike;enakomerna porazdelitev;derivate-free optimization;Hessian update;random matrices;uniform distribution;

Data

Language:	English
Year of publishing:	2021
Typology:	1.01 - Original Scientific Article
Organization:	UL FE - Faculty of Electrical Engineering
UDC:	004
COBISS:	87135235
ISSN:	2227-7390
Views:	105
Downloads:	47
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary keywords:	optimizacija brez uporabe odvodov;posodabljanje Hessejeve matrike;naključne matrike;enakomerna porazdelitev;
Type (COBISS):	Article
Pages:	str. 1-18
Volume:	ǂiss. ǂ15
Issue:	1775
Chronology:	Aug.-1 2021
DOI:	10.3390/math9151775
ID:	14966945