Bundle enrichment method for nosmooth DC optimization
BEM-DC
Bundle enrichment method (BEM-DC) is an algorithm for solving nonsmooth difference of convex (DC) programming problems. The novelty of the method consists of the dynamic management of the bundle. More specifically, a DC model, being the difference of two convex piecewise affine functions is formulated. The (global) minimization of the model is tackled by solving a set of convex problems whose cardinality depends on the number of linearizations adopted to approximate the second DC component function. The new bundle management policy distributes the information coming from previous iterations to separately model the DC components of the objective function. Such a distribution is driven by sign of linearization errors. If the displacement suggested by the model minimization provides no sufficient decrease of the objective function, then the temporary enrichment of the cutting plane approximation of just the first DC component function takes a place until either the termination of the algorithm is certified or a sufficient decrease is achieved. The most remarkable feature of the BEM-DC is that it uses less subgradient evaluations of the second DC components than any other method. This feature makes the proposed method different from other methods.
The software is free for academic teaching and research purposes but I ask you to refer the reference given below if you use it.
Code
| bem.f03 | - Main program for BEM-DC. |
|---|---|
| initbem.f03 | - Initialization of parameters for BEM-DC. |
| parameters.f03 | - Global parameters and constants. |
| functions.f03 | - User-specified DC components f_1 and f_2 together with subgradients of DC components. Contains also user-specified starting points. Includes now some test examples. |
| plqdf.f | - Quadratic solver by L. Luksan. |
| Makefile | - Makefile. |
| bem-dc.zip | - All the above in compressed form. |
| ReadMe | - Instruction file. |
To use the software give your functions and starting point in functions.f03. If you want to tune other parameters, modify initbem.f03.
References
- M. Gaudioso, S. Taheri, A. Bagirov, and N. Karmitsa, "Bundle Enrichment Method for Nonsmooth Difference ofConvex Programming Problems", In "Special Issue ”Numerical Optimization in Honor of the 60th Birthday of Marko M. Mäkelä" of Algorithms, 16, 394, 2023. https://doi.org/10.3390/a16080394.
