An approximation algorithm for convex multi-objective programming problems |
| |
Authors: | Matthias Ehrgott Lizhen Shao Anita Schöbel |
| |
Institution: | 1.Department of Engineering Science,The University of Auckland,Auckland,New Zealand;2.School of Information Engineering,University of Science and Technology Beijing,Beijing,China;3.Fakult?t für Mathematik,Georg-August Universit?t G?ttingen,G?ttingen,Germany |
| |
Abstract: | In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method
for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and
the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear
programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to
carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible
set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable
objectives or constraints. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|