A convergence analysis of the method of codifferential descent
From MaRDI portal
Publication:1756589
DOI10.1007/S10589-018-0024-0zbMATH Open1416.90057arXiv1801.07766OpenAlexW2784408805MaRDI QIDQ1756589FDOQ1756589
Authors: Maxim Dolgopolik 
Publication date: 21 December 2018
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Abstract: This paper is devoted to a detailed convergence analysis of the method of codifferential descent (MCD) developed by professor V.F. Demyanov for solving a large class of nonsmooth nonconvex optimization problems. We propose a generalization of the MCD that is more suitable for applications than the original method, and that utilizes only a part of a codifferential on every iteration, which allows one to reduce the overall complexity of the method. With the use of some general results on uniformly codifferentiable functions obtained in this paper, we prove the global convergence of the generalized MCD in the infinite dimensional case. Also, we propose and analyse a quadratic regularization of the MCD, which is the first general method for minimizing a codifferentiable function over a convex set. Apart from convergence analysis, we also discuss the robustness of the MCD with respect to computational errors, possible step size rules, and a choice of parameters of the algorithm. In the end of the paper we estimate the rate of convergence of the MCD for a class of nonsmooth nonconvex functions that arises, in particular, in cluster analysis. We prove that under some general assumptions the method converges with linear rate, and it convergence quadratically, provided a certain first order sufficient optimality condition holds true.
Full work available at URL: https://arxiv.org/abs/1801.07766
Recommendations
- The method of codifferential descent for convex and global piecewise affine optimization
- scientific article; zbMATH DE number 5800584
- A method of truncated codifferential with application to some problems of cluster analysis
- Codifferential method for minimizing nonsmooth DC functions
- Aggregate codifferential method for nonsmooth DC optimization
nonconvex optimizationnonsmooth optimizationcodifferentialquasidifferentialmethod of codifferential descent
Nonconvex programming, global optimization (90C26) Nonsmooth analysis (49J52) Derivative-free methods and methods using generalized derivatives (90C56)
Cites Work
- A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
- Discrete gradient method: Derivative-free method for nonsmooth optimization
- Optimization. Algorithms and consistent approximations
- Comparing different nonsmooth minimization methods and software
- Calculus without derivatives
- A redistributed proximal bundle method for nonconvex optimization
- Optimization and nonsmooth analysis
- Title not available (Why is that?)
- Globally convergent limited memory bundle method for large-scale nonsmooth optimization
- Title not available (Why is that?)
- Nonsmooth optimization via quasi-Newton methods
- Introduction to Derivative-Free Optimization
- Survey of Bundle Methods for Nonsmooth Optimization
- A derivative-free approximate gradient sampling algorithm for finite minimax problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Quasidifferentiability and related topics. Dedicated to Prof. Franco Giannessi on his 65th birthday and to Prof. Diethard Pallaschke on his 60th birthday
- Quasidifferentiability and nonsmooth modelling in mechanics, engineering and economics
- Inhomogeneous convex approximations of nonsmooth functions
- On locally-Lipschitz quasi-differentiate functions in Banach-spaces
- Title not available (Why is that?)
- Title not available (Why is that?)
- A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization
- An adaptive gradient sampling algorithm for non-smooth optimization
- Codifferential calculus in normed spaces
- On the convergence of descent algorithms
- A Method for Minimization of Quasidifferentiable Functions
- A method of truncated codifferential with application to some problems of cluster analysis
- Introduction to nonsmooth optimization. Theory, practice and software
- A splitting bundle approach for non-smooth non-convex minimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Codifferential method for minimizing nonsmooth DC functions
- On the rate of convergence of certain methods of centers
- A multidimensional descent method for global optimization
- On necessary minimum conditions in quasidifferential calculus: independence of the specific choice of quasidifferentials
- Exact barrier function methods for Lipschitz programs
- A solution method for a special class of nondifferentiable unconstrained optimization problems
- Quadratic rate of convergence of a linearization method for solving discrete minimax problems
- Abstract convex approximations of nonsmooth functions
- Title not available (Why is that?)
- A limited-memory quasi-Newton algorithm for bound-constrained non-smooth optimization
- Title not available (Why is that?)
- Fréchet quasidifferential calculus with applications to metric regularity of continuous maps
- Aggregate codifferential method for nonsmooth DC optimization
- The method of confidence neighborhoods for minimizing codifferentiable functions
- Direct Methods in the Parametric Moving Boundary Variational Problem
- Nonsmooth problems of calculus of variations via codifferentiation
- Exact penalty functions in isoperimetric problems
- A characterization of continuously codifferentiable functions and some consequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (10)
- The quasidifferential descent method in a control problem with nonsmooth objective functional
- Numerical analysis of the orthogonal descent method
- Codifferentials and Quasidifferentials of the Expectation of Nonsmooth Random Integrands and Two-Stage Stochastic Programming
- Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization
- The method of codifferential descent for convex and global piecewise affine optimization
- Constrained nonsmooth problems of the calculus of variations
- A unified study of necessary and sufficient optimality conditions for minimax and Chebyshev problems with cone constraints
- New global optimality conditions for nonsmooth DC optimization problems
- Metric regularity of quasidifferentiable mappings and optimality conditions for nonsmooth mathematical programming problems
- A method of truncated codifferential with application to some problems of cluster analysis
Uses Software
This page was built for publication: A convergence analysis of the method of codifferential descent
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756589)
