<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-approximate first-order critical point, which is <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {O}(\epsilon ^{-(p+1)/p})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mo stretchy="false">(</mo> <mi>p</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">/</mo> <mi>p</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>p</i> is the order of derivatives used. A variant of the algorithm using approximate Hessian matrices is also analysed and shown to require at most <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {O}(\epsilon ^{-2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> evaluations. Preliminary numerical tests show that the random-subspace technique can significantly improve performance when used with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$p=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> in the correct context.</p>

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

期刊论文
出版模式：

开放获取
发表日期：

2026年5月13日

查看全文

Stefania Bellavia,
Serge Gratton,
Benedetta Morini,
Philippe L. Toint

摘要

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.