Solving polyhedral d.c. optimization problems via concave minimization

Simeon vom Dahl, Andreas Löhne

Published 2019-05-27Version 1

The problem of minimizing the difference $g-h$ of two convex functions $g$ and $h$ is called polyhedral d.c. optimization problem if at least one of the two functions is polyhedral. We characterize the existence of global optimal solutions of polyhedral d.c. optimization problems. This result is used to show that, whenever the existence of an optimal solution can be certified, polyhedral d.c. optimization problems can be solved by certain concave minimization algorithms. No further assumptions are necessary in case of $g$ being polyhedral and just some mild assumptions to $g$ are required for the case where $h$ is polyhedral. In case of both functions being polyhedral, we obtain a primal and dual existence test and a primal and dual solution procedure. Numerical examples are discussed.