An approximation algorithm for convex multi-objective programming problems

被引:61
作者
Ehrgott, Matthias [2 ]
Shao, Lizhen [1 ]
Schoebel, Anita [3 ]
机构
[1] Univ Sci & Technol Beijing, Sch Informat Engn, Beijing 100083, Peoples R China
[2] Univ Auckland, Dept Engn Sci, Auckland, New Zealand
[3] Univ Gottingen, Fak Math, Gottingen, Germany
关键词
Multi-objective optimization; Convex optimization; Approximation algorithm; epsilon-nondominated point; LINEAR-PROGRAMS;
D O I
10.1007/s10898-010-9588-7
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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 epsilon-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.
引用
收藏
页码:397 / 416
页数:20
相关论文
共 15 条
[1]  
[Anonymous], 2005, MULTICRITERIA OPTIMI
[2]  
Bazaraa M. S., 2006, NONLINEAR PROGRAMMIN
[3]   Hybrid approach for solving multiple-objective linear programs in outcome space [J].
Benson, HP .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1998, 98 (01) :17-35
[4]   An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem [J].
Benson, HP .
JOURNAL OF GLOBAL OPTIMIZATION, 1998, 13 (01) :1-24
[5]   ONLINE AND OFF-LINE VERTEX ENUMERATION BY ADJACENCY LISTS [J].
CHEN, PC ;
HANSEN, P ;
JAUMARD, B .
OPERATIONS RESEARCH LETTERS, 1991, 10 (07) :403-409
[6]   A survey of recent developments in multiobjective optimization [J].
Chinchuluun, Altannar ;
Pardalos, Panos M. .
ANNALS OF OPERATIONS RESEARCH, 2007, 154 (01) :29-50
[7]   Improved ε-constraint method for multiobjective programming [J].
Ehrgott, M. ;
Ruzika, S. .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2008, 138 (03) :375-396
[8]  
Ehrgott M., 2007, Report 654
[9]  
Ehrgott M, 2005, INT SER OPER RES MAN, V78, P667, DOI 10.1007/0-387-23081-5_17
[10]   PROPER EFFICIENCY AND THEORY OF VECTOR MAXIMIZATION [J].
GEOFFRION, AM .
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1968, 22 (03) :618-+