Home > Research > Publications & Outputs > An approximation algorithm for convex multi-obj...

Research

Links

Text available via DOI:

Keywords

View graph of relations

An approximation algorithm for convex multi-objective programming problems

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

An approximation algorithm for convex multi-objective programming problems. / Ehrgott, Matthias; Shao, Lizhen; Schöbel, Anita.
In: Journal of Global Optimization, Vol. 50, No. 3, 01.07.2011, p. 397-416.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Ehrgott, M, Shao, L & Schöbel, A 2011, 'An approximation algorithm for convex multi-objective programming problems', Journal of Global Optimization, vol. 50, no. 3, pp. 397-416. https://doi.org/10.1007/s10898-010-9588-7

APA

Ehrgott, M., Shao, L., & Schöbel, A. (2011). An approximation algorithm for convex multi-objective programming problems. Journal of Global Optimization, 50(3), 397-416. https://doi.org/10.1007/s10898-010-9588-7

Vancouver

Ehrgott M, Shao L, Schöbel A. An approximation algorithm for convex multi-objective programming problems. Journal of Global Optimization. 2011 Jul 1;50(3):397-416. doi: 10.1007/s10898-010-9588-7

Author

Ehrgott, Matthias ; Shao, Lizhen ; Schöbel, Anita. / An approximation algorithm for convex multi-objective programming problems. In: Journal of Global Optimization. 2011 ; Vol. 50, No. 3. pp. 397-416.

Bibtex

@article{96386a20c2454c12a3f1ee752a665a53,
title = "An approximation algorithm for convex multi-objective programming problems",
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{\textquoteright}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 = "Multi-objective optimization , Convex optimization , Approximation algorithm , ε-nondominated point",
author = "Matthias Ehrgott and Lizhen Shao and Anita Sch{\"o}bel",
year = "2011",
month = jul,
day = "1",
doi = "10.1007/s10898-010-9588-7",
language = "English",
volume = "50",
pages = "397--416",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Netherlands",
number = "3",

}

RIS

TY - JOUR

T1 - An approximation algorithm for convex multi-objective programming problems

AU - Ehrgott, Matthias

AU - Shao, Lizhen

AU - Schöbel, Anita

PY - 2011/7/1

Y1 - 2011/7/1

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

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

KW - Multi-objective optimization

KW - Convex optimization

KW - Approximation algorithm

KW - ε-nondominated point

U2 - 10.1007/s10898-010-9588-7

DO - 10.1007/s10898-010-9588-7

M3 - Journal article

VL - 50

SP - 397

EP - 416

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 3

ER -