A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes
- Authors: Joki, Kaisa , Bagirov, Adil , Karmitsa, Napsu , Makela, Marko
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 68, no. 3 (2017), p. 501-535
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: 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.
Comparing different nonsmooth minimization methods and software
- Authors: Karmitsa, Napsu , Bagirov, Adil , Makela, Marko
- Date: 2012
- Type: Text , Journal article
- Relation: Optimization Methods and Software Vol. 27, no. 1 (2012), p. 131-153
- Relation: http://purl.org/au-research/grants/arc/DP0666061
- Full Text: false
- Reviewed:
- Description: Most nonsmooth optimization (NSO) methods can be divided into two main groups: subgradient methods and bundle methods. In this paper, we test and compare different methods from both groups as well as some methods which may be considered as hybrids of these two and/or some others. All the solvers tested are so-called general black box methods which, at least in theory, can be applied to solve almost all NSO problems. The test set includes a large number of unconstrained nonsmooth convex and nonconvex problems of different size. In particular, it includes piecewise linear and quadratic problems. The aim of this work is not to foreground some methods over the others but to get some insight on which method to select for certain types of problems. © 2012 Taylor and Francis Group, LLC.
Double bundle method for finding clarke stationary points in nonsmooth dc programming
- Authors: Joki, Kaisa , Bagirov, Adil , Karmitsa, Napsu , Makela, Marko , Taheri, Sona
- Date: 2018
- Type: Text , Journal article
- Relation: SIAM Journal on Optimization Vol. 28, no. 2 (2018), p. 1892-1919
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text:
- Reviewed:
- Description: The aim of this paper is to introduce a new proximal double bundle method for unconstrained nonsmooth optimization, where the objective function is presented as a difference of two convex (DC) functions. The novelty in our method is a new escape procedure which enables us to guarantee approximate Clarke stationarity for solutions by utilizing the DC components of the objective function. This optimality condition is stronger than the criticality condition typically used in DC programming. Moreover, if a candidate solution is not approximate Clarke stationary, then the escape procedure returns a descent direction. With this escape procedure, we can avoid some shortcomings encountered when criticality is used. The finite termination of the double bundle method to an approximate Clarke stationary point is proved by assuming that the subdifferentials of DC components are polytopes. Finally, some encouraging numerical results are presented.
Introduction to Nonsmooth Optimization : Theory, practice and software
- Authors: Bagirov, Adil , Karmitsa, Napsu , Makela, Marko
- Date: 2014
- Type: Text , Book
- Full Text: false
- Reviewed:
- Description: This book is the first easy-to-read text on nonsmooth optimization (NSO, not necessarily differentiable optimization). Soving these kinds of problems plays a critical role in many industrial applications and real-world modeling systems, for example in the context of image denoising, optimal control, neural network training, data mining, ecomonics, and computational chemistry and physics. The book covers both the theory and the numerical methods used in NSO, and provides an overview of different problems arising in the field. It is organized into three parts: 1. convex and nonconvex analysis and the theory of NSO; 2. test problems and practical applications; 3. a guide to NSO software. The book is ideal for anyone teaching or attending NSO courses. As an accessible introduction to the field, it is also well suited as an independent learning guide for practitioners already familiar with the basics of optimization.
Subgradient and bundle methods for nonsmooth optimization
- Authors: Makela, Marko , Karmitsa, Napsu , Bagirov, Adil
- Date: 2013
- Type: Text , Book chapter
- Relation: Numerical methods for differential equations, optimization, and technological problems p.
- Full Text: false
- Reviewed:
- Description: The nonsmooth optimization methods can mainly be divided into two groups: subgradient and bundle methods. Usually, when developing new algorithms and testing them, the comparison is made between similar kinds of methods. The goal of this work is to test and compare different bundle and subgradient methods as well as some hybrids of these two and/or some others. The test set included a large amount of different unconstrained nonsmooth minimization problems, e.g., convex and nonconvex problems, piecewise linear and quadratic problems, and problems with different sizes. Rather than foreground some method over the others, our aim is to get some insight on which method is suitable for certain types of problems.