Aggregate subgradient method for nosmooth DC optimization

"If there is a problem you can't solve, then there is an easier problem you can solve: find it."
- George Polya

AggSub

AggSub is a subgradient based solver for unconstrained nonsmooth DC (difference of two convex functions) optimization. The method consists of inner and outer iterations. In inner iterations null steps are carried out to find search directions. At each step of the inner iterations only two subgradients are used to calculate search directions: the aggregate subgradient and the subgradient calculated using the current direction. In outer iterations either serious steps are performed to move into a point with lower value of the objective or the parameters of the method are updated. It is proved that limit points of the sequence generated by the AggSub are critical points of the objective and the number of null steps in the inner iterations is finite.

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 (Fortran95)

 tsubgdc.f95 - Main program for AggSub. - Double precision and some other parameters. - User-specified DC components f_1 and f_2 together with subgradients of DC components. Contains also user-specified initial values for parameters. - AggSub method. - Makefile. - All the above in compressed form.

To use the software modify tsubgdc.f95 and functions.f95 as needed. The Fortran95 code is implemented by Kaisa Joki. If you have any questions conserning the implemetation, please contact her directly.

Code (Python)

aggsubpy.zip - Python implementation of the AggSub in compressed form.

Note that we highly recomment to use the Fortran implementation as it outperforms the Python implementation 100-0.

References

• A. Bagirov, S. Taheri, K. Joki, N. Karmitsa, M.M. Mäkelä, "Aggregate subgradient method for nonsmooth DC optimization", Optimization Letters, to appear, 2020.
• A. Bagirov, S. Taheri, K. Joki, N. Karmitsa, M.M. Mäkelä, "A new subgradient based method for nonsmooth DC programming", TUCS Technical Report, No. 1201, Turku Centre for Computer Science, Turku, 2019.

Acknowledgements

The work was financially supported by the Australian Research Counsil’s Discovery Projects funding scheme (Project No. DP190100580), Academy of Finland (Project No. 289500, 313266), and University of Turku.