Algorithms for Vector Optimization Problems

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.