A derivative-free comirror algorithm for convex optimization

作者：Bauschke Heinz H; Hare Warren L^*; Moursi Walaa M

来源：Optimization Methods and Software, 2015, 30(4): 706-726.

DOI：10.1080/10556788.2014.968158

• convex optimization
• derivative-free optimization
• lower-C-2
• approximate subgradient
• Non-Euclidean projected subgradient
• Bregman distance

We consider the minimization of a nonsmooth convex function over a compact convex set subject to a nonsmooth convex constraint. We work in the setting of derivative-free optimization (DFO), assuming that the objective and constraint functions are available through a black-box that provides function values for lower-C-2 representation of the functions. Our approach is based on a DFO adaptation of the -comirror algorithm [ Beck et al. The CoMirror algorithm for solving nonsmooth constrained convex problems, Oper. Res. Lett. 38( 6) ( 2010), pp. 493-498]. Algorithmic convergence hinges on the ability to accurately approximate subgradients of lower-C-2 functions, which we prove is possible through linear interpolation. We show that, if the sampling radii for linear interpolation are properly selected, then the new algorithm has the same convergence rate as the original gradient-based algorithm. This provides a novel global rate-of-convergence result for nonsmooth convex DFO with nonsmooth convex constraints. We conclude with numerical testing that demonstrates the practical feasibility of the algorithm and some directions for further research.

• 出版日期2015