Minimizing a Sum of Clipped Convex Functions
This work addresses a computationally challenging problem relevant to clipped empirical risk minimization and control, though it is incremental as it builds on existing methods for NP-hard optimization.
The paper tackles the problem of minimizing a sum of clipped convex functions, which is NP-hard, by proposing heuristics and a mixed-integer convex programming formulation to find approximate solutions and certify their proximity to the global optimum.
We consider the problem of minimizing a sum of clipped convex functions; applications include clipped empirical risk minimization and clipped control. While the problem of minimizing the sum of clipped convex functions is NP-hard, we present some heuristics for approximately solving instances of these problems. These heuristics can be used to find good, if not global, solutions and appear to work well in practice. We also describe an alternative formulation, based on the perspective transformation, which makes the problem amenable to mixed-integer convex programming and yields computationally tractable lower bounds. We illustrate one of our heuristic methods by applying it to various examples and use the perspective transformation to certify that the solutions are relatively close to the global optimum. This paper is accompanied by an open-source implementation.