|
Article Excerpt
In multicriteria optimization, several objective functions have to be minimized simultaneously. We propose a new efficient method for approximating the solution set of a multicriteria optimization problem, where the objective functions involved are arbitrary convex functions and the set of feasible points is convex. The method is based on generating warm-start points for an efficient interior-point algorithm, while the approximation computed consists of a finite set of discrete points. Polynomial-time complexity results for the method proposed are derived. In these estimates, the number of operations per point decreases when the number of points generated for the approximation increases. This reduced theoretical complexity estimate is a novel feature and is not observed in standard solution techniques for multicriteria optimization problems.
Key words: convex multicriteria optimization; interior point; polynomial time MSC2000 subject classification: Primary: 90C51; secondary: 90C29, 90C60 OR/MS subject classification: Primary: programming (multiple criteria); secondary: programming (nonlinear, algorithms) History: Received February 25, 2004; revised August 30, 2005, January 27, 2006, and March 26, 2006.
1. Introduction.
1.1. Preliminaries. In multicriteria optimization (also known as multiobjective or vector optimization), several conflicting objective functions have to be minimized simultaneously. Applications for this problem type are abundant (see, e.g., Haimes and Steuer [16], Hillermeier [20], Fliege and Heseler [9], and Koksalan and Zionts [26] and the references contained therein). In general, no single point will minimize all those objective functions simultaneously. For this reason, a feasible point is defined as efficient (i.e., optimal in a multicriteria sense) if 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. As a consequence, different efficient points of a multicriteria problem will be incomparable to each other in terms of the order defined above. Due to this, no single point can represent the whole solution set, which will usually be quite large. Therefore, it is important to gain as much information as possible about the solution set of a given problem, preferably by constructing a well-defined approximation to it. This is the subject of this paper.
The necessity for constructing a well-defined approximation to the set of efficient points was also observed by various other authors, e.g., Benson and Sayin [1], Das and Dennis [6, 5], Hillermeier [20], Fliege and Heseler [9], Fliege [8], and the references contained therein. However, only in Fliege and Heseler [9] the method under consideration is subject to a worst-case analysis with respect to its computational complexity. Berkelaar [2] and Berkelaar et al. [3] propose a basis identification algorithm based on interior-point methodology for convex quadratic bicriteria optimization problems. These results where further generalized by Hadigheh et al. [15]. However, since these algorithms compute combinatorial information of all optimal bases of the solutions, it is not clear if they are computationally or theoretically efficient.
We will present an algorithm for approximating the solution set of a convex multicriteria optimization problem and focus on polynomial-time worst-case complexity estimates for the number of steps executed. Each step will involve only one Newton step, i.e., the solution of one linear system of equations as well as the corresponding function evaluations. These estimates will confirm that the number of operations per point generated decreases when the number of points generated for the approximation increases. This reduced theoretical complexity estimate is a novel feature and is not observed in standard solution techniques for multicriteria optimization problems.
For reasons that will become clear during the derivation of the algorithms presented, we will use a O-free notation throughout the whole paper (apart from a few concluding remarks at the end of [section]3). While this results in a slightly more cumbersome notation, ultimately it allows for a far more comprehensive treatment of the various estimates that lead to the final complexity result presented in this paper. This, in turn, will facilitate a better understanding of the derivation of the results.
1.2. Convex multicriteria optimization.
1.1.1. The problem. Let there be given a compact, convex set of feasible points G [subset] [subset][R.sup.m] with G [not equal to] [empty set] and n > 1 convex objective functions
[f.sub.i]: G [right arrow]R, i = l, ..., n. (1)
We are interested in minimizing simultaneously the functions [f.sub.i] on the set G in a sense to be specified as follows. We have to define the notion of a solution to the given multicriteria problem. We do this by defining minimal elements of an arbitrary set in the image space of the function f: G [right arrow] [R.sup.n] defined by f = ([f.sub.1], ..., [f.sub.n)[??].
DEFINITION 1.1. Let M [??] [R.sup.n] be a nonempty set. The element [y.sup.*] [member of] M is called efficient (or Pareto optimal) if and only if there is no other y 6 M with
[y.sub.i] [less than or equal to] [y.sup.*.sub.i] [for all]i[member of]{1,2, ..., n}
and
[Y.sub.k] < [Y.sup.*.sub.k] for at least one k [member of] {1, 2 , ..., n}.
The set of all efficient points of the set M is called the efficient set E(M).
With this definition, it becomes clear that in multicriteria optimization we are in search for the whole set E(f(G)) and, obviously, for the corresponding set of optimal decision variables [f.sup.-1](E(f(G))). Now, note that two efficient points f([x.sup.(1)])), f([x.sup.(2)]) [member of] E(f(G)) ([x.sup.(1)], [x.sup.(2)] [member of] G) with f([x.sup.(1)]) [not equal to] f([x.sup.(2)]) are incomparable to each other. By their very nature of being efficient, there exist two indices i, j [member of] {1, ..., n} such that [f.sub.i]([x.sup.(1)] < [f.sub.i]([x.sup.(2)]) and [f.sub.j](x(2)) < [f.sub.j]([x.sup.(1)]). Therefore, just one efficient point can hardly capture the possible optimal alternatives we face when solving a multicriteria optimization problem. This shows that human decision makers need information about the whole set E(f(G)).
Note that the feasible region considered in this paper is convex and compact. Later on, we will also assume that this set has a nonempty interior. While this latter assumption can always be made at least theoretically without loss of generality, the compactness of this set is often not assumed in the literature. However, many real-world problems have compact sets of feasible points. For example, in problems in finance like in the standard multicriteria Markowitz model (Markowitz [28], Rudolf [35]) and its extensions (Markowitz [27], Steinbach [37]), the decision variables represent quantities of investment (money) into different investment possibilities and therefore these variables have natural lower and upper bounds. Likewise, decision variables in multicriteria engineering problems usually represent physical quantities like power (Juschke et al. [25], Fliege and Heseler [9]), response time (Jahn [24, [section] 13.2]), temperature (Hillermeier [20], Jahn [24, [section] 13.3]), or pressure (Hillermeier [20]), which likewise are bounded from above and from below. Moreover, the algorithm presented in [sections]3 for solving a multicriteria optimization problem can also be used in the case of an unbounded feasible set. However, it has to be made clear that the corresponding complexity estimate (see Theorems 2.1 and 3.1) breaks down in the unbounded case (see also Remark 2.4).
1.1.2. Scalarization. It is well-known that we can find a point close to E(f(G)) of the multicriteria problem specified above by solving the single-objective optimization problem
min [z.sup.T] f(x)
subject to x [member of] G, (2)
with z [member of] Z an arbitrary weight vector from the set
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)
This approach is often called scalarization (for a discussion of this and other scalarization techniques see, e.g., Gopfert and Nehse [14], Jahn [23, 24], Hillermeier [20], and Fliege [8]) while the corresponding single-objective optimization problems are often called scalarized problems (or programs), auxiliary problems, or compromise models (Jahn [24]). Indeed, defining the set of properly efficient points P by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)
it can be shown (Geoffrion [10], Sawaragi et al. [36]) that
P(f(G)) [??] E(f(G)) [??] cl(P(f(G))) (5)
holds. Here, cl(x) is the closure operator. In fact, this result holds for arbitrary functions f: G [right arrow] [R.sup.n] as long as the set {y + w | y [member of] f(G), w [member of] [R.sup.n.sub.+]} is closed and convex (see, e.g., Jahn [24, Corollary 11.19] and Geoffrion [10]).
Because we can not distinguish numerically between a set and its closure, we can therefore replace E by P in all applications involving convex functions. However, with the scalarization above, the optimal value function
[phi]: z, [??] arg min{ x [member of] G} (6)
is set valued and in general not continuous in any sense. It has recently been shown that this effect does not occur when one does not use a linear objective function as above (linear scalarization) but a quadratic one (quadratic scalarization) in the sense of
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
(see Fliege [8]). As usual, diag(z) is the diagonal matrix in [R.sup.nxn] with the vector z[member of] [R.sup.n] on its main diagonal. Indeed, if f(G) [sub set] int ([R.sup.n.sub.+]) (a rather weak assumption), we have that
P(f(G)) [??] Q(f(G)) [??] E(f(G))
holds and the optimal value function
[psi]: z [right arrow] arg min{ | x[member of]G} (7)
is locally Lipshitz continuous (see Fliege [8]). For more details about different scalarization techniques, the reader is referred to Fliege [7, 8], Hillermeier [20], Carrizosa and Fliege [4], and Jahn [24].
Introducing artificial variables, we see that we have to consider an infinite family of scalar problems of the form
minimize subject to [f.sub.i](x) [less than or equal to] [t.sub.i] (i = 1, ..., n), (8) x[member of]G,
resp.
minimize subject to [f.sub.i](x) [less than or equal to] [t.sub.i] (i = 1, ..., n), (9)
x [member of ]G.
Accordingly, we can assume that the objective function f: G [right arrow] R of the scalarized problem is linear or strictly convex quadratic and the set of feasible points is fixed, i.e., independent of the parameterization. This is an important simplification in order to employ interior-point methods because quadratic objective functions are 0-compatible with self-concordant barrier functions (Nesterov and Nemirovskii [30]), and constant sets of feasible points reduce the amount of work needed to find strictly feasible starting points.
Of course, in applications we have to content ourselves with a finite subset Z [sub set] Z from which we have to choose our weight vectors. This will lead to a discrete approximation of the set of efficient points. However, it has been observed (Fliege and Heseler [9]) that an a priori discretization of the set of weights Z will usually result in a waste of a large amount of computational effort, because it is not a priori clear in which part of the weight space a finer discretization (i.e., a finer grid) is necessary. Basically, we want to use more parameters in those regions of the parameter space where weight vectors which are close together result in efficient points whose images in the image space [R.sup.n] are far apart from each other. Furthermore, to save work when computing some additional efficient points (i.e., when solving some additional, new optimization problems), we propose to use a warm-start strategy. With such a strategy, points from the iteration history of scalar problems already solved are used as starting points for the optimization problems currently under consideration.
The rest of this paper is organized as follows. In [section]2, an algorithm is presented to solve two singlecriterion (scalar) programs simultaneously by way of an adapted interior-point method employing a warm-start method. For this, the standard primal path-following interior-point algorithm as presented in Nesterov and Nemirovskii [30] is rehearsed in short in [section]2.1. It turns out that the first stage of the algorithm (the construction of a point close to the "center" of the set of feasible points) can be used without any modification in a multicriteria framework (see [sub section]2.1.1-2.1.2). The second stage of this algorithm is analyzed in more detail in [section]2.1.3. In [section]2.2, an algorithm is presented in which two scalar programs with linear objective functions are solved simultaneously by way of an adapted interior-point method. Moreover, an efficiency estimate elucidates the dependence of the number of steps of the algorithm on...
|
