A normal form for the feasible set of optimization problems

Matthias Sekatzek Martin–Luther–Universität Halle–Wittenberg Fachbereich Mathematik und Informatik Institut für Optimierung und Stochastik D-06099 Halle/Saale Germany

Abstract The purpose of this paper is to propose a normal form for the analytical description of the feasible set. In the normal form, the restrictions only consist of equations and inclusions with respect to a convex cone with nonempty interior. As an application, there is considered a multiplier rule of Breckner. Keywords: feasible set, convex cone, multiobjective optimization, multiplier rule, complementarity condition 1991 Mathematics Subject Classification: Primary: 52A20, Secondary: 90C29

1 Introduction

In this paper we consider a general optimization problem

f_{1}(x) ⟶ max_{x∈S}  (1)

with respect to the feasible set

S = {x ∈ X; f_{2}(x) ∈ K_{2}, f_{3}(x) ∈ K_{3}},  (2)

where X is a nonempty set, f_{1} is an arbitrary function defined on X, f_{2} is a mapping from X to R^{m_{2}}, f_{3} is a mapping from X to R^{m_{3}}, and K_{2} and K_{3} are closed convex cones in the spaces R^{m_{2}} and R^{m_{3}}, respectively. In the case m_{2} = 0 or m_{3} = 0, we will take the corresponding constraint for not present.

Additionally, we claim int K_{2} ≠ ∅. Feasible sets of that type are considered in [1], [2], [4], [6], for instance. As a special case of (2), we get the feasible set S = {x ∈ X; f_{2}(x) ≥ 0, f_{3}(x) = 0} by setting K_{2} = R_{+}^{m_{2}} and K_{3} = {0}. Problems of this kind are well–known; remember the almost classical results of Carathèodory and John, as well as Karush, Kuhn, and Tucker (compare [3]).

The studies on the structure of the feasible set were motivated by a result given in [1]. There the author proved a multiplier rule (see also Proposition 4) with different conditions concerning the constraints f_{2}(x) ∈ K_{2} and f_{3}(x) ∈ K_{3}. In particular, to an optimal solution x_{0} ∈ X has to exist a multiplier λ_{2}^{∗} ∈ K_{2}^{∗}, such that the complementarity condition

λ_{2}^{∗}^{⊤}f_{2}(x_{0}) = 0  (3)

holds. Comparing this result with the stucture of the muliplier rules given in [4], Satz 3.3.9. or [6], theorem 2, we asked if for the multiplier λ_{3}^{∗} ∈ K_{3}^{∗} a similar complementarity condition

λ_{3}^{∗}^{⊤}f_{3}(x_{0}) = 0  (4)

could be proved, too.

The only difference between the constraints f_{2}(x) ∈ K_{2} and f_{3}(x) ∈ K_{3} is the claim int K_{2} ≠ ∅. If we have additionally int K_{3} ≠ ∅, the condition (4) can be received analogously to (3). In contrary, if we have K_{3} = {0}, the condition (4) is fulfilled trivially, because of f_{3}(x_{0}) ∈ K_{3}.

So, the case int K_{3} = ∅ and K_{3} ≠ {0} is of special interest. We will show that in this case it is possible to give an analytical description of S in the form

S = \{x ∈ X; \overline{f}_{2}(x) ∈ \overline{K}_{2}, \overline{f}_{3}(x) = 0\},  (5)

with certain mappings \overline{f}_{2} : X → R^{\overline{m}^{2}}, \overline{f}_{3} : X → R^{\overline{m}^{3}}, and a closed convex cone \overline{K}_{2} ∈ R^{\overline{m}^{2}} with int \overline{K}_{2} ≠ ∅, where \overline{m}_{2} + \overline{m}_{3} = m_{2} + m_{3}. The form (5) shall be called normal form of the feasible set S.

2 The transformation theorem

First we study three examples:

Example 1 Set K := R_{+}^{2}. This cone is convex, but has a nonempty interior.

Example 2 Set K := R_{+}^{2} \ int R_{+}^{2}. Indeed, this cone has an empty interior, but it is not convex.

Example 3 Set K := {(x_{1}, x_{2})^{⊤} ∈ R_{+}^{2}; x_{1} = x_{2}}. Here, we have a convex cone with empty interior. Note, that this cone lies in a one–dimensional subspace of R^{2}.

From Example 3, we get the conjecture that every convex cone K ⊆ R^{n} with int K = ∅ lies in a (n − 1)–dimensional subspace of R^{n}. This conjecture is true, as shown in the following:

Lemma 1 A convex cone K in R^{n} with int K = ∅ contains at most n−1 linearly independent vectors.

Proof. Let K ⊆ R^{n} be such a cone. Assume there were n linearly independent vectors {x_{1}, x_{2}, …, x_{n}} ⊂ K. Then these vectors build up a base of the space R^{n}.

Consider y := x_{1} + x_{2} + ⋯ + x_{n}. Due to the convexity of K yields y ∈ K. We will show, that y is an interior point of K.

Any arbitrary u ∈ R^{n} can be represented as a linear combination of basic vectors:

u = α_{1}x_{1} + α_{2}x_{2} + ⋯ + α_{n}x_{n}.

With this represention, we define the following norm in R^{n}:

∥u∥_{max} := max_{i=1,...,n} |α_{i}|.

(It is easily seen, that ∥.∥_{max} fulfills the norm axioms.) Because of the equivalence of all norms in R^{n} there is a constant c > 0, so that holds

c∥u∥_{max} ≤ ∥u∥ ∀u ∈ R^{n},

where ∥.∥ is the ordinary euclidean norm.

Consider now a neighbourhood U of the origin, given by U := {u ∈ R^{n}; ∥u∥ < c}. Choose u = α_{1}x_{1} + α_{2}x_{2} + ⋯ + α_{n}x_{n} arbitrary in U. Then we have

c max_{i=1,...,n} |α_{i}| = c∥u∥_{max} ≤ ∥u∥ < c
max_{i=1,...,n} |α_{i}| < 1
|α_{i}| < 1  (i = 1, …, n).

Consequently, for all u ∈ U we have

y + u = (1 + α_{1})x_{1} + (1 + α_{2})x_{2} + ⋯ + (1 + α_{n})x_{n} ∈ K,

since, because of 1 + α_{i} > 0 (i = 1, …, n), the linear combination above is an element of the cone K.

So, it is shown y + U ⊂ K, and therefore, y is an interior point of K. But this contradicts the supposition. The assumption is proved to be wrong, and hence, there are at most n − 1 linearly independent vectors in K.

Using this lemma, we get the following result:

Proposition 2 Let K ⊆ R^{m}(m ≥ 2) be a closed convex cone with int K = ∅ and K ≠ {0}. Then there exists a natural number k (1 ≤ k ≤ m − 1), a closed convex cone \overline{K} ⊆ R^{m−k} with int \overline{K} ≠ ∅ and real numbers a_{ij} (i = 1, 2, …, k; j = k + 1, …, m), such that K (possibly after changing the arrangement of the coordinates) has the representation

K = \{( ∑_{j=k+1}^{m} a_{1j}y_{j} ; ⋮ ; ∑_{j=k+1}^{m} a_{kj}y_{j} ; y_{k+1} ; ⋮ ; y_{m} ); ( y_{k+1} ; ⋮ ; y_{m} ) ∈ \overline{K}\} .  (6)

Proof. Step 1: According Lemma 1, K contains at most m − 1 linearly independent vectors. Hence there is a (m − 1)–dimensional hyperplane E^{(1)} in R^{m} containing K. This hyperplane let be

E^{(1)} := {( y_{1} ; ⋮ ; y_{m} ) ∈ R^{m}; λ_{0}^{(1)} + λ_{1}^{(1)}y_{1} + ⋯ + λ_{m}^{(1)}y_{m} = 0}

with K ⊆ E^{(1)}.

Since K is a cone the origin belongs to E^{(1)}, hence λ_{0}^{(1)} = 0. Further there is a λ_{i}^{(1)} (i = 1, …, m) with λ_{i}^{(1)} ≠ 0. Let be λ_{1}^{(1)} ≠ 0 (possibly after re–arrange the coordinates). Without loss of generality set λ_{1}^{(1)} = 1.

E^{(1)} = {( y_{1} ; ⋮ ; y_{m} ) ∈ R^{m}; y_{1} + λ_{2}^{(1)}y_{2} + ⋯ + λ_{m}^{(1)}y_{m} = 0} .

We define

K^{(1)} := {( y_{2} ; ⋮ ; y_{m} ) ∈ R^{m−1}; ∃y_{1} ∈ R^{1} : ( y_{1} ; y_{2} ; ⋮ ; y_{m} ) ∈ K} .

(That implies, K^{(1)} is the projection of K onto the subspace {(y_{1}, y_{2}, …, y_{m})^{⊤} ∈ R^{m}; y_{1} = 0}.) Due to the properties of K, also K^{(1)} is a closed convex cone.

Obviously the following conditions are equivalent:

( y_{1} ; ⋮ ; y_{m} ) ∈ K ⟺ ( y_{1} ; ⋮ ; y_{m} ) ∈ K ∩ E^{(1)}

⟺ \{ \begin{matrix}y_{1} + λ_{2}^{(1)}y_{2} + ⋯ + λ_{m}^{(1)}y_{m} = 0 \\ ( y_{1} ; ⋮ ; y_{m} ) ∈ K \end{matrix} \}

⟺ \{ \begin{matrix}y_{1} + λ_{2}^{(1)}y_{2} + ⋯ + λ_{m}^{(1)}y_{m} = 0 \\ ( y_{2} ; ⋮ ; y_{m} ) ∈ K^{(1)} \end{matrix} \}

Case 1: int K^{(1)} ≠ ∅. Then we get the expression (6) by setting:

k := 1,
a_{1j} := −λ_{j}^{(1)}  (j = 2, …, m),
\overline{K} := K^{(1)},

and the proposition is proved.

Case 2: int K^{(1)} = ∅. Then we go on with step 2.

Step 2: According Lemma 1 again, there is a (m − 2)–dimensional hyperplane E^{(2)} in R^{m−1} containing K^{(1)}:

K^{(1)} ⊆ E^{(2)} := {( y_{2} ; ⋮ ; y_{m} ) ∈ R^{m−1}; y_{2} + λ_{3}^{(2)}y_{3} + ⋯ + λ_{m}^{(2)}y_{m} = 0} .

Analogously to step 1 we define a closed convex cone K^{(2)} in R^{m−2} by

K^{(2)} := {( y_{3} ; ⋮ ; y_{m} ) ∈ R^{m−2}; ∃y_{2} ∈ R^{1} : ( y_{2} ; y_{3} ; ⋮ ; y_{m} ) ∈ K^{(1)}} ,

and we conclude

( y_{2} ; ⋮ ; y_{m} ) ∈ K^{(1)} ⟺ \{ \begin{matrix}y_{2} + λ_{3}^{(2)}y_{3} + ⋯ + λ_{m}^{(2)}y_{m} = 0 \\ ( y_{3} ; ⋮ ; y_{m} ) ∈ K^{(2)} \end{matrix} \} ,

hence

( y_{1} ; ⋮ ; y_{m} ) ∈ K ⟺ \{ \begin{matrix}y_{1} + λ_{2}^{(1)}y_{2} + λ_{3}^{(1)}y_{3} + ⋯ + λ_{m}^{(1)}y_{m} = 0 \\ y_{2} + λ_{3}^{(2)}y_{3} + ⋯ + λ_{m}^{(2)}y_{m} = 0 \\ ( y_{3} ; ⋮ ; y_{m} ) ∈ K^{(2)} \end{matrix} \} .

Case 1: int K^{(2)} ≠ ∅. Then we get the expression (6) by setting:

k := 2,
a_{2j} := −λ_{j}^{(2)}  (j = 3, …, m),
a_{1j} := −λ_{2}^{(1)}a_{2j} − λ_{j}^{(1)}  (j = 3, …, m),
\overline{K} := K^{(2)},

and the proposition is proved.

Case 2: int K^{(2)} = ∅. Then we go on with step 3.

Step p (1 ≤ p ≤ m − 1): If the procedure has not stopped before, the step p runs like this: According Lemma 1 we find a (m − p)–dimensional hyperplane E^{(p)} in R^{m−p+1} with:

K^{(p−1)} ⊆ E^{(p)} := {( y_{p} ; ⋮ ; y_{m} ) ∈ R^{m−p+1}; y_{p} + λ_{p+1}^{(p)}y_{p+1} + ⋯ + λ_{m}^{(p)}y_{m} = 0} .

We define a closed convex cone K^{(p)} in R^{m−p}:

K^{(p)} := {( y_{p+1} ; ⋮ ; y_{m} ) ∈ R^{m−p}; ∃y_{p} ∈ R^{1} : ( y_{p} ; y_{p+1} ; ⋮ ; y_{m} ) ∈ K^{(p−1)}} ,

and we conclude

( y_{1} ; ⋮ ; y_{m} ) ∈ K ⟺ { y_{1} + λ_{2}^{(1)}y_{2} + λ_{3}^{(1)}y_{3} + ⋯ + λ_{m}^{(1)}y_{m} = 0 ; ⋮ ; y_{p} + λ_{p+1}^{(p)}y_{p+1} + ⋯ + λ_{m}^{(p)}y_{m} = 0 ; ( y_{p+1} ; ⋮ ; y_{m} ) ∈ K^{(p)} } .

Case 1: int K^{(p)} ≠ ∅. Then we get the expression (6) by setting:

k := p,
a_{pj} := −λ_{j}^{(p)}  (j = p + 1, …, m),
a_{p−1,j} := −λ_{2}^{(p−1)}a_{2j} − λ_{j}^{(p−1)}  (j = p + 1, …, m),
⋮
a_{1j} := −λ_{2}^{(1)}a_{2j} − λ_{3}^{(1)}a_{3j} − ⋯ − λ_{p}^{(1)}a_{pj} − λ_{j}^{(1)}  (j = p + 1, …, m),
\overline{K} := K^{(p)},

and the proposition is proved.

Case 2: int K^{(p)} = ∅. Then we go on with step p + 1.

This proving procedure stops at the latest in step m−1 by entering case 1. Otherwise, in step m−1 we would get a cone K^{(m−1)} with int K^{(m−1)} = ∅. Because of K^{(m−1)} ⊆ R^{1} yields K^{(m−1)} = {0}. (For this is the only cone in R^{1} with empty interior.) Then we have

( y_{1} ; ⋮ ; y_{m} ) ∈ K ⟺ { y_{1} + λ_{2}^{(1)}y_{2} + ⋯ + λ_{m}^{(1)}y_{m} = 0 ; ⋮ ; y_{m−1} + λ_{m}^{(m−1)}y_{m} = 0 ; y_{m} ∈ K^{(m−1)} }

⟺ { y_{1} + λ_{2}^{(1)}y_{2} + ⋯ + λ_{m}^{(1)}y_{m} = 0 ; ⋮ ; y_{m−1} + λ_{m}^{(m−1)}y_{m} = 0 ; y_{m} = 0 }

⟺ ( y_{1} ; ⋮ ; y_{m} ) = ( 0 ⋮ 0 ) .

But this implies K = {0}, which contradicts the supposition.

From proposition 2, it follows easily:

Proposition 3 (Existence of a normal form) Let S be a feasible set given by

S := {x ∈ X; f_{2}(x) ∈ K_{2}, f_{3}(x) ∈ K_{3}},

with a nonempty set X, a mapping f_{2} : X → R^{m_{2}}, a mapping f_{3} : X → R^{m_{3}}, and two closed convex cones K_{2} ⊆ R^{m_{2}} and K_{3} ⊆ R^{m_{3}} (int K_{2} ≠ ∅).

Then there exists a natural number k (0 ≤ k ≤ m_{3}), a mapping \overline{f}_{2} : X → R^{m_{2}+m_{3}−k}, a mapping \overline{f}_{3} : X → R^{k}, and a closed convex cone \overline{K}_{2} ⊆ R^{m_{2}+m_{3}−k} with int \overline{K}_{2} ≠ ∅, such that

S = \{x ∈ X; \overline{f}_{2}(x) ∈ \overline{K}_{2}, \overline{f}_{3}(x) = 0\}.

In particular, the components of \overline{f}_{2} and \overline{f}_{3} just are linear combinations of the components of f_{2} and f_{3}.

Proof. If int K_{3} ≠ ∅ set

k := 0,
\overline{f}_{2}(x) := ( \begin{matrix}f_{2}(x) \\ f_{3}(x) \end{matrix} ) : X → R^{m_{2}+m_{3}},
\overline{K}_{2} := K_{2} × K_{3} ⊆ R^{m_{2}+m_{3}}.

Conditions in equality form are not present (i.e. \overline{m}_{3} = k = 0). Verifying int \overline{K}_{2} = int K_{2} × int K_{3} ≠ ∅ the proof is done.

If K_{3} = {0} set

k := m_{3},
\overline{f}_{2}(x) := f_{2}(x),
\overline{f}_{3}(x) := f_{3}(x),
\overline{K}_{2} := K_{2}.

Here is nothing to do because S is already given in normal form.

Else, if intK_{3} = ∅ and K_{3} ≠ {0} we can apply proposition 2. (This case is only possible if m_{3} ≥ 2.) Thus, we have the following equivalence:

( f_{3,1}(x) ; ⋮ ; f_{3,m_{3}}(x) ) ∈ K_{3} ⟺ \{ f_{3,1}(x) = ∑_{j=k+1}^{m_{3}} a_{1j}f_{3,j}(x) ; ⋮ ; f_{3,k}(x) = ∑_{j=k+1}^{m_{3}} a_{kj}f_{3,j}(x) ; ( f_{3,k+1}(x) ; ⋮ ; f_{3,m_{3}}(x) ) ∈ \overline{K}_{3} \}

with some natural k (1 ≤ k ≤ m − 1), some reals a_{ij} (i = 1, 2, …, k; j = k + 1, …, m_{3}), and a closed convex cone \overline{K}_{3} ⊆ R^{m_{3}−k} with int \overline{K}_{3} ≠ ∅.

Setting

\overline{f}_{2}(x) := ( f_{2,1}(x) ; ⋮ ; f_{2,m_{2}}(x) ; f_{3,k+1}(x) ; ⋮ ; f_{3,m_{3}}(x) ) : X → R^{m_{2}+m_{3}−k},

\overline{f}_{3}(x) := ( f_{3,1}(x) − ∑_{j=k+1}^{m_{3}} a_{1j}f_{3,j}(x) ; ⋮ ; f_{3,k}(x) − ∑_{j=k+1}^{m_{3}} a_{kj}f_{3,j}(x) ) : X → R^{k},

\overline{K}_{2} := K_{2} × \overline{K}_{3} ⊆ R^{m_{2}+m_{3}−k}

and verifying int \overline{K}_{2} = int K_{2} × int \overline{K}_{3} ≠ ∅, the proof is done.

3 Application: Extension of a theorem of Breckner

First, we will state Breckner’s multiplier rule and its background. Consider the optimization problem

f_{1}(x) ⟶ K_{1} − Max!
f_{2}(x) ∈ K_{2},  (P)
f_{3}(x) ∈ K_{3},
x ∈ X,

where X is a nonempty subset of a topological space, f_{1} : X → R^{m_{1}}, f_{2} : X → R^{m_{2}}, f_{3} : X → R^{m_{3}} are some functions, and K_{1} ⊆ R^{m_{1}}, K_{2} ⊆ R^{m_{2}}, K_{3} ⊆ R^{m_{3}} are convex cones, of which K_{1} and K_{2} have a nonempty interior, while K_{2} and K_{3} are closed.

In the following, we set:

m := m_{1} + m_{2} + m_{3},
f(x) := ( \begin{matrix}f_{1}(x) \\ f_{2}(x) \\ f_{3}(x) \end{matrix} ) : X → R^{m},
K := K_{1} × K_{2} × K_{3} ⊆ R^{m}.

Definition 1 A point x_{0} ∈ X is called a local weakly K_{1}–maximal point of (P) if x_{0} ∈ S and if there is a neighbourhood V of x_{0} such that

[f_{1}(x_{0}) + int K_{1}] ∩ f_{1}(S ∩ V) = ∅.

Definition 2 An n–tuple {d^{1}, …, d^{n}} of points in the space R^{m} is called a K–gradient of f at x_{0} if there exist a number r > 0, a function ω : B_{+}^{n}(r) → X (B_{+}^{n}(r) := {x ∈ R_{+}^{n}; ∥x∥ ≤ r}), and a function ρ = (ρ_{1}, ρ_{2}, ρ_{3})^{⊤} : B_{+}^{n}(r) → R^{m_{1}} × R^{m_{2}} × R^{m_{3}} such that the following conditions are satisfied:

(A) we have

f(ω(t)) − f(x_{0}) − (t_{1}d^{1} + ⋯ + t_{n}d^{n}) − ∥t∥ρ(t) ∈ K ∀t = (t_{1}, …, t_{n})^{⊤} ∈ B_{+}^{n}(r),

(B) ω(0) = x_{0} and ω is continous at 0,

(C1) there exists a point y_{1}^{0} ∈ K_{1} so that for each number ϵ > 0 there is a number r_{ϵ} ∈]0, r] such that

ρ_{1}(t) + ϵy_{1}^{0} ∈ K_{1} ∀t ∈ B_{+}^{n}(r_{ϵ}),

(C2) there exists a point y_{2}^{0} ∈ K_{2} so that for each number ϵ > 0 there is a number r_{ϵ} ∈]0, r] such that

ρ_{2}(t) + ϵy_{2}^{0} ∈ K_{2} ∀t ∈ B_{+}^{n}(r_{ϵ}),

(C3) ρ_{3}(0) = 0 and ρ_{3} is continous.

Definition 3 A nonempty subset D ⊆ R^{m} is called:

• a K–derived set for f at x_{0} if every (m+1)–tuple of points belonging to D is a K–gradient of f at x_{0},

• a K–derived convex cone for f at x_{0} if it is both a K–derived set for f at x_{0} and a convex cone.

Proposition 4 (Breckner’s multiplier rule, [1]) Let x_{0} ∈ X be a local weakly K_{1}-maximal point of (P) and let D ∈ R^{m} be an K-derived convex cone for f at x_{0}. Then there exists a multiplier vector λ^{∗} = (λ_{1}^{∗}, λ_{2}^{∗}, λ_{3}^{∗})^{⊤} ∈ K_{1}^{∗} × K_{2}^{∗} × K_{3}^{∗}, λ^{∗} ≠ 0, such that

λ^{∗}^{⊤}d ≤ 0  ∀d ∈ D,
λ_{2}^{∗}^{⊤}f_{2}(x_{0}) = 0.

Needless to say, that the search for an additional condition (4)

λ_{3}^{∗}^{⊤}f_{3}(x_{0}) = 0

becomes uninterestingly, if we claim that (P) is given in normal form. For we have proved that every feasible set of (P) can be transformed into its normal form, the problem mentioned in the introduction can be considered as solved.

But in supplement of this, using the special structure of the transformation formula (6), it is possible to show that (4) holds even if the feasible set of (P) has not its normal form. That shall be demonstrated in the following.

First we claim:

(i) int K_{3} = ∅ and K_{3} ≠ {0}.

(ii) Let x_{0} ∈ X be a local weakly K_{1}-maximal point of (P).

(iii) Let D ∈ R^{m} be an K-derived convex cone for f at x_{0}.

1. Construction of a problem (\overline{P}) equivalent to (P) with the feasible set in normal form We apply proposition 2 and set (as done in of the proof of proposition 3):

\overline{f}_{2}(x) := ( f_{2,1}(x) ; ⋮ ; f_{2,m_{2}}(x) ; f_{3,k+1}(x) ; ⋮ ; f_{3,m_{3}}(x) ) : X → R^{m_{2}+m_{3}−k},

\overline{f}_{3}(x) := ( f_{3,1}(x) − ∑_{j=k+1}^{m_{3}} a_{1j}f_{3,j}(x) ; ⋮ ; f_{3,k}(x) − ∑_{j=k+1}^{m_{3}} a_{kj}f_{3,j}(x) ) : X → R^{k},

\overline{K}_{2} := K_{2} × \overline{K}_{3} ⊆ R^{m_{2}+m_{3}−k}.

Therefore, the problem

f_{1}(x) ⟶ K_{1} − Max!
\overline{f}_{2}(x) ∈ \overline{K}_{2},  (\overline{P})
\overline{f}_{3}(x) = 0,
x ∈ X

is equivalent to (P). Note, that int \overline{K}_{3} and also int \overline{K}_{2} are nonempty. From (ii) we get:

(iv) x_{0} is a local weakly K_{1}-maximal point of (\overline{P}).

Set

\overline{f}(x) := ( \begin{matrix}f_{1}(x) \\ \overline{f}_{2}(x) \\ \overline{f}_{3}(x) \end{matrix} ) : X → R^{m},
\overline{K} := K_{1} × \overline{K}_{2} × \{0\} ⊆ R^{m}.

2. Construction of a \overline{K}–derived convex cone \overline{D} for \overline{f} at x_{0} Based on the set D we define a set \overline{D} ∈ R^{m} by: A point \overline{d} = (\overline{d}_{1}, \overline{d}_{2}, \overline{d}_{3})^{⊤} ∈ R^{m_{1}} × R^{m_{2}+m_{3}−k} × R^{k} belongs to \overline{D} if and only if there is an element d ∈ D (d = (d_{1}, d_{2}, d_{3})^{⊤} ∈ R^{m_{1}} × R^{m_{2}} × R^{m_{3}}) with

\overline{d}_{1} = d_{1},

\overline{d}_{2} = ( d_{2,1} ; ⋮ ; d_{2,m_{2}} ; d_{3,k+1} ; ⋮ ; d_{3,m_{3}} ) ,  (7)

\overline{d}_{3} = ( d_{3,1} − ∑_{j=k+1}^{m_{3}} a_{1j}d_{3,j} ; ⋮ ; d_{3,k} − ∑_{j=k+1}^{m_{3}} a_{kj}d_{3,j} ) .

\overline{D} is a convex cone, because of D is one. Further, we will show:

(v) \overline{D} is a \overline{K}–derived convex cone for \overline{f} at x_{0}.

Choose an arbitrary (m + 1)–tuple \{\overline{d}^{1}, …, \overline{d}^{m+1}\} of points in \overline{D}. Then there is an (m + 1)–tuple \{d^{1}, …, d^{m+1}\} of points in D such that (7) holds for every corresponding \overline{d}^{l} and d^{l} (l = 1, …, m + 1). Due to (iii) {d^{1}, …, d^{m+1}} is a K–gradient of f at x_{0}, and therefore we have (A), (B), (C1), (C2), and (C3) with n = m + 1.

Using the terms r and ρ from (A) we define the function \overline{ρ} = (\overline{ρ}_{1}, \overline{ρ}_{2}, \overline{ρ}_{3})^{⊤} : B_{+}^{m+1}(r) → R^{m_{1}} × R^{m_{2}} × R^{m_{3}} by

\overline{ρ}_{1}(t) := ρ_{1}(t),

\overline{ρ}_{2}(t) := ( ρ_{2,1}(t) ; ⋮ ; ρ_{2,m_{2}}(t) ; ρ_{3,k+1}(t) ; ⋮ ; ρ_{3,m_{3}}(t) ) ,

\overline{ρ}_{3}(t) := ( ρ_{3,1}(t) − ∑_{j=k+1}^{m_{3}} a_{1j}ρ_{3,j}(t) ; ⋮ ; ρ_{3,k}(t) − ∑_{j=k+1}^{m_{3}} a_{kj}ρ_{3,j}(t) ) .

With the function ω given in (A) it follows from (A): (\overline{A}) we have

\overline{f}(ω(t)) − \overline{f}(x_{0}) − (t_{1}\overline{d}^{1} + ⋯ + t_{m+1}\overline{d}^{m+1}) − ∥t∥\overline{ρ}(t) ∈ \overline{K} ∀t = (t_{1}, …, t_{m+1})^{⊤} ∈ B_{+}^{m+1}(r). From (C3) we have on the one hand

(\overline{C3}) \overline{ρ}_{3}(0) = ( ρ_{3,1}(0) − ∑_{j=k+1}^{m_{3}} a_{1j}ρ_{3,j}(0) ; ⋮ ; ρ_{3,k}(0) − ∑_{j=k+1}^{m_{3}} a_{kj}ρ_{3,j}(0) ) = 0 and ρ_{3} is continous,

and on the other hand

(C3)’ ( ρ_{3,k+1}(0) ; ⋮ ; ρ_{3,m_{3}}(0) ) = 0 and ( ρ_{3,k+1}(.) ; ⋮ ; ρ_{3,m_{3}}(.) ) is continous.

Because of int \overline{K}_{3} ≠ ∅ it follows from (C3)’ (compare [1], remark 3.1.): (C3)” there exists a point \overline{y}_{3}^{0} ∈ \overline{K}_{3} so that for each number ϵ > 0 there is a number r_{ϵ} ∈]0, r] such that

( ρ_{3,k+1}(t) ; ⋮ ; ρ_{3,m_{3}}(t) ) + ϵ\overline{y}_{3}^{0} ∈ \overline{K}_{3} ∀t ∈ B_{+}^{m+1}(r_{ϵ}).

From (C2) and (C3)” we get: (\overline{C3}) there exists a point \overline{y}_{2}^{0} ∈ \overline{K}_{2} so that for each number ϵ > 0 there is a number r_{ϵ} ∈]0, r] such that

\overline{ρ}_{2}(t) + ϵ\overline{y}_{2}^{0} ∈ \overline{K}_{3} ∀t ∈ B_{+}^{m+1}(r_{ϵ}).

(To prove this, set \overline{y}_{2}^{0} := (y_{2}, \overline{y}_{3})^{⊤} and take for r_{ϵ} the minimum of the r_{ϵ} from (C2) and (C3)”.) With (\overline{A}), (B), (C1), (\overline{C2}), and (\overline{C3}), the assertion (v) is shown.

3. Application of proposition 4 on (\overline{P}) Due to (iv) and (v) there is a multiplier vector \overline{λ}^{∗} = (\overline{λ}_{1}^{∗}, \overline{λ}_{2}^{∗}, \overline{λ}_{3}^{∗})^{⊤} ∈ K_{1}^{∗} × \overline{K}_{2}^{∗} × R^{k} \ \{0\},

such that

\overline{λ}^{∗}^{⊤}\overline{d} ≤ 0 ∀\overline{d} ∈ \overline{D}, (8)
\overline{λ}_{2}^{∗}^{⊤}\overline{f}_{2}(x_{0}) = 0.  (9)

We define

λ_{1}^{∗} := \overline{λ}_{1}^{∗},
λ_{2}^{∗} := ( \overline{λ}_{2,1}^{∗} ; ⋮ ; \overline{λ}_{2,m_{2}}^{∗} ) ,

λ_{3}^{∗} := ( \overline{λ}_{3,1}^{∗} ; ⋮ ; \overline{λ}_{3,k}^{∗} ; \overline{λ}_{2,m_{2}+1}^{∗} − ∑_{i=1}^{k} \overline{λ}_{3,i}^{∗}a_{i,k+1} ; ⋮ ; \overline{λ}_{2,m_{2}+m_{3}−k}^{∗} − ∑_{i=1}^{k} \overline{λ}_{3,i}^{∗}a_{i,m_{3}} ) .

By construction, it is

(λ_{1}^{∗}, λ_{2}^{∗}, λ_{3}^{∗})^{⊤} ≠ 0,
λ_{1}^{∗} ∈ K_{1}^{∗},
λ_{2}^{∗} ∈ K_{2}^{∗},

( λ_{3,k+1}^{∗} + ∑_{i=1}^{k} λ_{3,i}^{∗}a_{i,k+1} ; ⋮ ; λ_{3,m_{3}}^{∗} + ∑_{i=1}^{k} λ_{3,i}^{∗}a_{i,m_{3}} ) = ( \overline{λ}_{2,m_{2}+1}^{∗} ; ⋮ ; \overline{λ}_{2,m_{2}+m_{3}−k}^{∗} ) ∈ \overline{K}_{3}^{∗}.

Take an arbitrary y_{3} ∈ K_{3}. Then we have by proposition 2 y_{3,i} = ∑_{j=k+1}^{m_{3}} a_{ij}y_{3,j} (i = 1, …, k) and (y_{3,k+1}, …, y_{3,m_{3}})^{⊤} ∈ \overline{K}_{3}. Thus

λ_{3}^{∗}^{⊤}y_{3} = ∑_{i=1}^{k} λ_{3,i}^{∗} [ ∑_{j=k+1}^{m_{3}} a_{ij}y_{j}] + ∑_{j=k+1}^{m_{3}} λ_{3,j}^{∗}y_{j}

= ∑_{j=k+1}^{m_{3}} [λ_{3,j}^{∗} + ∑_{i=1}^{k} λ_{3,i}^{∗}a_{ij}] y_{j}

= ( λ_{3,k+1}^{∗} + ∑_{i=1}^{k} λ_{3,i}^{∗}a_{i,k+1} ; ⋮ ; λ_{3,m_{3}}^{∗} + ∑_{i=1}^{k} λ_{3,i}^{∗}a_{i,m_{3}} )^{⊤} ( y_{3,k+1} ; ⋮ ; y_{3,m_{3}} )

≥ 0,

in other words

λ_{3}^{∗} ∈ K_{3}^{∗}.

So, we have shown

λ^{∗} = (λ_{1}^{∗}, λ_{2}^{∗}, λ_{3}^{∗})^{⊤} ∈ K_{1}^{∗} × K_{2}^{∗} × K_{3}^{∗} \ {0}.  (10)

Further, we get

sup \{\overline{λ}^{∗}^{⊤}\overline{d}; \overline{d} ∈ \overline{D}\} = sup \{λ^{∗}^{⊤}d; d ∈ D\} ,
\overline{λ}_{2}^{∗}^{⊤}\overline{f}_{2}(x_{0}) = λ_{2}^{∗}^{⊤}f_{2}(x_{0}) + λ_{3}^{∗}^{⊤}f_{3}(x_{0}).

Hence, it follows from (8) and (9)

λ^{∗}^{⊤}d ≤ 0  ∀d ∈ D,  (11)
λ_{2}^{∗}^{⊤}f_{2}(x_{0}) = 0,  (12)
λ_{3}^{∗}^{⊤}f_{3}(x_{0}) = 0.  (13)

So, starting with (i), (ii), and (iii) we have received a multiplier vector λ^{∗} with (10), (11), (12), and (13). As explained in the indroduction, if (i) not holds, the conclusions (10), (11), (12), and (13) follow directly from propostion 4. This resultat is noted in the following theorem.

Proposition 5 (extended multiplier rule) Let x_{0} ∈ X be a local weakly K_{1}–maximal point of (P) and let D ∈ R^{m} be a K–derived convex cone for f at x_{0}. Then there exists a multiplier vector λ^{∗} = (λ_{1}^{∗}, λ_{2}^{∗}, λ_{3}^{∗})^{⊤} ∈ K_{1}^{∗} × K_{2}^{∗} × K_{3}^{∗}, λ^{∗} ≠ 0, such that

λ^{∗}^{⊤}d ≤ 0  ∀d ∈ D,
λ_{2}^{∗}^{⊤}f_{2}(x_{0}) = 0,
λ_{3}^{∗}^{⊤}f_{3}(x_{0}) = 0.

References

[1] Breckner, W.W. (1994). Derived sets in multiobjective optimization. Zeitschrift für Analysis und ihre Anwendungen 13, 725–738

[2] Nieuwenhuis, J.W. (1980) A general multiplier rule. Journal of Optimzation Theory and Applications 31, 167–176

[3] Pourciau, B.H. (1980) Modern multiplier rules. American Mathematical Monthly 87, 433–452

[4] Schirotzek, W. (1989) Differenzierbare Extremalprobleme. Eine Einführung. BSB B. G. Teubner Verlagsges., Leipzig

[5] Sekatzek, M. (1996) Multiplikatorenregeln für die multikriterielle Optimierung. Diplomarbeit, Halle

[6] Tuy, H. (1974) On the convex approximation of nonlinear inequalities. Mathematische Operationsforschung und Statistik 5, 451–466