Solution methodologies for minimizing a sum of pointwise minima of two functions

In this paper, an NP-hard problem of minimizing a sum of pointwise minima of two functions is considered. Using a new equivalent formula, we propose a smooth approximation and an ADMM algorithm for solving the problem. In numerical experiments, we survey four methods including the algorithms proposed in this paper and the known methods. The results of numerical experiments indicate that the performance of each of algorithms could highly depend on the problem and simulation settings.