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

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. Preliminary numerical tests show that the random-subspace technique can significantly improve performance on some problems, albeit, unsurprisingly, not for all.