An optimally fast objective-function-free minimization algorithm using random subspaces

Stefania Bellavia, Serge Gratton, Benedetta Morini, Philippe TOINT

Résultats de recherche: Papier de travailPréprint

6 Téléchargements (Pure)

Résumé

An algorithm for unconstrained non-convex optimization is described, which does not evaluate the objective function and in which minimization is carried out, at each iteration, within a randomly selected subspace. It is shown that this random approximation technique does not affect the method's convergence nor its evaluation complexity for the search of an $\epsilon$-approximate first-order critical point, which is $\mathcal{O}(\epsilon^{-(p+1)/p})$, where $p$ is the order of derivatives used. A variant of the algorithm using approximate Hessian matrices
is also analyzed and shown to require at most $\mathcal{O}(\epsilon^{-2})$ evaluations.
Preliminary numerical tests show that the random-subspace technique can significantly improve performance on some problems, albeit, unsurprisingly, not for all.
langue originaleAnglais
ÉditeurArxiv
Nombre de pages23
Volume2310.16580
Etat de la publicationPublié - 25 oct. 2023

Empreinte digitale

Examiner les sujets de recherche de « An optimally fast objective-function-free minimization algorithm using random subspaces ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation