Journal of Optimization Theory and Applications Исследование операций и наука управления

An Optimally Fast Objective-Function-Free Minimization Algorithm Using Random Subspaces

Stefania Bellavia, Serge Gratton, Benedetta Morini, Philippe L. Toint
Springer Nature · 2026-05-01 · DOI 10.1007/s10957-026-03004-3

Аннотация

Abstract 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 convergence of the method or its evaluation complexity for the search of an $$\epsilon $$ ϵ -approximate first-order critical point, which is $$\mathcal {O}(\epsilon ^{-(p+1)/p})$$ O ( ϵ - ( p + 1 ) / p ) , where p is the order of derivatives used. A variant of the algorithm using approximate Hessian matrices is also analysed and shown to require at most $$\mathcal {O}(\epsilon ^{-2})$$ O ( ϵ - 2 ) evaluations. Preliminary numerical tests show that the random-subspace technique can significantly improve performance when used with $$p=2$$ p = 2 in the correct context.

Читать у издателя →