A new scalarization approach and applications in multicriteria d.c. optimization

Christiane Tammer Kristin Winkler ^{∗}

Abstract

We introduce a specialization of the nonlinear scalarization concept by Gerth (Tammer) and Weidner using so-called block norms and oblique norms, recently studied by Klamroth, Schandl and Wiecek. So we get a polyhedral structure of the scalarizing functional which is useul from the theoretical as well as from the numerical point of view. We give a characterization of efficient elements by a scalarization via oblique norms and a characterization of weakly efficient elements via block norms. Finally, we apply our efficiency assertions to multicriteria d.c. optimization.

1 Motivation

Klamroth, Schandl and Wiecek, [7], [8], investigate block norms and so-called oblique norms in order to generate nondominated solutions of multicriteria programs. They use the norm scalarization concept based on the Minkowski functional generated by these norms and propose necessary as well as sufficient conditions for efficiency.

In [2], Gerth (Tammer) and Weidner propose a nonlinear scalarization method for multiobjective programming problems using a functional z_{γ,k,w} : IR^{d} → IR defined by

z_{γ,k,w}(y) := inf{τ ∈ IR : y ∈ τk + C + w},  y ∈ IR^{d},  (1)

where k ∈ int IR_{+}^{d}, w ∈ IR^{d}, C ⊂ IR^{d}. This concept is based on separation theorems due to a shift of an appropriate set C in direction k, and it yields parametric surrogate problems. They were able to derive scalarization assertions without the assumption of convexity.

The aim of our paper is to study a specialization of the nonlinear scalarization concept by Gerth (Tammer) and Weidner using the notion of oblique norms recently studied by Klamroth, Schandl and Wiecek. The shifted set C in the definition of the scalarizing functional will be constructed on the basis of block norms. We use the special polyhedral structure of this set C in order to derive a characterization of the solutions of multicriteria problems by scalarizing functional with suitable numerical properties. We establish necessary as well as sufficient efficiency criteria. Using oblique norms, we can derive strict monotonicity properties of the functional and improve the possibilities to distinguish efficient elements from weakly efficient ones. Moreover, the scalarizing functional is useful for the selection of the most preferred efficient solution by the decision maker. Finally, we show how some known scalarization concepts fit into our approach due to their polyhedral structure.

∗Martin Luther University Halle-Wittenberg, Department of Mathematics and Computer Sciences, Institute of Optimization and Stochastics, Theodor-Lieser-Strasse 5, D-06099 Halle (Saale), Germany, tammer@mathematik.uni-halle.de, winkler@mathematik.uni-halle.de

In the last section, we apply our results to vector-valued d.c. optimization problems. On the base of the special structure of the set C in the definition of the scalarizing functional it is possible to preserve the typical d.c. structure during scalarization.

Though some of our assertions also hold in general topological vector spaces, we restrict ourselves to IR^{d}, d ≥ 1, in the moment.

Definition 1.1 Let Y ⊂ IR^{d} a non-empty set and K ⊂ IR^{d} a pointed convex cone with nonempty interior. An element ȳ ∈ Y is called

• K-efficient in Y, if Y ∩ (ȳ − K\{0}) = ∅;

• weakly K-efficient in Y, if Y ∩ (ȳ − int K) = ∅.

The set of (weakly) K-efficient elements of Y is denoted by E(Y, K) and E_{w}(Y, K), respectively.

It is well-known that E(Y, K) ⊆ E_{w}(Y, K). Supposing K = IR_{+}^{d}, we shortly speak of (weakly) efficient elements instead of (weakly) IR_{+}^{d}-efficient elements. The case K ⊃ IR_{+}^{d} with IR_{+}^{d}\{0} ⊂ int K is also known as proper efficiency.

In order to translate efficiency into real-valued analyis, we will deal with so-called scalarization functionals z : IR^{d} → IR. As an important property, scalarization functionals should map the order of IR^{d} on the natural order in IR in an appropriate way, which is done by monotonicity:

Definition 1.2 A functional z : IR^{d} → IR is called

• monotone, if y_{1} ∈ y_{2} − IR_{+}^{d} implies z(y_{1}) ≤ z(y_{2});

• strictly monotone, if y_{1} ∈ y_{2} − IR_{+}^{d}\{0} implies z(y_{1}) < z(y_{2}).

Obviously, a strictly monotone functional is monotone. Further, if the functional z is continuous and fulfills y_{1} ∈ y_{2}−int IR_{+}^{d} ⇒ z(y_{1}) < z(y_{2}), then z is monotone, too.

In the following we give some remarks on our notations. We use lower indices in order to distinguish between different elements of a set, for instance y_{1}, y_{2} ∈ IR^{d}, and we use upper indices for the components of a vector: y = (y^{1}, ..., y^{d}) ∈ IR^{d}. IR_{+}^{d} defines the cone of positive elements in IR^{d},

IR_{+}^{d} = {y ∈ IR^{d} : y^{i} ≥ 0, i = 1, ..., d}.

We denote by 𝔢_{j}, j = 1, ..., d, the unit vectors of IR^{d}, i.e. 𝔢_{j}^{i} = 1 if i = j and 𝔢_{j}^{i} = 0 otherwise. The symbol ⟨., .⟩ stands for the scalar product in IR^{d},

⟨y_{1}, y_{2}⟩ = y_{1}^{1}y_{2}^{1} + ... + y_{1}^{d}y_{2}^{d}.

We write y + A instead of {y} + A = {y + a : a ∈ A} for the sum of an element (set containing only one element) and an arbitrary set. Further, we denote by int A the (topological) interior of a set A ⊂ IR^{d}, by cl A its closure and by bd A its boundary. Note that int (y + A) = y + int A and cl (y + A) = y + cl A.

2 Block norms and oblique norms

Polyhedral norms or block norms play an important role in the measurement of distances, especially in locational analysis, approximation theory and mathematical programming. They can be used in order to approximate arbitrary norms since the set of block norms is dense in the set of all norms, compare Ward and Wendell, [14]. Furthermore, block norms imply piecewise linearity of the corresponding distance measure because of their polyhedral structure. This often leads to efficiently solvable (piecewise linear) optimization problems.

Several authors have used norms in multicriteria optimization in order to compute the efficient solutions that are closest to the utopia point (cf. Yu, [16]; Steuer and Choo, [13]; Jahn, [5]; Lewandowski and Wierzbicki, [9]). In our paper we will use block norms and oblique norms in order to define a suitable nonlinear scalarizing functional. This functional can be used in an interactive procedure for the determination of efficient solutions as well as for selecting the most preferred efficient solution by the decision maker.

Definition 2.1 A subset A ⊂ IR^{d} is called polyhedral, if it can be expressed as the intersection of a finite collection of closed half-spaces, i.e. as the solution of a finite system of inequalities

⟨a_{i}, y⟩ ≤ α_{i},  a_{i} ∈ IR^{d}, α_{i} ∈ IR, i = 1, ..., n.  (2)

A bounded polyhedral set is called a polytope.

Before continuing with the introduction of block norms, let us biefly consider polyhedral cones. Allthough this is well-known that polyhedral cones can be represented by homogen inequalities, we didn’t found it explicitly in the literature. So we state this characterization with a short proof.

Lemma 2.1 If K ⊂ IR^{d} is a polyhedral cone, then K can be characterized by a system of homogeneous inequalities:

K = {y ∈ IR^{d} : ⟨a_{i}, y⟩ ≤ 0, i = 1, ..., n}, a_{i} ∈ IR^{d}.

Proof. Let K ⊂ IR^{d} be a convex polyhedral cone. From the definition of polyhedral sets we know, that K can be characterized by a system of inequalities ⟨a_{i}, y⟩ ≤ α_{i}, i = 1, ..., n. From 0 ∈ K we have 0 ≤ α_{i} for all i = 1, ..., n. Now assume that there exists some j ∈ {1, ..., n} and y ∈ K \ {0} such that α_{j} ≥ ⟨a_{j}, y⟩ > 0. Since K is a cone, we could derive

(\frac{2α_{j}}{⟨a_{j}, y⟩})y ∈ K

and therefore

2α_{j} = ⟨a_{j}, 2 \frac{α_{j}}{⟨a_{j}, y⟩}y⟩ ≤ α_{j},

which is a contradiction.

Let γ be a norm on IR^{d} which is characterized by its (closed) unit ball

B_{γ} := {y ∈ IR^{d} : γ(y) ≤ 1}.

Clearly, B_{γ} is a convex set. Conversely, let a closed, convex, symmetric (i.e. y ∈ B ⇒ −y ∈ B) set B ⊂ IR^{d} with 0 ∈ int B be given. Then B characterizes a norm γ given by

γ(y) := inf {τ ∈ IR_{+} : y ∈ τB}.

So it is no matter whether we have a norm γ given as a function or by its unit ball. In this paper, we mainly deal with norms given by its unit balls.

Definition 2.2 A norm γ is called a block norm, if its unit ball B_{γ} is polyhedral (a polytope).

Some authors prefer another definition for block norms: They say that the unit ball of a block norm has to be the convex hull of finitely many elements of IR^{d}. In fact, both definitions coincide, as the following lemma demonstrates. (For the proof, see for instance [11], Theorem 19.1.)

Lemma 2.2 The following properties of a convex set A ⊂ IR^{d} are equivalent:

a) A is polyhedral;

b) A is the convex hull of finitely many elements y_{i}^{∗} ∈ IR^{d}, i = 1, ..., m.

If A is the convex hull of finitely many elements y_{i}^{∗} ∈ IR^{d}, these elements are called extremal elements. Many effort has been done to provide algorithms for calculating the extreme elements from the hyperplanes given by a_{i}, i = 1, ..., n, and vice versa. Nevertheless, we will always deal with unit balls of norms given by a system of inequalities as in (2).

The subsets F_{i} := {y ∈ B_{γ} : ⟨a_{i}, y⟩ = α_{i}} are called faces of the unit ball B_{γ}. Throughout this paper, we assume that the system (2) contains no redundant inequalities, i.e. that each set F_{i} consists of at least two different elements.

If γ is an block norm with unit ball B_{γ} given by system (2), then we have

int B_{γ} = {y ∈ B_{γ} : ⟨a_{i}, y⟩ < α_{i}, i = 1, ..., n},  (3)
bd B_{γ} = {y ∈ B_{γ} : ∃ i, 1 ≤ i ≤ n : ⟨a_{i}, y⟩ = α_{i}}.  (4)

So, bd B_{γ} is equivalently given by the union of all faces of B_{γ}.

In [7], Klamroth, Schandl and Wiecek introduced the notion of so-called oblique norms:

Definition 2.3 Let ȳ ∈ IR^{d}. The reflection set of ȳ is defined by

R(ȳ) := {y ∈ IR^{d} : |y^{i}| = |ȳ^{i}| ∀ i = 1, ..., d}.

A norm γ is called absolute, if γ(y) = γ(ȳ) for all y ∈ R(ȳ). A block norm γ is called oblique, if γ is absolute and satisfies (y − IR_{+}^{d}) ∩ IR_{+}^{d} ∩ bd B_{γ} = {y} for all y ∈ IR_{+}^{d} ∩ bd B_{γ}.

Absoluteness of norms provides a high geometrical symmetry of the unit ball B_{γ}. Indeed, the unit balls of absolute norms are completely described by their positive parts B_{γ} ∩ IR_{+}^{d}.

Lemma 2.3 Let B_{γ} be the unit ball of an absolute norm γ. Then conv R(y) ⊆ B_{γ} holds for each y ∈ B_{γ}.

Proof. We choose ȳ ∈ B_{γ} arbitrary and consider y ∈ conv R(ȳ). Then there are y_{1}, ..., y_{k} ∈ R(ȳ) and λ_{1}, ..., λ_{k} ∈ [0, 1], ∑_{i=1}^{k} λ_{i} = 1, with y = ∑_{i=1}^{k} λ_{i}y_{i}. ȳ ∈ B_{γ} and y_{1}, ..., y_{k} ∈ R(ȳ) imply γ(y_{i}) = γ(ȳ) ≤ 1 for all i = 1, ..., k. Since γ is subadditive, we can conclude γ(y) ≤ ∑_{i=1}^{k} λ_{i}γ(y_{i}) ≤ ∑_{i=1}^{k} λ_{i} = 1, i.e. y ∈ B_{γ}.

Lemma 2.4 Let an oblique norm γ be given by the inequality system ⟨a_{i}, y⟩ ≤ α_{i}, i = 1, ..., n. Then we have ⟨a_{i}, 𝔢_{j}⟩ ≠ 0 for all i = 1, ..., n and for each unit vector 𝔢_{j}, j = 1, ..., d.

Proof. Assume ⟨a_{i^{∗}}, 𝔢_{j^{∗}}⟩ = 0 for some i^{∗} ∈ {1, ..., n} and j^{∗} ∈ {1, ..., d}. Then there exists an elements y_{1} ∈ B_{γ} with ⟨a_{i^{∗}}, y_{1}⟩ = α_{i^{∗}}. We can assume y_{1} ∈ IR_{+}^{d}, y_{1}^{j^{∗}} > 0, otherwise the face F_{i^{∗}} would contain the origin. We define an element y_{2} ∈ IR^{d} by

y_{2} = y_{1} − \frac{y_{1}^{j^{∗}}}{2} 𝔢_{j^{∗}}

Without effort we can verify y_{2} ∈ conv R(y_{1}), where R(y_{1}) denotes the reflection set of y_{1}. Since γ is absolute and y_{1} ∈ bd B_{γ}, we get y_{2} ∈ B_{γ}. Next, we derive

⟨a_{i^{∗}}, y_{2}⟩ = ⟨a_{i^{∗}}, y_{1}⟩ − \frac{y_{1}^{j^{∗}}}{2} ⟨a_{i^{∗}}, 𝔢_{j^{∗}}⟩ = α_{i^{∗}},

i.e. y_{2} ∈ bd B_{γ}. Together with y_{2} ∈ (y_{1} − IR_{+}^{d}) ∩ IR_{+}^{d}, this yields y_{2} ∈ (y_{1} − IR_{+}^{d}) ∩ IR_{+}^{d} ∩ bd B_{γ}: Since y_{2} ≠ y_{1}, this is a contradiction to the assumption that γ is oblique.

Example 2.1 The unit ball of the norm ∥.∥ defined by the euclidean distance in IR^{d},

∥y∥ = \sqrt{⟨y, y⟩} = \sqrt{y^{1}y^{1} + ... + y^{d}y^{d}}, y = (y^{1}, ..., y^{d}) ∈ IR^{d},

is absolute. It even satisfies the second condition in the definition for oblique norms. But ∥.∥ is not a block norm, so ∥.∥ is absolute but not oblique.

The unit ball of the maximum-norm ∥.∥_{∞} in IR^{d},

∥y∥_{∞} = max_{i=1,...,d} |y^{i}|, y = (y^{1}, ..., y^{d}) ∈ IR^{d},

is an absolute block norm. We have (0, y^{2}, ..., y^{d}) ∈ ((y^{1}, ..., y^{d}) − IR_{+}^{d}) ∩ IR_{+}^{d} ∩ bd B_{∥.∥_{∞}} for each y = (y^{1}, ..., y^{d}) ∈ IR_{+}^{d} ∩ bd B_{∥.∥_{∞}}, so ∥.∥_{∞} is not oblique.

Example 2.2 Let ȳ = (ȳ^{1}, ..., ȳ^{d}) ∈ int IR_{+}^{d}, i.e. ȳ^{i} > 0 for all i = 1, ..., d. We define a norm γ by

B_{γ} := conv R(ȳ) = ⋃_{y∈(ȳ−IR_{+}^{d})∩IR_{+}^{d}} R(y).

Obviously, B_{γ} is closed. The corresponding system of inequalities is given by

⟨𝔢_{i}, y⟩ ≤ |ȳ^{i}| = ȳ^{i},  −⟨𝔢_{i}, y⟩ ≤ |ȳ^{i}| = ȳ^{i},  i = 1, ..., d.

This can easily be seen by γ(y) ≤ 1 if and only if y ∈ conv R(ȳ) resp. if |y^{i}| ≤ ȳ^{i} for all i = 1, ..., d. According to Lemma 2.4, this norm is not oblique: For i ≠ j we have ⟨a_{i}, 𝔢_{j}⟩ = ±⟨𝔢_{i}, 𝔢_{j}⟩ = 0.

Example 2.3 Let K be a polyhedral convex pointed cone with IR_{+}^{d}\{0} ⊂ int K ≠ ∅. Regarding Lemma 2.1, K can be expressed by

K = {y ∈ IR^{d} : ⟨b_{i}, y⟩ ≤ 0, i = 1, ..., m}.

Under the assumption IR_{+}^{d}\{0} ⊂ int K ≠ ∅, 𝔢_{j} ∈ K yields b_{i} ∉ IR_{+}^{d} for all i = 1, ..., d, resp. Since K is assumed to be pointed, we have even b_{i} ∈ −IR_{+}^{d} for all i = 1, ..., d. We will use the cone K in order to construct a norm γ with the corresponding unit ball B_{γ} and show that this norm γ is oblique.

Let ȳ = (ȳ^{1}, ..., ȳ^{d}) ∈ int IR_{+}^{d}, i.e. ȳ^{i} > 0 for all i = 1, ..., d. Similar to the example above, we define

B_{γ} := ⋃_{y∈(ȳ−K)∩IR_{+}^{d}} R(y)

= {y = (y^{1}, ..., y^{d}) ∈ IR^{d} : ỹ:= (|y^{1}|, ..., |y^{d}|) ∈ ȳ − K},

where R(.) denotes the reflection set. Firstly, we show that B_{γ} can be expressed as the solution of a corresponding system of inequalities:

y ∈ B_{γ} ⟺ ⟨−a_{i}, y − ȳ⟩ ≤ 0, a_{i} ∈ R(b_{i}), i = 1, ..., m.  (5)

For the proof of (5), note that y ∈ B_{γ} if and only if

⟨−b_{i}, (|y^{1}|, ..., |y^{d}|)^{T} ⟩ ≤ −⟨b_{i}, ȳ⟩, i = 1, ..., m.

We introduce for each vector v ∈ IR^{d} the index set J_{+}(v) := {j : 1 ≤ j ≤ d, v^{j} ≥ 0}. Since −b_{i} ∈ IR_{+}^{d}, we have for all a_{i} ∈ R(b_{i}), i = 1, ..., m, and y ∈ IR^{d}

⟨−b_{i}, (|y^{1}|, ..., |y^{d}|)^{T} ⟩ = ⟨−ā_{i}, y⟩ ≥ ⟨−a_{i}, y⟩,

where ā_{i} ∈ R(b_{i}) and J_{+}(−ā_{i}) = J_{+}(y). This completes the proof of (5).

Obviously, the norm γ is absolute. In order to proof obliqueness, we choose ȳ ∈ IR_{+}^{d} ∩ bd B_{γ} arbitrary; further we assume the existence of an element ỹ ∈ IR_{+}^{d} ∩ bd B_{γ}, ỹ ≠ ȳ, such that ỹ ∈ ȳ − IR_{+}^{d}. We get from IR_{+}^{d}\{0} ∈ int K that ỹ ∈ ȳ − int K and therefore ỹ ∈ int B_{γ}, in contradiction to ỹ ∈ bd B_{γ}.

3 Scalarization

Let γ be a block norm with unit ball B_{γ},

B_{γ} = {y ∈ IR^{d} : ⟨a_{i}, y⟩ ≤ α_{i}, a_{i} ∈ IR^{d}, α_{i} ∈ IR, i = 1, ..., n}.

Using a_{i} from this formular for B_{γ}, we define a set C ⊂ IR^{d} by

C := {y ∈ IR^{d} : ⟨a_{i}, y⟩ ≤ α_{i}, i ∈ I}  (6)

with the index set

I := {i ∈ {1, ..., m} : {y ∈ IR^{d} : ⟨a_{i}, y⟩ = α_{i}} ∩ B_{γ} ∩ int IR_{+}^{d} ≠ ∅}. (7)

The set I is exactly the set of indices i = 1, ..., n for which the hyperplanes ⟨a_{i}, y⟩ = α_{i} are active in the positive orthant (see Lemma 3.1). Clearly, the set C is closed, and we have

int C := {y ∈ IR^{d} : ⟨a_{i}, y⟩ < α_{i}, i ∈ I}.

We state some geometric properties of the set C.

Lemma 3.1 For every block norm γ with unit ball B_{γ} and the corresponding set C, we have B_{γ} ⊂ C and B_{γ} ∩ IR_{+}^{d} = C ∩ IR_{+}^{d}.

Proof. I ⊂ {1, ..., n} yields B_{γ} ⊂ C resp. B_{γ} ∩ IR_{+}^{d} ⊂ C ∩ IR_{+}^{d}.

For the opposite inclusion, assume that there exists some ȳ ∈ C ∩ IR_{+}^{d} with ȳ ∉ B_{γ} ∩ IR_{+}^{d}. Clearly, ȳ ∉ B_{γ}, so we have γ(ȳ) > 1 and ỹ := ȳ/γ(ȳ) ∈ (bd B_{γ}) ∩ IR_{+}^{d}. Since ỹ ∈ bd B_{γ}, there exists some index j ∈ {1, ..., n} such that ⟨a_{j}, ỹ⟩ = α_{j}. This yields ỹ ∈ B_{γ} ∩ {y ∈ IR^{d} : ⟨a_{j}, y⟩ = α_{j}} ∩ IR_{+}^{d}, i.e. j ∈ I. On the other hand, ⟨a_{j}, ȳ⟩ = γ(ȳ)⟨a_{j}, ỹ⟩ = γ(ȳ)α_{j} > α_{j} and ȳ ∈ C imply j ∉ I.

The following lemma proposes an important property of the parameters a_{i}, i ∈ I. Indeed, it gives an equivalent definition of the set C.

Lemma 3.2 Let γ be an absolute block norm with unit ball

B_{γ} = {y ∈ IR^{d} : ⟨a_{i}, y⟩ ≤ α_{i}, i = 1, ..., n},

let the index set I be defined as in (7). Then we have a_{i} ∈ IR_{+}^{d} if and only if i ∈ I. If γ is an oblique norm, a_{i} ∈ int IR_{+}^{d} holds if and only if i ∈ I.

Proof. We proceed step by step:

1) Firstly, we show that i ∈ I implies a_{i} ∈ IR_{+}^{d}: From the definition of the index set I we get for each i ∈ I some y_{i} ∈ B_{γ} ∩ int IR_{+}^{d} with ⟨a_{i}, y_{i}⟩ = α_{i}. Note that γ(y_{i}) = 1, since each y_{i} is contained in some face of B_{γ}. For each j = 1, ..., d we define an element u_{ij} ∈ IR_{+}^{d} via u_{ij}^{j} = 0 and u_{ij}^{k} = y_{i}^{k} for k ≠ j. Clearly u_{ij} ≠ y_{i} and u_{ij} ∈ conv R(y_{i}) for all i ∈ I and j = 1, ..., d. Since γ is absolute, we can conclude γ(u_{ij}) ≤ γ(y_{i}) = 1 and therefore ⟨a_{i}, u_{ij}⟩ ≤ α_{i} for all i ∈ I and j = 1, ..., d. This yields for all i ∈ I and j = 1, ..., d

0 = α_{i} − α_{i} ≥ ⟨a_{i}, u_{ij} − y_{i}⟩ = ⟨a_{i}, −y_{i}^{j}𝔢_{j}⟩ = −y_{i}^{j}a_{i}^{j}.

Since y_{i} ∈ int IR_{+}^{d}, we get a_{i}^{j} ≥ 0 for all i ∈ I and j = 1, ..., d.

2) For the opposite direction, assume a_{i} ∉ IR_{+}^{d} for some i ∈ I. Then there exists a component a_{i}^{j} < 0, 1 ≤ j ≤ d, and some y ∈ B_{γ} ∩ int IR_{+} with ⟨a_{i}, y⟩ = α_{i}. We verify

⟨a_{i}, y − y^{j}𝔢_{j}⟩ = ⟨a_{i}, y⟩ − y^{j} ⟨a_{i}, 𝔢_{j}⟩ = ⟨a_{i}, y⟩ − y^{j}a_{i}^{j} > ⟨a_{i}, y⟩ = α_{i}

(remind y^{j} > 0 and a_{i}^{j} < 0), so y − y^{j}𝔢_{j} ∉ B_{γ}. On the other hand, we have y − y^{j}𝔢_{j} ∈ conv R(y), where R(y) denotes the reflection set of y, so Lemma 2.3 yields y − y^{j}𝔢_{j} ∈ B_{γ}, in contradiction to y − y^{j}𝔢_{j} ∉ B_{γ}.

3) Finally we discuss the case where γ is oblique. We consider again the element u_{ij} from part 1 of this proof and verify u_{ij} ∈ (y_{i} − IR_{+}^{d}) ∩ IR_{+}^{d}. If γ is an oblique norm, we get from Definition 2.3 u_{ij} ∉ bd B_{γ}, i.e. u_{ij} ∈ int B_{γ}. This implies ⟨a_{i}, u_{ij}⟩ < α_{i} for all i ∈ I and j = 1, ..., d and finally

0 = α_{i} − α_{i} > ⟨a_{i}, u_{ij} − y_{i}⟩ = ⟨a_{i}, −y_{i}^{j}𝔢_{j}⟩ = −y_{i}^{j}a_{i}^{j}.

With y_{i} ∈ int IR_{+}^{d}, now we get a_{i}^{j} > 0 for all i ∈ I and j = 1, ..., d.

Example 3.1 Let ȳ = (ȳ^{1}, ..., ȳ^{d}) ∈ int IR_{+}^{d}. We define a norm γ by B_{γ} := conv R(ȳ). We know from Example 2.2 that the corresponding system of inequalities is given by

⟨𝔢_{i}, y⟩ ≤ ȳ^{i},  −⟨𝔢_{i}, y⟩ ≤ ȳ^{i},  i = 1, ..., d.

From the preceeding lemma we derive

C = {y ∈ IR^{d} : ⟨𝔢_{i}, y⟩ ≤ ȳ^{i}, i = 1, ..., d}
= {y ∈ IR^{d} : y^{i} ≤ ȳ^{i}, i = 1, ..., d}
= ȳ − IR_{+}^{d}.

So, the set C is given by a shift of the negative of the cone IR_{+}^{d}.

Example 3.2 Let ȳ = (ȳ^{1}, ..., ȳ^{d}) ∈ int IR_{+}^{d} and K a polyhedral, convex, pointed cone with IR_{+}^{d}\{0} ⊂ int K ≠ ∅,

K = {y ∈ IR^{d} : ⟨b_{i}, y⟩ ≤ 0, i = 1, ..., m}.

We define a norm γ by B_{γ} := ⋃_{y∈(ȳ−K)∩IR_{+}^{d}} R(y). We know from Example 2.3 that the corresponding system of inequalities is given by

⟨−a_{i}, y − ȳ⟩ ≤ 0, a_{i} ∈ R(b_{i}), i = 1, ..., m.

This yields

C = {y ∈ IR^{d} : ⟨−a_{i}, y − ȳ⟩ ≤ 0, a_{i} ∈ R(b_{i}) ∩ −IR_{+}^{d}, i = 1, ..., m}
= {y ∈ IR^{d} : ⟨b_{i}, ȳ − y⟩ ≤ 0, i = 1, ..., m}
= {y ∈ IR^{d} : ȳ − y ∈ K}
= ȳ − K.

So, the set C is given by a shift of the negative of the cone K.

Lemma 3.3 Let γ be an absolute block norm with corresponding unit ball B_{γ} and set C. Then for all vectors k ∈ B_{γ} ∩ IR_{+}^{d} we have −IR_{+}^{d} ⊆ C − k and −int IR_{+}^{d} ⊆ int C −k. If γ is an oblique norm, even −IR_{+}^{d}\{0} ⊆ int C −k holds.

Proof. Let γ be an absolute block norm, k ∈ B_{γ} ∩ IR_{+}^{d} and y ∈ IR_{+}^{d} arbitrary. Considering k ∈ B_{γ}, we have ⟨a_{i}, k⟩ ≤ α_{i} for i = 1, ..., n and ⟨a_{i}, y⟩ ≥ 0 for i ∈ I by Lemma 3.2. This implies for all i ∈ I

⟨a_{i}, k − y⟩ = ⟨a_{i}, k⟩ − ⟨a_{i}, y⟩ ≤ ⟨a_{i}, k⟩ ≤ α_{i}

and therefore k − y ∈ C, i.e. −IR_{+}^{d} ⊂ C − k.

If we chose y ∈ int IR_{+}^{d} or if γ is an oblique norm, then we get ⟨a_{i}, y⟩ > 0 for i ∈ I and finally ⟨a_{i}, k − y⟩ < α_{i}, i ∈ I.

Note that Lemma 3.3 holds not only for k ∈ bd B_{γ} ∩ IR_{+}^{d}, but also for k ∈ B_{γ} ∩ IR_{+}^{d}. Nevertheless, we will use this assertion only for k ∈ bd B_{γ}.

Let γ be an absolute block norm with unit ball B_{γ} and the corresponding set C defined as in (6), let vectors k ∈ int IR_{+}^{d} and w ∈ IR^{d} be given. We define a functional z_{γ,k,w} : IR^{d} → IR by

z_{γ,k,w}(y) := inf{τ ∈ IR : y ∈ τk + C + w},  y ∈ IR^{d}.  (8)

The functional z = z_{γ,k,w} depends on the norm γ and the parameters k and w. If w = 0, we will often write z_{γ,k} instead of z_{γ,k,0}.

A functional of this type was introduced by Gerth (Tammer) und Weidner (see [2]) in order to scalarize vector optimzation problems. They established the following properties of z_{γ,k}:

Theorem 3.1 Let arbitrary vectors k ∈ int IR_{+}^{d}, w ∈ IR^{d} and an absolute norm γ be given. Consider the corresponding set C given by (6), (7) and the functional z = z_{γ,k,w} to be defined by (8), resp. Let A be a nonempty subset of IR^{d}. Then we have:

(i) z is a well-defined, continuous, convex functional from IR^{d} onto IR.

(ii) z(C + w) ≤ 0, z(bd C + w) = 0, z(int C + w) < 0.

(iii) A ∩ (int C + w) = ∅ if and only if z(A) ≥ 0.

(iv) z is B-monotone for each set B ⊂ IR^{d} with bd C − B ⊆ C. z is strictly B-monotone for each set B ⊂ IR^{d} with bd C − B\{0} ⊆ int C.

(v) z is subadditive if bd C + bd C + w ⊆ cl C.

Remark 3.1 For assertion (iii) in the theorem above, we need int C ≠ ∅. In our cases, this is trivially given by the construction of the set C.

Proof. We apply Theorem 2.1. of [2] choosing K in the original paper as IR_{+}^{d} and C as C + w. Obviously, IR_{+}^{d} and C + d have non-empty interior. The inclusion cl C + w − int IR_{+}^{d} ⊆ int C + w follows directly from a_{i} ∈ IR_{+}^{d}\{0} for i ∈ I resp. ⟨a_{i}, y⟩ > 0 for i ∈ I and y ∈ int IR_{+}^{d}. The convexity of C + w is obvious. In order to show (v), we use the equivalence of bd C + bd C + w ⊆ cl C and (bd C + w) + (bd C + w) ⊆ cl C + w, the latter inclusion is exacty the subadditivity condition in [2, Theorem 2.1].

Corollary 3.1 Let γ be an absolute block norm with unit ball B_{γ} and corresponding set C; let k ∈ int IR_{+}^{d} and w ∈ IR^{d} be arbitrary chosen. Then the functional z_{γ,k,w} defined by forumlar (8) is IR_{+}^{d}-monotone and strictly (int IR_{+}^{d})- monotone.

Proof. Let y_{1} ∈ bd C, y_{2} ∈ IR_{+}^{d} and y_{3} ∈ int IR_{+}^{d} arbitrary. From the definition of the set C and Lemma 3.2 we get for all i ∈ I the inequalities ⟨a_{i}, y_{1}⟩ ≤ α_{i}, ⟨a_{i}, y_{2}⟩ ≥ 0 and ⟨a_{i}, y_{3}⟩ > 0. This yields ⟨a_{i}, y_{1} − y_{2}⟩ ≤ α_{i} and ⟨a_{i}, y_{1} − y_{3}⟩ < α_{i} for all i ∈ I, i.e. y_{1}−y_{2} ∈ C and y_{1}−y_{3} ∈ int C resp. So we have bd C −IR_{+}^{d} ⊆ C and bd C − int IR_{+}^{d} ⊆ int C resp. Now we can apply part (iv) of Theorem 3.1 which implies the proposed assertions about monotonicity.

Corollary 3.2 Let γ be an oblique block norm with unit ball B_{γ} and corresponding set C; let k ∈ int IR_{+}^{d} and w ∈ IR^{d} be arbitrary. Then the functional z_{γ,k,w} defined by forumlar (8) is strictly IR_{+}^{d}-monotone.

Proof. We can conclude as in the preceeding proof with y_{1} ∈ bd C and y_{2} ∈ IR_{+}^{d}\{0}. From the definition of the set C and Lemma 3.2 we get for all i ∈ I the inequalities ⟨a_{i}, y_{1}⟩ ≤ α_{i} and ⟨a_{i}, y_{2}⟩ > 0. This yields ⟨a_{i}, y_{1} − y_{2}⟩ < α_{i} for all i ∈ I, i.e. y_{1} − y_{2} ∈ int C. So we have bd C − IR_{+}^{d} \ {0} ⊆ int C. Now we can apply part (iv) of Theorem 3.1 which implies monotonicity.

For given y ∈ IR^{d}, we can calculate the value z_{γ,k,w}(y) by the following formular:

z_{γ,k,w}(y) = inf {τ ∈ IR : y − w − τk ∈ C}
= inf {τ ∈ IR : ⟨a_{i}, y⟩ − ⟨a_{i}, w⟩ − τ⟨a_{i}, k⟩ ≤ α_{i}, i ∈ I}
= inf \{τ ∈ IR : \frac{⟨a_{i}, y⟩ − ⟨a_{i}, w⟩ − α_{i}}{⟨a_{i}, k⟩} ≤ τ, i ∈ I\}
= max_{i∈I} \frac{⟨a_{i}, y⟩ − ⟨a_{i}, w⟩ − α_{i}}{⟨a_{i}, k⟩} .  (9)

Since k ∈ int IR_{+}^{d}, from Lemma 3.2 we have ⟨a_{i}, k⟩ ≠ 0.

Now we are ready to characterize efficiency via sclarized problems.

Theorem 3.2 (Necessary conditions.) Let Y ⊆ int IR_{+}^{d} be a nonempty set.

(i) If ȳ ∈ E_{w}(Y, IR_{+}^{d}), then there exists a block norm γ such that for each vector k ∈ bd B_{γ} ∩ int IR_{+}^{d} and w = 0 the functional z = z_{γ,k,w} defined by (8) satisfies

z(y) ≥ z(ȳ) = 0 ∀ y ∈ Y.

(ii) If ȳ ∈ E(Y, IR_{+}^{d}), then there exists a block norm γ such that for each vector k ∈ bd B_{γ} ∩ int IR_{+}^{d} and w = 0 the functional z = z_{γ,k,w} defined by (8) satisfies

z(y) > z(ȳ) = 0 ∀ y ∈ Y \{ȳ}.

(iii) If ȳ ∈ E(Y, K) for some convex, polyhedral cone K with IR_{+}^{d}\{0} ⊂ int K, then the norm γ in (ii) can be chosen to be oblique.

Proof. Let Y ⊆ IR_{+}^{d} be a nonempty set.

(i) Let ȳ ∈ E_{w}(Y, IR_{+}^{d}). We define a norm γ by

B_{γ} := conv R(ȳ),

where R(ȳ) denotes the reflection set of ȳ (compare definition 2.3). From Example 3.1 we get C = ȳ − IR_{+}^{d} as corresponding set C for the scalarization functional. So, ȳ ∈ E_{w}(Y, IR_{+}^{d}) is equivalent to ∅ = Y ∩(ȳ−int IR_{+}^{d}) = Y ∩ int C and by Theorem 3.1 (iii) equivalent to z_{γ,k}(y) ≥ 0 for all y ∈ Y and arbitrary fixed k ∈ bd B_{γ} ∩int IR_{+}^{d}. Clearly, ȳ ∈ bd C, so Theorem 3.1 (ii) yields z_{γ,k}(ȳ) = 0 and consequently z_{γ,k}(y) ≥ z_{γ,k}(ȳ) for all y ∈ Y and arbitrary fixed k ∈ B_{γ} ∩ int IR_{+}^{d}.

(ii) We introduce the sets B_{γ}, C and the functional z_{γ,k} as in part (i) of this proof. Assume ȳ ∈ E_{w}(Y, IR_{+}^{d}) and z_{γ,k}(y) = z_{γ,k}(ȳ) for some y ∈ Y, y ≠ ȳ. Then z_{γ,k}(y) = 0, and Theorem 3.1 (ii) implies y ∈ bd C = ȳ − bd IR_{+}^{d}. We we get y ∈ ȳ − IR_{+}^{d}\{0} which contradicts ȳ ∈ E(Y, IR_{+}^{d}). So ȳ ∈ E(Y, IR_{+}^{d}) implies z_{γ,k}(y) > z_{γ,k}(ȳ) for all y ∈ Y \{ȳ} and arbitrary fixed k ∈ bd B_{γ} ∩ int IR_{+}^{d}.

(iii) Let ȳ ∈ E(Y, K). Using the cone K, we define a norm γ by

B_{γ} := {y = (y^{1}, ..., y^{d}) ∈ IR^{d} : ỹ:= (|y^{1}|, ..., |y^{d}|) ∈ ȳ − K}.

In Example 2.3 we have shown that γ is oblique. Furthermore, from Example 3.2 we get that the corresponding set C given by (6) has the form C = ȳ − K. Now we consider the functional z_{γ,k} : IR^{d} → IR (w = 0) defined by (8) using C = ȳ − K. For elements ȳ ∈ E(Y, K) we have ∅ = Y ∩(ȳ−K\{0}) and so ∅ = Y ∩(ȳ−int K) = Y ∩int C and by Theorem 3.1 (iii) z_{γ,k}(y) ≥ 0 for all y ∈ Y and arbitrary fixed k ∈ bd B_{γ} ∩ int IR_{+}^{d}. Clearly, ȳ ∈ bd C, so Theorem 3.1 (ii) yields z_{γ,k}(ȳ) = 0 and consequently z_{γ,k}(y) ≥ z_{γ,k}(ȳ) for all y ∈ Y and arbitrary fixed k ∈ B_{γ} ∩ int IR_{+}^{d}.

Now we proceed as in part (ii) of this proof: Assume z_{γ,k}(y) = z_{γ,k}(ȳ) for some y ∈ Y, y ≠ ȳ. Then z_{γ,k}(y) = 0, and Theorem 3.1 (ii) implies y ∈ bd C = ȳ − bd K. We we get y ∈ ȳ − K\{0} which contradicts ȳ ∈ E(Y, K). So ȳ ∈ E(Y, K) implies z_{γ,k}(y) > z_{γ,k}(ȳ) for all y ∈ Y \{ȳ} and arbitrary fixed k ∈ B_{γ} ∩ int IR_{+}^{d}.

Remark 3.2 Note that we have chosen w = 0 in the assertions above. Therefore the shift of the set C starts always in ȳ which can not be omitted. For other ”origins” of the functional z, i.e. w ≠ 0, we probably can state only inequalities of the type z(y − ȳ) ≥ 0. Of course, this is not the same, since z is in general not homogen and not subadditive, too.

Remark 3.3 We have assumed k to be in bd B_{γ}. This is a rather technical assumption since we only use k ∈ int IR_{+}^{d}.

Theorem 3.3 (sufficient conditions) Let γ be an absolute block norm with unit ball B_{γ} and k ∈ bd B_{γ} ∩ int IR_{+}^{d} arbitrary. Let Y ⊆ int IR_{+}^{d} be a nonempty set.

(i) If ȳ ∈ Y fulfills

z(y) ≥ z(ȳ) ∀ y ∈ Y,

where z = z_{γ,k,w} with w = ȳ − k is defined by (8), then we have ȳ ∈ E_{w}(Y, IR_{+}^{d}).

(ii) If ȳ ∈ Y fulfills

z(y) > z(ȳ) ∀ y ∈ Y \{ȳ},

where z = z_{γ,k,w} with w = ȳ − k is defined by (8), then we have ȳ ∈ E(Y, IR_{+}^{d}).

(iii) Let γ be oblique. If ȳ ∈ Y fulfills

z(y) ≥ z(ȳ) ∀ y ∈ Y,

where z = z_{γ,k,w} with w = ȳ − k is defined by (8), then we have ȳ ∈ E(Y, IR_{+}^{d}).

Proof. Let Y ⊆ IR_{+}^{d} be a nonempty set.

(i) Let γ be an absolute block norm with unit ball B_{γ} and k ∈ bd B_{γ} ∩int IR_{+}^{d} arbitrary; assume that ȳ ∈ Y fulfills

z_{γ,k,w}(y) ≥ z_{γ,k,w}(ȳ)  ∀ y ∈ Y  (10)

with w = ȳ − k. We can transform z_{γ,k,w} into z_{γ,k} and vice versa by

z_{γ,k,w}(y) = inf{τ ∈ IR : y ∈ τk + C + w}
= inf{τ ∈ IR : y − w ∈ τk + C}
= z_{γ,k}(y − w)
= z_{γ,k}(y − ȳ + k).

So, inequality (10) can be written as

z_{γ,k}(y − ȳ + k) ≥ z_{γ,k}(ȳ − ȳ + k) = z_{γ,k}(k)

or equivalently, since k ∈ bd B_{γ} ∩ int IR_{+}^{d} ⊂ bd C and z_{γ,k}(bd C) = 0 (remind w = 0),

z_{γ,k}(y − ȳ + k) ≥ 0.  (11)

Theorem 3.1 (iii) yields y − ȳ + k ∉ int C for all y ∈ Y. Lemma 3.3 states −int IR_{+}^{d} ⊆ int C − k, so we can conclude y − ȳ ∉ −int IR_{+}^{d} for all y ∈ Y which yields ȳ ∈ E_{w}(Y, IR_{+}^{d}).

(ii) We reason as in part (i) of this proof, but now the inequality (11) is

strongly fulfilled,

z_{γ,k}(y − ȳ + k) > 0.  (12)

Theorem 3.1 (iii) yields y −ȳ+k ∉ int C for all y ∈ Y, due to Theorem 3.1 (ii) we can strengthen this inclusion to y − ȳ + k ∉ C for all y ∈ Y. Lemma 3.3 states −IR_{+}^{d} ⊆ C − k, so we can conclude y − ȳ ∉ −IR_{+}^{d} \ {0} for all y ∈ Y \ {ȳ} which yields ȳ ∈ E(Y, IR_{+}^{d}).

(iii) We reason as in part (i) of this proof. If γ is an oblique norm, Lemma 3.3 even states −IR_{+}^{d}\{0} ⊆ int C − k, so we can conclude y − ȳ ∉ −IR_{+}^{d}\{0} for all y ∈ Y \ {ȳ} which yields ȳ ∈ E(Y, IR_{+}^{d}).

The two theorems above have the same structure: Solutions of the scalarized problem generated by a block norm are only weak efficient elements, while efficiency can be guaranteed either for strict solutions of the scalarized problems or for solutions of the scalarized problems generated by oblique norms.

Note that the condition Y ⊂ int IR_{+}^{d} can be fulfilled easily if Y is bounded from below, i.e. if there exists some b ∈ IR_{+}^{d} such that y ∈ b + IR_{+}^{d} for all y ∈ Y. Then the original optimization problem is equivalent to finding some vector minimum in Y + b + k for some k ∈ int IR_{+}^{d}.

It is known that many concepts of proper efficiency fit into the general approach of Gerth (Tammer) and Weidner. Since many of them are based on a certain kind of generalized linear scalarization, they are endowed with a polyhedral structure:

a) In [15], Weidner characterizes properly efficient elements in the sense of Geoffrion by solutions of the auxiliary problem

max_{i=1,...,l}(⟨v_{i}, y⟩ − ν_{i}) → min, y ∈ Y

with v_{i} ∈ int IR_{+}^{d}, ν_{i} ∈ IR. Without effort, we can verify that these auxiliary problems coincide with

z_{γ,k,w}(y) → min, y ∈ Y

where γ is an oblique norm, k ∈ IR_{+}^{d} is arbitrary and w = 0.

b) Note that the most primitive case of a),

⟨a, y⟩ → min, y ∈ Y,

with a ∈ int IR_{+}^{d} characterizes proper efficient elements in the sense of linear scalarization (Schönfeld, compare [12]).

c) Kaliszewski characterizes efficiency with respect to polyhedral cones by some inconsistency assertions, compare for instance [6, Theorem 3.7]: Let a polyhedral cone K be given,

K := {y ∈ IR^{d} : ⟨−b_{i}, y⟩ ≥ 0, i = 1, ..., m}.

Then he states: y ∈ E(Y, K) implies that the system

⟨b_{i}, y − ŷ⟩ < ⟨b_{i}, ȳ − ŷ⟩, i = 1, ..., m,

where Y ⊂ ŷ + K, is inconsistent for all y ∈ Y. Indeed, this characterization is a consequence of our Theorem 3.2 (iii): We choose C = ȳ − K and consider Ŷ = Y − ŷ. Then we have Ŷ ⊂ K. (This is a weaker condition than Ŷ ⊂ IR_{+}^{d}, but it suffices for our purposes.) Theorem 3.2 (iii) yields

z(y − ŷ) ≥ z(ȳ − ŷ), ∀ y ∈ Y.

Using formular (9) and w = 0, β_{i} = 0, we get for all y ∈ Y

max_{i=1,...,m} \frac{⟨b_{i}, y − ŷ⟩}{⟨b_{i}, k⟩} ≥ max_{i=1,...,m} \frac{⟨b_{i}, ȳ − ŷ⟩}{⟨b_{i}, k⟩}

So, for each y ∈ Y there exists some i^{∗} ∈ I such that

\frac{⟨b_{i^{∗}}, y − ŷ⟩}{⟨b_{i^{∗}}, k⟩} ≥ max_{i=1,...,m} \frac{⟨b_{i}, ȳ − ŷ⟩}{⟨b_{i}, k⟩} ≥ \frac{⟨b_{i^{∗}}, ȳ⟩}{⟨b_{i^{∗}}, k⟩},

that is ⟨b_{i^{∗}}, y−ŷ⟩ ≥ ⟨b_{i^{∗}}, ȳ−ŷ⟩. So, ⟨b_{i}, y−ŷ⟩ < ⟨b_{i}, ȳ−ŷ⟩ for all i = 1, ..., m is not possible.

4 Applications in d.c. optimization

In this section we apply our results from Section 3 in order to give a characterization of efficient elements of a nonconvex vector optimization problem via scalarization.

We consider a multicriteria d.c. optimization problem, i.e. Y = f[X], where f : X → IR^{d} is given by

f(x) = g(x) − h(x) = ( g_{1}(x) − h_{1}(x) ; ⋮ ; g_{d}(x) − h_{d}(x) ) , x ∈ X.

Let X be a nonempty, convex subset of a linear topological space, let the functions g_{i}, h_{i} : X → IR ∪ {+∞} be continuous and convex. We define problem (P_{CD}) by

E(Y, IR_{+}^{d})

= E((g − h)[X], IR_{+}^{d})

= {g(x) − h(x) : x ∈ X, (g − h)(X) ∩ (g(x) − h(x) − IR_{+}^{d}\{0}) = ∅}.

Dealing with real-valued d.c. problems, an important question is to obtain a lower bound for the minimum. Such lower bounds are a real need for solving global optimization problems by a branch-and-bound strategy. Using polyhedral branching schemes it is important to find in the bounding process good lower bounds for subproblems in d.c. form at each stage in the resolution of the d.c. problem. Furthermore, lower bounds are interesting in order to check feasibility: If a lower bound for min_{x∈X}{g(x) − h(x)} is strictly positive, then the infeasibility of the problem

min{f(x) : g(x) − h(x) ≤ 0, x ∈ X}

follows.

We want to characterize the solutions of the multicriteria d.c. problem on the base of a suitable scalarization. It is important to preserve the typical d.c. structure during scalarization. Then it would be possible to apply well known results from real-valued d.c. optimization (cf. Horst and Thoai [3], Horst and Tuy [4]), especially duality assertions (cf. Martinez-Legaz and Volle, [10]) or Lagrangian decomposition methods (cf. Carrizosa, [1]).

A function g : X → IR^{d} is called IR_{+}^{d}-convex if

g(λx_{1}) + g((1 − λ)x_{2}) ∈ λg(x_{1}) + (1 − λ)g(x_{2}) − IR_{+}^{d}

holds for all x_{1}, x_{2} ∈ X, λ ∈ [0, 1]. Clearly, if g(x) = (g_{1}(x), ..., g_{d}(x))^{T} with convex functions g_{i} : X → IR, i = 1, ..., d, then g is IR_{+}^{d}-convex.

Next, we show that convexity is preserved under monotone scalarization. This fact guarantees some d.c. structure after a scalarization.

Lemma 4.1 Let g : X → IR^{d} be a IR_{+}^{d}-convex function. Furthermore, assume that z : IR^{d} → IR is a IR_{+}^{d}-monotone, convex functional. Then (z ∘ g)(.) is convex.

Proof. For all x^{1}, x^{2} ∈ X and for all λ ∈ [0, 1] holds

z(g(λx^{1} + (1 − λ)x^{2})) ≤ z(λg(x^{1}) + (1 − λ)g(x^{2}))
≤ λz(g(x^{1})) + (1 − λ)z(g(x^{2})),

which is convexity.

In the following theorem we derive a lower bound for scalarized objective function values of feasible elements of (P_{CD}) applying Theorem 3.2. For this purpose it is important that the lower bound has the d.c. structure, too. So it would be possible to apply duality assertion for real-valued d.c. problems.

Theorem 4.1 (Necessary condition) Consider the problem (P_{CD}), assume (g − h)[X] ∈ int IR_{+}^{d} and let ȳ = g(x̄) − h(x̄) ∈ E((g − h)[X], IR_{+}^{d}). Then there exists a block norm γ such that the functional z = z_{γ,k,w} defined by (8) with k = ȳ = g(x̄) − h(x̄) and w = −ȳ satisfies

z(g(x̄)) − z(h(x̄)) < z(g(x) − h(x))

for all x ∈ X with g(x) − h(x) ≠ g(x̄) − h(x̄).

Proof. Let ȳ = g(x̄) − h(x̄) ∈ E((g − h)[X], IR_{+}^{d}). From Theorem 3.2 (ii) we derive for all y ∈ (g − h)[X]\{ȳ}

z_{γ,k,w}(ȳ) < z_{γ,k,w}(y)  (13)

where the functional z_{γ,k,w} defined by (8) is generated by a norm γ with B_{γ} = conv R(ȳ), an arbitrary vector k ∈ bd B_{γ} ∩ int IR_{+}^{d} and w = 0. The set C is given by ȳ − IR_{+}^{d} (compare Example 3.1). We choose k = ȳ (which is in fact an element of bd B_{γ} ∩ int IR_{+}^{d}) and verify

z_{γ,ȳ,−ȳ}(y) = max_{i∈I} \frac{⟨a_{i}, y⟩ + ⟨a_{i}, ȳ⟩ − α_{i}}{⟨a_{i}, ȳ⟩}
= max_{i∈I} \frac{⟨a_{i}, y⟩ − α_{i}}{⟨a_{i}, ȳ⟩} + 1
= z_{γ,ȳ,0}(y) + 1

(compare formular (9)). Here, the set I is the index set defined in (7). So, inequality (13) remains valid if we write z_{γ,ȳ,−ȳ} instead of z = z_{γ,ȳ,0}. Replacing y by g(x) − h(x), we get

z_{γ,ȳ,−ȳ}(g(x̄ − h(x̄)) < z_{γ,ȳ,−ȳ}(g(x) − h(x))

for all x ∈ X with g(x)−h(x) ≠ g(x̄)−h(x̄). Further, z = z_{γ,ȳ,−ȳ} is subadditive due to Theorem 3.1 (v). In fact, we have

bd C + bd C − ȳ = ȳ − bd IR_{+}^{d} + ȳ − bd IR_{+}^{d} − ȳ ⊆ −IR_{+}^{d} + ȳ = cl C.

So we can apply the subadditivity of z and derive

z(g(x) − h(x)) > z(g(x̄) − h(x̄)) ≥ z(g(x̄)) − z(h(x̄))

for all x ∈ X with g(x) − h(x) ≠ g(x̄) − g(x̄).

Remark 4.1 Theorem 4.1 gives a lower bound for optimal solutions of the scalarized problem. From Theorem 3.3 (a) we get that any solution of the scalarized problem is a weakly efficient element of the multicriteria problem.

Theorem 4.2 (Sufficient condition) Consider a functional z = z_{γ,k,w} defined by (8), where γ is an oblique norm, k ∈ bd B_{γ} ∩ int IR_{+}^{d} arbitrary and w = g(x̄) − h(x̄) − k. Assume x̄ ∈ X to be a solution of the scalarized problem

z(g(x) − h(x)) → min, x ∈ X.

Then we get g(x̄) − h(x̄) ∈ E((g − h)[X], IR_{+}^{d}).

Proof. The assertion follows from Theorem 3.3 (iii).

5 Conclusions

Gerth (Tammer) and Weidner [2] introduced a general nonlinear scalarization method using a functional z_{γ,k,w} : IR^{d} → IR defined by

z_{γ,k,w}(y) := inf{τ ∈ IR : y ∈ τk + C + w},  y ∈ IR^{d},  (14)

where k ∈ int IR_{+}^{d}, w ∈ IR^{d}, C ⊂ IR^{d}.

In our paper, we have considered a special polyhedral structure of the set C in the definition of the functional z = z_{γ,k,w} which is useful from the theoretical as well as from the numerical point of view. We have presented characterizations of efficient and weakly efficient elements of multicriteria optimization problems on the base of this scalarization concept. Furthermore, we have applied our results for the case of multicriteria d.c. problems.

In Theorem 4.1 we have derived a lower bound in d.c structure for the objective function values of the scalarized multicriteria d.c. problem. Now it is possible to apply methods from real-valued d.c. optimization (cf. Horst and Thoai [3] and Horst and Tuy [4]) for obtaining lower bounds for d.c. programs. Especially, a Lagrangian decomposition method given by Carrizosa [1] is applicable. Here the special structure of our scalarizing functional defined via block norms with polyhedral unit balls is very useful for the application of polyhedral branching schemes.

Furthermore, regarding Theorem 4.1, it is possible to apply under additional assumptions duality assertions for real-valued d.c. problems investigated by Martinez-Legaz and Volle, [10], in order to obtain lower bounds for the d.c. problem.

References

[1] E. Carrizosa: An optimal bound for d.c. programs with convex constraints. Mathematical Methods of Operations Research 54, 47-51, 2001.

[2] Chr. Gerth (Tammer), P. Weidner: Nonconvex separation theorems and some applications in vector optimization. J. Optim. Theory Appl. 67 (2), 297-320, 1990.

[3] R. Horst, N.V. Thoai: DC programming: Overview. Journal of Optimization Theory and Applications 103, 1-43, 1999.

[4] R. Horst, H. Tuy: Global optimization. Deterministic approaches. Springer Verlag, Berlin, 1996.

[5] J. Jahn: Scalarization in vector optimization. Mathematical Programming 29, 203-218, 1984.

[6] I. Kaliszewski: Qualitative Pareto Analysis by Cone Separation Technique. Kluwer Academic Publishers, Boston/Dordrecht/London 1994.

[7] K. Klamroth, B. Schandl, M. M. Wiecek: Using block norms in bicriteria optimization. In: Research and Practice in Multiple Criteria Decision Making (Charlottesville, VA, 1998). Lect. Notes in Econ. Math. Systems 487, 149-160, 2000.

[8] K. Klamroth, B. Schandl, M. M. Wiecek: Introducing oblique norms into multiple criteria programming. In preparation.

[9] A. Lewandowski, A. Wierzbicki: Aspiration based decision analysis. Part I: Theoretical and methodological backgrounds. Working Paper WP-88-03, International Institute for Applied Systems Analysis, Laxemburg, Austria, 1988.

[10] J.-E. Martinez-Legaz, M. Volle: Duality for d.c. optimization over compact sets. In preparation.

[11] R. T. Rockafellar: Convex Analysis. 10. print. (Princeton Landmarks in Mathematics), Princeton University Press, 1997.

[12] P. Schönfeld: Some duality theorems for the nonlinear vector maximum problem. Unternehmensforschung 14, 51-63, 1970.

[13] R.E. Steuer, E.U. Choo: An interactive weighted Tchebycheff procedure for multiple objective programming. Mathematical Programming 26, 326-344, 1983.

[14] J.E. Ward, R.E. Wendell: Using block norms for location modelling. Operations Research 33, 1074-1090, 1985.

[15] P. Weidner: The influence of proper efficiency on optimal solutions of scalarizing problems in multicriteria optimization. OR Spektrum 16, 255-260, 1994.

[16] P.L. Yu: A class of solutions for decision problems. Management Science, 19, 936-946, 1973.