Randomized simplicial Hessian update

Bűrmen, Árpád (author), Tuma, Tadej (author), Olenšek, Jernej (author)

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.

• Language: English
• Keywords: derivative-free optimization, Hessian update, random matrices, uniform distribution
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FE - Faculty of Electrical Engineering
• Publication status: Published
• Publication version: Version of Record
• Year: 2021
• Number of pages: 18 str.
• Numbering: Vol. 9, iss. 15, art. 1775
• PID: 20.500.12556/RUL-136022
• UDC: 004
• ISSN on article: 2227-7390
• DOI: 10.3390/math9151775
• COBISS.SI-ID: 87135235
• Publication date in RUL: 07.04.2022

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 01.08.2021

Secondary language

• Language: Slovenian
• Keywords: optimizacija brez uporabe odvodov, posodabljanje Hessejeve matrike, naključne matrike, enakomerna porazdelitev

Projects

• Funder: ARRS - Slovenian Research Agency
• Project number: P2-0246
• Name: ICT4QoL - Informacijsko komunikacijske tehnologije za kakovostno življenje