A New Adaptive Algorithm for

Convex Quadratic Multicriteria Optimization

by

Multicriteria optimization problems are a class of difficult optimization
problems in which several different objective functions have to be
taken care of at the same time. It will usually be the case that
no single point will minimize all of the several objective functions given at
once. Therefore, we are in search for so-called *efficient* points,
i. e. feasible points for which there does not exist a different
feasible point with the same or smaller objective function values such that
there is a strict decrease in at least one objective function value.
More precisely, let

be a function and let ( ) be the objective functions to be minimized. Then, an element is called

and

The set of all efficient points of the set is called the

The basic idea is as follows. Our aim is to compute a discrete approximation of the set of efficient points. By a standard scalarization approach, we have to solve a scalar optimization problem for each efficient point we want to compute. These different optimization problems we have to consider can be viewed as perturbations of each other, defined by a well-defined perturbation parameter.

We propose to use an adaptive discretization technique for the set of pertubations. Basically, we want to use more parameters in those regions of the parameter space where pertubations which are close together result in efficient points whose images in the image space are far apart from each other. We will introduce more parameters (i. e. more scalar problems) during the solution process of other scalar problems, even before these other problems are completely solved.

Furthermore, to save work when computing the new efficient points (i. e. when solving the new optimization problems), we propose to use a warm-start strategy. With such a strategy, points from the iteration history of scalar problems already considered (but not necessarily solved to optimality) are used as starting points for the optimization problems currently under consideration. In this way, even intermediate results obtained during a solution process form already a well-defined approximation to the set of efficient points.

The paper is therefore organized as follows. First, we derive a long-step interior-point algorithm for convex quadratic optimization problems subject to linear equality and inequality constraints that is able to use infeasible starting points. Then, perturbed optimization problems which stem form a standard scalarization approach for multicriteria problems are considered and a warm-start strategy for these problems are derived. After that, we describe a new efficient adaptive interior-point technique for solving convex quadratic multicriteria problems. Numerical results are presented and discussed, too. It turns out that the method is faster than a standard method for solving multicriteria optimization problems.