165. Using relative errors for solving convex vector optimization problems
Invited abstract in session TC-5: Multiobjective Optimization 2: Continuous Problems, stream Decision Theory and Multi-criteria Decision Making.
Thursday, 11:45-13:15Room: H7
Authors (first author is the speaker)
| 1. | Daniel Dörfler
|
| Mathematics and Computer Science, Friedrich Schiller University Jena | |
| 2. | Andreas Löhne
|
| Institut für Mathematik, FSU Jena | |
| 3. | Rebecca Köhler
|
| Faculty of Mathematics and Computer Science , Friedrich Schiller University Jena |
Abstract
Approximately solving a convex vector optimization problem is done by approximating its upper image by finitely many points or polyhedra using any error measure to quantify the approximation quality. Only measures that depend on absolute error values are used in the literature, e.g. the Hausdorff distance for bounded problems, which don’t take the scale of the upper image or the fact, that objective function values may be of different scales, into account. In this talk we propose a solution concept that depends on relative errors to approximate the upper image. We show, that within a region depending on the approximation quality and a chosen reference point the distance between points of the approximation and weakly minimal points of the vector optimization problem can be bounded. This bound increases with the distance of the points to the reference point. Points outside of the region also carry information as they are close to weakly minimal points or recession directions of the upper image. The method is applicable to arbitrary convex vector optimization problems. In particular, boundedness or polyhedrality of the ordering cone are not required. We also compare the approach with solution concepts from the literature.
Keywords
- Multi-Objective Programming
- Convex Optimization
- Approximation Algorithms
Status: accepted
Back to the list of papers