A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes

In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC re...

Full description

Saved in:
Bibliographic Details
Published in:Journal of global optimization 2017-07, Vol.68 (3), p.501-535
Main Authors: Joki, Kaisa, Bagirov, Adil M., Karmitsa, Napsu, Mäkelä, Marko M.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Approximation
Bundling
Computer Science
Convergence
Critical point
Cutting
Iterative methods
Mathematical analysis
Mathematics
Mathematics and Statistics
Methods
Operations Research/Decision Theory
Optimization
Planes
Programming
Real Functions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an ε -critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.
ISSN:0925-5001
1573-2916
DOI:10.1007/s10898-016-0488-3