The method of codifferential descent for convex and global piecewise affine optimization

DOI10.1080/10556788.2019.1571590MaRDI QIDQ5859002zbMATH OpenOpenAlexWikidataFDO

Authors Maxim Dolgopolik

Publication date 15 April 2021

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

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

zbMATH Keywords

codifferentialconvex optimizationglobal optimality conditionsmethod of codifferential descentpiecewise affine optimization

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Abstract: The class of nonsmooth codifferentiable functions was introduced by professor V.F.~Demyanov in the late 1980s. He also proposed a method for minimizing these functions called the method of codifferential descent (MCD). However, until now almost no theoretical results on the performance of this method on particular classes of nonsmooth optimization problems were known. In the first part of the paper, we study the performance of the method of codifferential descent on a class of nonsmooth convex functions satisfying some regularity assumptions, which in the smooth case are reduced to the Lipschitz continuity of the gradient. We prove that in this case the MCD has the iteration complexity bound $mathcalO(1/varepsilon)$. In the second part of the paper we obtain new global optimality conditions for piecewise affine functions in terms of codifferentials. With the use of these conditions we propose a modification of the MCD for minimizing piecewise affine functions (called the method of global codifferential descent) that does not use line search, and discards those "pieces" of the objective functions that are no longer useful for the optimization process. Then we prove that the MCD as well as its modification proposed in the article find a point of global minimum of a nonconvex piecewise affine function in a finite number of steps.

Recommendations

• A convergence analysis of the method of codifferential descent
• scientific article; zbMATH DE number 5800584
• Codifferential method for minimizing nonsmooth DC functions
• Finding the set of global minimizers of a piecewise affine function
• Aggregate codifferential method for nonsmooth DC optimization

Cites work

• A convergence analysis of the method of codifferential descent
• A doubly stabilized bundle method for nonsmooth convex optimization
• A method of truncated codifferential with application to some problems of cluster analysis
• A Proximal Bundle Method with Approximate Subgradient Linearizations
• A subgradient method based on gradient sampling for solving convex optimization problems
• Abstract convex approximations of nonsmooth functions
• Aggregate codifferential method for nonsmooth DC optimization
• Codifferential calculus in normed spaces
• Codifferential method for minimizing nonsmooth DC functions
• Conditions for global optimality. II
• Direct Methods in the Parametric Moving Boundary Variational Problem
• Exact penalty functions in isoperimetric problems
• Finding the distance between ellipsoids
• Gradient methods for minimizing composite functions
• scientific article; zbMATH DE number 5800584 (Why is no real title available?)
• scientific article; zbMATH DE number 4069674 (Why is no real title available?)
• scientific article; zbMATH DE number 16306 (Why is no real title available?)
• scientific article; zbMATH DE number 16313 (Why is no real title available?)
• scientific article; zbMATH DE number 477581 (Why is no real title available?)
• scientific article; zbMATH DE number 1376935 (Why is no real title available?)
• scientific article; zbMATH DE number 1568960 (Why is no real title available?)
• scientific article; zbMATH DE number 872150 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Lectures on Polytopes
• Methods of subdifferential and hypodifferential descent in the problem of constructing an integrally constrained program control
• On global unconstrained minimization of the difference of polyhedral functions
• On the global convergence of a nonmonotone proximal bundle method for convex nonsmooth minimization
• OSGA: a fast subgradient algorithm with optimal complexity
• Piecewise affine functions and polyhedral sets^∗
• Piecewise affine functions as a difference of two convex functions
• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• Smooth minimization of non-smooth functions
• Survey of Bundle Methods for Nonsmooth Optimization
• Universal gradient methods for convex optimization problems

Cited in

(7)

• A method of truncated codifferential with application to some problems of cluster analysis
• A convergence analysis of the method of codifferential descent
• New global optimality conditions for nonsmooth DC optimization problems
• Finding the set of global minimizers of a piecewise affine function
• Equivalence of two optimality conditions for polyhedral functions
• Nonlocal error bounds for piecewise affine functions
• Hypodifferentials of nonsmooth convex functions and their applications to nonsmooth convex optimization

Describes a project that uses

Uses Software

• NESUN

This page was built for publication: The method of codifferential descent for convex and global piecewise affine optimization

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