Solving DC programs with a polyhedral component utilizing a multiple objective linear programming solver

Abstract

A class of non-convex optimization problems with DC objective function is studied, where DC stands for being representable as the difference $f=g-h$ of two convex functions $g$ and $h$. In particular, we deal with the special case where one of the two convex functions $g$ or $h$ is polyhedral. In case $g$ is polyhedral, we show that a solution of the DC program can be obtained from a solution of an associated polyhedral projection problem. In case $h$ is polyhedral, we prove that a solution of the DC program can be obtained by solving a polyhedral projection problem and finitely many convex programs. Since polyhedral projection is equivalent to multiple objective linear programming (MOLP), a MOLP solver (in the second case together with a convex programming solver) can be used to solve instances of DC programs with polyhedral component. Numerical examples are provided, among them an application to locational analysis.

2nd version: some typos corrected, some remarks added, update of references