A derivative-free comirror algorithm for convex optimization

DOI10.1080/10556788.2014.968158MaRDI QIDQ3458813zbMATH OpenOpenAlexFDO

Authors Heinz H. Bauschke, Walaa M. Moursi, Warren L. Hare

Publication date 28 December 2015

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.6403

zbMATH Keywords

approximate subgradientBregman distanceconvex optimizationderivative-free optimizationlower-\(\mathcal{C}^2\)non-Euclidean projected subgradient

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Derivative-free methods and methods using generalized derivatives (90C56)

Abstract: We consider $minf(x):g(x)le0,xinX,$ where $X$ is a compact convex subset of $R{R}^m$, and $f$ and $g$ are continuous convex functions defined on an open neighbourhood of $X$. We work in the setting of derivative-free optimization, assuming that $f$ and $g$ are available through a black-box that provides only function values for a lower-$mathcal{C}^2$ representation of the functions. We present a derivative-free optimization variant of the $eps$-comirror algorithm cite{BBTGBT2010}. Algorithmic convergence hinges on the ability to accurately approximate subgradients of lower-$mathcal{C}^2$ functions, which we prove is possible through linear interpolation. We provide convergence analysis that quantifies the difference between the function values of the iterates and the optimal function value. We find that the DFO algorithm we develop has the same convergence result as the original gradient-based algorithm. We present some numerical testing that demonstrate the practical feasibility of the algorithm, and conclude with some directions for further research.

Recommendations

• Model-based derivative-free methods for convex-constrained optimization
• A derivative-free trust-region algorithm for composite nonsmooth optimization
• A derivative-free \(\mathcal{V} \mathcal{U}\)-algorithm for convex finite-max problems
• scientific article; zbMATH DE number 1971709
• A derivative-free method for linearly constrained nonsmooth optimization

Cites work

• A Derivative-Free Algorithm for Linearly Constrained Finite Minimax Problems
• A derivative-free approximate gradient sampling algorithm for finite minimax problems
• An active-set trust-region method for derivative-free nonlinear bound-constrained optimization
• Benchmarking Derivative-Free Optimization Algorithms
• CONDOR, a new parallel, constrained extension of Powell's UOBYQA algorithm: Experimental results and comparison with the DFO algorithm
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Convex Analysis
• Derivative-free optimization methods for finite minimax problems
• Geometry of interpolation sets in derivative free optimization
• scientific article; zbMATH DE number 1972340 (Why is no real title available?)
• Introduction to Derivative-Free Optimization
• Mesh Adaptive Direct Search Algorithms for Constrained Optimization
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Objective-derivative-free methods for constrained optimization
• OrthoMADS: A Deterministic MADS Instance with Orthogonal Directions
• Sequential penalty derivative-free methods for nonlinear constrained optimization
• Smoothed analysis of \(\kappa(A)\)
• Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization
• The CoMirror algorithm for solving nonsmooth constrained convex problems
• The ordered subsets mirror descent optimization method with applications to tomography
• UOBYQA: unconstrained optimization by quadratic approximation
• Variational Analysis
• Worst case complexity of direct search

Cited in

(9)

• Compositions of convex functions and fully linear models
• Limiting behaviour of the generalized simplex gradient as the number of points tends to infinity on a fixed shape in \(\mathrm{IR}^n\)
• Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
• Model-based derivative-free methods for convex-constrained optimization
• A derivative-free \(\mathcal{V} \mathcal{U}\)-algorithm for convex finite-max problems
• Derivative-free optimization methods
• Linear convergence of the derivative-free proximal bundle method on convex nonsmooth functions, with application to the derivative-free \(\mathcal{VU}\)-algorithm
• A hybrid direct search and projected simplex gradient method for convex constrained minimization
• Nonsmooth projection-free optimization with functional constraints

This page was built for publication: A derivative-free comirror algorithm for convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3458813)