Randomized simplicial Hessian update

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

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.

• Jezik: Angleški jezik
• Ključne besede: derivative-free optimization, Hessian update, random matrices, uniform distribution
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FE - Fakulteta za elektrotehniko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2021
• Št. strani: 18 str.
• Številčenje: Vol. 9, iss. 15, art. 1775
• PID: 20.500.12556/RUL-136022
• UDK: 004
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math9151775
• COBISS.SI-ID: 87135235
• Datum objave v RUL: 07.04.2022

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 01.08.2021

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: optimizacija brez uporabe odvodov, posodabljanje Hessejeve matrike, naključne matrike, enakomerna porazdelitev

Projekti

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: P2-0246
• Naslov: ICT4QoL - Informacijsko komunikacijske tehnologije za kakovostno življenje