TY - JOUR

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

AU - Wagner, Andrea

AU - Löhne, Andreas

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://rdcu.be/vVCd

U2 - 10.1007/s10898-017-0519-8

DO - 10.1007/s10898-017-0519-8

M3 - Journal article

SN - 0925-5001

SP - 1

EP - 17

JO - Journal of Global Optimization

JF - Journal of Global Optimization

ER -