A derivative-free V U-algorithm for convex finite-max problems

DOI10.1080/10556788.2019.1668944MaRDI QIDQ5113714zbMATH OpenOpenAlexFDO

Authors

Publication date 16 June 2020

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

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

zbMATH Keywords

convex minimizationderivative-free optimizationproximal-point mappingfinite-max function\(\mathcal{U}\)-gradient\(\mathcal{U}\)-Hessian\(\mathcal{V} \mathcal{U}\)-algorithm\(\mathcal{V} \mathcal{U}\)-decomposition

Mathematics Subject Classification ID

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

Abstract: The $mathcalVU$-algorithm is a superlinearly convergent method for minimizing nonsmooth, convex functions. At each iteration, the algorithm works with a certain $mathcalV$-space and its orthogonal $U$-space, such that the nonsmoothness of the objective function is concentrated on its projection onto the $mathcalV$-space, and on the $mathcalU$-space the projection is smooth. This structure allows for an alternation between a Newton-like step where the function is smooth, and a proximal-point step that is used to find iterates with promising $mathcalVU$-decompositions. We establish a derivative-free variant of the $mathcalVU$-algorithm for convex finite-max objective functions. We show global convergence and provide numerical results from a proof-of-concept implementation, which demonstrates the feasibility and practical value of the approach. We also carry out some tests using nonconvex functions and discuss the results.

Recommendations

• A derivative-free comirror algorithm for convex optimization
• Derivative-free optimization methods for finite minimax problems
• A derivative-free approximate gradient sampling algorithm for finite minimax problems
• A Derivative-Free Algorithm for Linearly Constrained Finite Minimax Problems
• Numerical analysis of \(\mathcal{VU}\)-decomposition, \(\mathcal{U}\)-gradient, and \(\mathcal{U}\)-Hessian approximations

Cites work

• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• scientific article; zbMATH DE number 1274356 (Why is no real title available?)
• scientific article; zbMATH DE number 1971709 (Why is no real title available?)
• scientific article; zbMATH DE number 1568991 (Why is no real title available?)
• scientific article; zbMATH DE number 1873048 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 1424528 (Why is no real title available?)
• A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization
• A Proximal Bundle Method with Approximate Subgradient Linearizations
• A Spectral Bundle Method for Semidefinite Programming
• A \(\mathcal{VU}\)-algorithm for convex minimization
• A derivative-free approximate gradient sampling algorithm for finite minimax problems
• A doubly stabilized bundle method for nonsmooth convex optimization
• A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization
• A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes
• A proximal bundle method for nonsmooth nonconvex functions with inexact information
• A proximal method for composite minimization
• A proximity control algorithm to minimize nonsmooth and nonconvex functions
• A survey on direct search methods for blackbox optimization and their applications
• Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm
• Benchmarking Derivative-Free Optimization Algorithms
• Bundle methods for sum-functions with ``easy components: applications to multicommodity network design
• Composite proximal bundle method
• Computing proximal points of convex functions with inexact subgradients
• Continuity theory
• Convergence of some algorithms for convex minimization
• Convex proximal bundle methods in depth: a unified analysis for inexact oracles
• Derivative-free and blackbox optimization
• Derivative-free optimization methods for finite minimax problems
• Derivative-free optimization via proximal point methods
• Developments of NEWUOA for minimization without derivatives
• Discrete gradient method: Derivative-free method for nonsmooth optimization
• Gradients of Convex Functions
• Implicit filtering
• Introduction to Derivative-Free Optimization
• Level bundle methods for constrained convex optimization with various oracles
• Manifold sampling for \(\ell_1\) nonconvex optimization
• Mesh Adaptive Direct Search Algorithms for Constrained Optimization
• New diagonal bundle method for clustering problems in large data sets
• Nonsmooth bundle trust-region algorithm with applications to robust stability
• Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search
• Numerical analysis of \(\mathcal{VU}\)-decomposition, \(\mathcal{U}\)-gradient, and \(\mathcal{U}\)-Hessian approximations
• Numerical optimization. Theoretical and practical aspects. Transl. from the French
• Numerical recipes. The art of scientific computing.
• On \(\mathcal{VU}\)-theory for functions with primal-dual gradient structure
• On the differentiability check in gradient sampling methods
• On the local convergence analysis of the gradient sampling method for finite max-functions
• Optimizing damper connectors for adjacent buildings
• OrthoMADS: A Deterministic MADS Instance with Orthogonal Directions
• Primal-Dual Gradient Structured Functions: Second-Order Results; Links to Epi-Derivatives and Partly Smooth Functions
• Proximal bundle methods for nonsmooth DC programming
• Proximal splitting methods in signal processing
• Proximity control in bundle methods for convex nondifferentiable minimization
• The spectral bundle method with second-order information
• The 𝒰-Lagrangian of a convex function
• Using Sampling and Simplex Derivatives in Pattern Search Methods
• Variational Analysis
• 𝒱𝒰-smoothness and proximal point results for some nonconvex functions

Cited in

(14)

• A discussion on variational analysis in derivative-free optimization
• scientific article; zbMATH DE number 1424528 (Why is no real title available?)
• A derivative-free comirror algorithm for convex optimization
• Linear convergence of the derivative-free proximal bundle method on convex nonsmooth functions, with application to the derivative-free \(\mathcal{VU}\)-algorithm
• Conditions for the existence, identification and calculus rules of the threshold of prox-boundedness
• Compositions of convex functions and fully linear models
• A derivative-free approximate gradient sampling algorithm for finite minimax problems
• A hybrid direct search and projected simplex gradient method for convex constrained minimization
• A Derivative-Free Algorithm for Linearly Constrained Finite Minimax Problems
• Numerical analysis of \(\mathcal{VU}\)-decomposition, \(\mathcal{U}\)-gradient, and \(\mathcal{U}\)-Hessian approximations
• Manifold sampling for optimizing nonsmooth nonconvex compositions
• A derivative-free trust-region algorithm with copula-based models for probability maximization problems
• A \(\mathcal{VU}\)-algorithm for convex minimization
• Derivative-free optimization methods

Describes a project that uses

Uses Software

• OrthoMADS
• UNLocBoX
• DGM
• SQPlab
• KELLEY
• IMFIL
• PLCP
• DFO
• NEWUOA

This page was built for publication: A derivative-free \(\mathcal{V} \mathcal{U}\)-algorithm for convex finite-max problems

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