{
  "id": "1905.11228",
  "version": "v1",
  "published": "2019-05-27T13:56:34.000Z",
  "updated": "2019-05-27T13:56:34.000Z",
  "title": "Solving polyhedral d.c. optimization problems via concave minimization",
  "authors": [
    "Simeon vom Dahl",
    "Andreas Löhne"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-27T13:56:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C26",
      "90C29",
      "52B55"
    ],
    "keywords": [
      "optimization problem",
      "solving polyhedral",
      "global optimal solutions",
      "dual solution procedure",
      "concave minimization algorithms"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}