Vector Optimization Problems, Algorithms and Financial Applications
Seminar by
Firdevs Ulus
Princeton University
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 it is possible to extent them to any polyhedral ordering cone C. The parametric simplex algorithm solves the LVOP as long as it has a solution. In each iteration, it provides a set of inequalities, which defines the current partition of the parameter space. In addition to the usual simplex arguments, one needs to eliminate the redundant inequalities from that set. This extra step is similar to yet simpler than the vertex enumeration procedure, which is used in most of the objective space based LVOP algorithms. Different from those, this algorithm doesn’t require to solve a scalar linear program in each iteration. The approximation 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 and lower) images. Only one scalar convex program has to be solved in each iteration. We allow objective and constraint functions that are not necessarily differentiable, and relate the approximations to an appropriate ε-solution concept. Some financial applications are provided.
