Skip navigation
Please use this identifier to cite or link to this item:
Title: Algorithms for Vector Optimization Problems
Authors: Ulus, Firdevs
Advisors: Rudloff, Birgit
Contributors: Operations Research and Financial Engineering Department
Keywords: Algorithms
Convex Programming
Linear Programming
Multiobjective optimization
Vector optimization
Subjects: Operations research
Issue Date: 2015
Publisher: Princeton, NJ : Princeton University
Abstract: This dissertation studies algorithms to solve linear and convex vector optimization problems. A parametric simplex algorithm for solving linear vector optimization problems (LVOPs) and two approximation algorithms for solving convex vector optimization problems (CVOPs) are provided. The algorithms work for any number of objectives and any solid polyhedral ordering cone. The parametric simplex algorithm can be seen as a variant of Evans-Steuer algorithm. Different from it, this algorithm does not aim to find the set of all efficient solutions, it finds a subset that generate the whole frontier. In that sense, it can also be seen as a generalization of the parametric self-dual simplex algorithm, which is designed for solving LPs, and is modified to solve bi-objective LVOPs. Numerical results are provided to compare the proposed algorithm with objective space based Benson's algorithm and with the Evans-Steuer algorithm. The results show that for non-degenerate problems the proposed algorithm outperforms Benson's algorithm and is on par with Evan-Steuer algorithm. For highly degenerate problems Benson's algorithm excels the simplex-type algorithms; however, the parametric simplex algorithm performs much better than Evans-Steuer algorithm. For solving convex vector optimization problems (CVOPs), two approximation algorithms are provided. Both algorithms solve the CVOP and its geometric dual problem simultaneously. The first algorithm is an extension of Benson's outer approximation algorithm, and the second one is a dual variant of it. Both algorithms provide an inner as well as an outer approximation of the (upper respectively lower) image. Only one scalar convex program has to be solved in each iteration. We allow objective and constraint functions that are not necessarily differentiable, allow solid pointed polyhedral ordering cones, and relate the approximations to an appropriate ε-solution concept. Some illustrative examples and also numerical results are provided for the approximation algorithms.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Ulus_princeton_0181D_11324.pdf2.65 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.