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

DOI10.1080/10556788.2019.1668944zbMATH Open1443.90331arXiv1903.11184OpenAlexW2975502682MaRDI QIDQ5113714FDOQ5113714

Author name not available (Why is that?)

Publication date: 16 June 2020

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

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.

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• A discussion on variational analysis in derivative-free 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
• Manifold Sampling for Optimizing Nonsmooth Nonconvex Compositions
• A Derivative-Free Algorithm for Linearly Constrained Finite Minimax Problems
• 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

Uses Software

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

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)