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

DOI10.1007/S10898-017-0519-8zbMATH Open1373.90075arXiv1610.05470OpenAlexW2536818598MaRDI QIDQ1679488FDOQ1679488

Authors: Andreas Löhne, Andrea Wagner 

Publication date: 9 November 2017

Published in: Journal of Global Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1610.05470

Recommendations

• Solving polyhedral d.c. optimization problems via concave minimization
• The DC (Difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems
• A method for solving d.c. programming problems. Application to fuel mixture nonconvex optimization problem
• Convex analysis approach to d. c. programming: Theory, algorithms and applications
• On solving a d.c. programming problem by a sequence of linear programs

zbMATH Keywords

global optimizationDC programmingmultiple objective linear programminglinear vector optimizationpolyhedral projection

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Multi-objective and goal programming (90C29)

Cites Work

• Vector Optimization with Infimum and Supremum
• DC programming: overview.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Location theory. A unified approach
• On minima of the difference of functions
• Duality in nonconvex optimization
• State Constraints in Convex Control Problems of Bolza
• Convex analysis and global optimization
• Geometrical properties of the Fermat-Weber problem
• A dual variant of Benson's ``outer approximation algorithm for multiple objective linear programming
• Title not available (Why is that?)
• Foundations of Optimization
• A Maxmin Location Problem
• Solving DC programs using the cutting angle method
• On functions representable as a difference of convex functions
• An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem
• The vector linear program solver Bensolve -- notes on theoretical background
• Solution concepts in vector optimization: a fresh look at an old story
• Equivalence between polyhedral projection, multiple objective linear programming and vector linear programming
• A Fenchel-Rockafellar type duality theorem for maximization
• A d.c. optimization method for single facility location problems
• Title not available (Why is that?)
• Using multiobjective optimization to map the entropy region
• The Weber Problem On The Plane With Some Negative Weights
• A General Formula on the Conjugate of the Difference of Functions
• A formula on the approximate subdifferential of the difference of convex functions
• Title not available (Why is that?)
• An expert decision-support system for option-based investment strategies
• Title not available (Why is that?)
• Conditions characterizing minima of the difference of functions
• Title not available (Why is that?)
• An extension of D.C. duality theory, with an appendix on ∗-subdifferentials

Cited In (5)

• Locating a semi-obnoxious facility in the special case of Manhattan distances
• A vector linear programming approach for certain global optimization problems
• Solving polyhedral d.c. optimization problems via concave minimization
• A norm minimization-based convex vector optimization algorithm
• Solving DC programs using the cutting angle method

Uses Software

• BENSOLVE

This page was built for publication: Solving DC programs with a polyhedral component utilizing a multiple objective linear programming solver

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679488)