Randomized simplicial Hessian update

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	2021
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FE - Fakulteta za elektrotehniko
UDK:	004
COBISS:	87135235
ISSN:	2227-7390
Št. ogledov:	105
Št. prenosov:	47
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarne ključne besede:	optimizacija brez uporabe odvodov;posodabljanje Hessejeve matrike;naključne matrike;enakomerna porazdelitev;
Vrsta dela (COBISS):	Članek v reviji
Strani:	str. 1-18
Letnik:	ǂiss. ǂ15
Zvezek:	1775
Čas izdaje:	Aug.-1 2021
DOI:	10.3390/math9151775
ID:	14966945