Contributions to a Multiplier Rule for Multiobjective 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. In this paper, we will consider a necessary optimality condition in form of a multiplier rule for so–called K-derived sets, given by Breckner in 1994. For this multiplier rule, we present an alternative method of proof, without making use of the theorem of Hoang Tuy that was needed in Breckner’s original paper. Furthermore, for this rule it will be derived an additional complementarity relation as well as regularity conditions for the multipliers, the latter according to an idea of Hestenes for the scalar case.

1 Introduction

For to solve a nonlinear optimization problem succesfully, one needs in general such classical assumptions as differentiability or convexity. In recent time, much work has been done in weakening those assumptions for special problems in an appropriate way. The optimality condition considered in the present paper is a multiplier rule given by Breckner in [1]. Some applications of this rule can be found in [2]. In the latter paper it is also shown that both the differentiable case and the convex case are covered by Breckner’s theorem.

Breckner’s multiplier rule deals with so–called derived sets. The term of a derived set was introduced by Hestenes in [4]. There are some optimality conditions related with the theory of derived sets given in the papers [3], [5], [6], and [8]. But all these theorems aim at optimization problems with only one objective function. In [1], Hestenes’ definition has been extended onto problems with a multidimensional objective function. For distinction, Breckner called the new objects K-derived sets, where K is the ordering cone of the image space. Going this way, Breckner received a multiplier rule for a multiobjective optimization problem.

Note, that in [1] the author originally deals with a vector–maximizing problem. For compatibility reasons, in the given paper the terminology is transformed for a minimization problem. Correctly spoken, all K-derived sets considered here are (−K)-derived sets in the sense of [1].

Consider the optimization problem

f_{1}(x) ⟶ K_{1} − Min!  (1)

subject to

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

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. With K_{1}^{∗}, K_{2}^{∗}, and K_{3}^{∗} we describe the respective dual cones. Furthermore, let be

L := {y ∈ K_{2}^{∗}; ⟨y, f_{2}(x_{0})⟩ = 0}.  (3)

For short, we agree upon this:

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}.

According to this convention, every vector y ∈ R^{m} is understood as the triple y = (y_{1}, y_{2}, y_{3}) ∈ R^{m_{1}} × R^{m_{2}} × R^{m_{3}}.

Definition 1. A point x_{0} ∈ X is called a local weakly K_{1}-minimal point for the function f_{1} over S 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 (m + 1)–tuple {d_{1}, …, d_{m+1}} of points in the space R^{m} is called a K-derived convex cone for f at x_{0} if there exist a number r > 0, a function ω : B_{+}^{m+1}(r) → X (B_{+}^{m+1}(r) := {x ∈ R_{+}^{m+1}; ∥x∥ ≤ r}), and a function ϱ = (ϱ_{1}, ϱ_{2}, ϱ_{3}) : B_{+}^{m+1}(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^{m+1}d_{m+1}) − ∥t∥ϱ(t) ∈ −K
∀t = (t^{1}, …, t^{m+1}) ∈ B_{+}^{m+1}(r),

(B) ω(0) = x_{0} and ω is continuous 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_{+}^{m+1}(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_{+}^{m+1}(r_{ε}),

(C3) ϱ_{3}(0) = 0 and ϱ_{3} is continuous.

Now we are able to state the theorem to be considered.

Theorem 1. Let x_{0} ∈ X be a local weakly K_{1}-minimal point for the function f_{1} over S 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,  (4)
⟨λ_{2}, f_{2}(x_{0})⟩ = 0.  (5)

In section 2, we will give some remarks about the proof of Breckner’s theorem. On the one hand, we show that the multiplier rule can be proved without making use of a rather complicated linearization theorem of Tuy. Such a theorem as well Breckner in [1] as Nieuwenhuis in [8] needed. On the other hand, we give a proving idea, which seems to be more evident than the method Breckner used. In section 3, for this rule it will be derived the additional complementarity condition

⟨λ_{3}, f_{3}(x_{0})⟩ = 0,  (6)

missing in Theorem 1. Finally, in section 4 a regularity condition ensuring λ_{1} ≠ 0 in Theorem 1 is given.

2 Alternative Proving Methods

2.1 Proof without using the theory of nonlinear inequalities

Proving the multiplier rule, Breckner states the following assertion.

Proposition 1. Let t_{0} be a vector in the space R^{m}, let K be a closed convex cone in the space R^{p}, and let F : R^{m} → R^{p} be a continuous function, differentiable at the origin, satisfying the following conditions:

(i) F (0) ∈ −K,
(ii) F′(0)(t_{0}) ∈ −K,
(iii) F′(0)[R^{m}] − K = R^{p}.

Then there exist a sequence {a_{n}} (n = 1, 2, …) of positive numbers with lim_{n→∞} a_{n} = 0, and a sequence {t_{n}} (n = 1, 2, …) of vectors in the space R^{m} with lim_{n→∞} t_{n} = t_{0}, such that

F (a_{n}t_{n}) ∈ −K ∀n.

For the proof of this proposition, Breckner [1] refers to a result given by Tuy in [9]. In the latter paper, the author considers systems of nonlinear inequalities. Indeed, under the assumptions of proposition 1, the system

{x ∈ R^{m}; F (0) + F′(0)(x) ∈ −K}

is a local approximation at 0 of the system

{x ∈ R^{m}; F (x) ∈ −K}

in the terminology introduced in [9].

To see this, one must study the theory appearing in Tuy’s paper. But the result is only a very special case of Theorem 1 in [9]. Furthermore, proposition 1 can be formulated without any connection to inequality systems. So we asked whether it is possible to prove only the needed special case without using the theory in [9].

In the following, we will give such a proof. Before, we have to prove a lemma.

Lemma 1. Let U ⊂ R^{m} be a nonempty, convex, and compact set, let A : U → R^{p} be a continuous function, B : R^{m} → R^{p} be a linear function, and let K be a convex closed cone of the space R^{p}. Then the set–valued mapping Γ : U → 2^{U} given by

Γ (u) := {ũ ∈ U; A(u) ∈ B(ũ) − K}

possesses a fixed point, if for every u ∈ U the set Γ (u) is nonempty.

Proof. We will show that the assumptions of Kakutani’s fixed point theorem are fulfilled. So, we have to prove the mapping Γ to be closed, and the images Γ (u) to be convex and closed for every u ∈ U.

a) Closedness of Γ. Consider two converging sequences {u_{n}} ⊂ U and {ũ_{n}} ⊂ U with ũ_{n} ∈ Γ (u_{n}) ∀n, or equivalently

A(u_{n}) ∈ B(ũ_{n}) − K ∀n.

Let be u := lim_{n→∞} u_{n} and ũ := lim_{n→∞} ũ_{n}. Then u ∈ U and ũ ∈ U. By continuity of A and B and the closedness of K, it follows

A(u) ∈ B(ũ) − K,

what means ũ ∈ Γ (u).

b) Convexity of Γ (u) ∀u ∈ U. Let u ∈ U be fixed. Consider two arbitrary points ũ_{1} and ũ_{2} in Γ (u). Since U is convex, we have λũ_{1} + (1 − λ)ũ_{2} ∈ U ∀λ ∈ [0, 1]. Furthermore it is

A(u) = λA(u) + (1 − λ)A(u)
∈ λB(ũ_{1}) + (1 − λ)B(ũ_{2}) − K
= B(λũ_{1} + (1 − λ)ũ_{2}) − K  ∀λ ∈ [0, 1],

hence λũ_{1} + (1 − λ)ũ_{2} ∈ Γ (u) for all λ ∈ [0, 1].

c) Closedness of Γ (u) ∀u ∈ U. Let u ∈ U be fixed. Consider a converging sequence {ũ_{n}} ⊂ Γ (u) with ũ := lim_{n→∞} ũ_{n}. Since ũ_{n} ∈ U ∀n and the closedness of U, we have ũ ∈ U. From

A(u) ∈ B(ũ_{n}) − K ∀n

it follows by the continuity of B and the closedness of K

A(u) ∈ B(ũ) − K,

what means ũ ∈ Γ (u).

Remark 1. Lemma 1 is still valid, even if the linearity of function B is replaced by K-concavity.

Proof. (of Proposition 1) If t_{0} = 0, the proposition is fulfilled trivially choosing {t_{n}} = {0, 0, …} and an arbitrary sequence {a_{n}} of positive numbers converging to zero. So, in the following we assume t_{0} ≠ 0. For every natural number n = 1, 2, … let be U_{n} := \{u ∈ R^{m}; ∥u∥ ≤ \frac{1}{2n}\}. It is easily seen, that all sets U_{n} are convex, closed, and bounded, hence compact. Due to the linearity of F′(t_{0})(.) and condition (iii), the set

V_{n} := −(F′(t_{0})[U_{n}] + K)

is a neighbourhood of the origin of R^{p}. Taking into account

lim_{x→0} \frac{1}{∥x∥} [F (x) − F (0) − F′(0)(x)] = 0,

we find for every n a constant ε_{n} > 0, such that

F (x) − F (0) − F′(0)(x) ∈ ∥x∥V_{n} ∀x : ∥x∥ < ε_{n}.

Hence we have

F (x) ∈ F (0) + F′(0)(x) − ∥x∥ (F′(t_{0})[U_{n}] − K)
= F (0) + F′(0)(x) − ∥x∥F′(t_{0})[U_{n}] − K  ∀x : ∥x∥ < ε_{n} ∀n.

By (i), this implies

F (x) ∈ F′(0)(x) − ∥x∥F′(t_{0})[U_{n}] − K  ∀x : ∥x∥ < ε_{n} ∀n. (7)

Let {α_{n}} be a sequence of positive numbers converging to zero with

0 < α_{n} ≤ ε_{n} ∀n.

From

∥\frac{t_{0}}{2∥t_{0}∥} + u∥ ≤ \frac{∥t_{0}∥}{2∥t_{0}∥} + ∥u∥ ≤ \frac{1}{2} + \frac{1}{2n} < 1  ∀u ∈ U_{n} ∀n  (8)

therefore we get

∥α_{n} (\frac{t_{0}}{2∥t_{0}∥} + u)∥ < ε_{n} ∀u ∈ U_{n} ∀n.

So from (7) yields

F (α_{n} (\frac{t_{0}}{2∥t_{0}∥} + u))

∈ F′(0) (α_{n} (\frac{t_{0}}{2∥t_{0}∥} + u)) − α_{n} ∥\frac{t_{0}}{2∥t_{0}∥} + u∥ F′(t_{0})[U_{n}] − K
= \frac{α_{n}}{2∥t_{0}∥}F′(0)(t_{0}) + α_{n}F′(0)(u) − α_{n}F′(t_{0}) [∥\frac{t_{0}}{2∥t_{0}∥} + u∥ U_{n}] − K
∀u ∈ U_{n} ∀n.

By (ii), we have

\frac{α_{n}}{2∥t_{0}∥}F′(0)(t_{0}) ∈ −K ∀n,

and by (8)

∥\frac{t_{0}}{2∥t_{0}∥} + u∥ U_{n} ⊆ U_{n} ∀u ∈ U_{n} ∀n.

Hence, it holds

F (α_{n} (\frac{t_{0}}{2∥t_{0}∥} + u)) ∈ α_{n}F′(0)(u)−α_{n}F′(t_{0})[U_{n}]−K ∀u ∈ U_{n} ∀n. (9)

For every natural number n let Γ_{n} : U_{n} → 2^{U_{n}} be the set–valued mapping defined by

Γ_{n}(u) := \{ũ ∈ U_{n}; F (α_{n} (\frac{t_{0}}{2∥t_{0}∥} + u)) ∈ α_{n}F′(0)(u − ũ) − K\} .

Due to (9), for every n and each u ∈ U_{n}, the set Γ_{n}(u) is nonempty. Furthermore, the mapping

F (α_{n} (\frac{t_{0}}{2∥t_{0}∥} + .)) − α_{n}F′(0)(.)

is continuous, and the mapping

−α_{n}F′(0)(.)

is linear. Applying Lemma 1, for every n the mapping Γ_{n} has a fixed point u_{n} ∈ U_{n} fulfilling u_{n} ∈ Γ_{n}(u_{n}), what means

F (α_{n} (\frac{t_{0}}{2∥t_{0}∥} + u_{n})) ∈ −K  ∀n.  (10)

So, the sequences {a_{n}} and {t_{n}} defined by

a_{n} := \frac{α_{n}}{2∥t_{0}∥}  ∀n
t_{n} := t_{0} + 2∥t_{0}∥u_{n}  ∀n

have the properties claimed in the proposition.

2.2 A direct approach by using a separation theorem

In this section we will show that derived cones constructed at an optimal point never can contain a vector belonging to the interior of the ordering cone. From that property, Breckner’s multiplier rule can be deduced using a simple separation theorem. Also in the original proof, there is performed a separation of two sets. But these sets are constructed rather artificially. So, our method of proof seems to be more evident.

For simplicity of the proof, we assume K_{3} = {0^{m_{3}}}. As we will see in section 3, any problem that meets the requirements initially made can be reformulated equivalently fulfilling this assumption. By this, in the proof a result like proposition 1 can be replaced by a classical implicit function theorem.

All we have to do is to show the following proposition being true.

Proposition 2. Let x_{0} ∈ X be a local weakly K_{1}-mimimal point for the function f_{1} over S and let D ∈ R^{m} be an K-derived convex cone for f at x_{0}. Then there exists a sequence {b_{k}} ⊂ R^{m} (k = 1, 2, …) converging to zero, such that

D ∩ (−b_{k} − (K_{1} × L^{∗} × {0^{m_{3}}})) = ∅  ∀k.  (11)

Remark 2. Property (11) implies the origin of R^{m} being an extremal point of the system {D, (−K_{1}) × (−L^{∗}) × {0^{m_{3}}}} in the sense of Kruger and Mordukhovich^{1} [7].

By (11), we can separate^{2} the convex sets D and −b_{k} + (−K_{1}) × (−L^{∗}) × {0^{m_{3}}}. Hence, there exists for each k ∈ {1, 2, …} a multiplier vector λ_{k} =

1 A point x_{0} is called to be an extremal point of the system {C_{1}, …, C_{n}}, if x_{0} ∈ ⋂_{i=1}^{n} C_{i} and there are sequences {a_{ik}} (k = 1, 2, …) converging to zero such that

⋂_{i=1}^{n}(C_{i} − a_{ik}) = ∅ (k = 1, 2, …).

2 Relation (11) was received searching for fundamental properties of K-derived sets at optimal points. The autor wishes to express his thanks to Prof. W. W. Breckner for the idea of applying a separation theorem on this in order to prove Theorem 1.

(λ_{k1}, λ_{k2}, λ_{k3}) ∈ R^{m_{1}} × R^{m_{2}} × R^{m_{3}}, ∥λ_{k}∥ = 1, fulfilling

⟨λ_{k}, d⟩ ≥ 0  ∀d ∈ D,
⟨λ_{k1}, y⟩ ≥ ⟨λ_{k1}, b_{k1}⟩  ∀y ∈ K_{1},
⟨λ_{k2}, y⟩ ≥ ⟨λ_{k2}, b_{k2}⟩  ∀y ∈ L^{∗}.

Because of the compactness of the finite–dimensional unit ball, the sequence {λ_{k}} converges to a certain vector λ = (λ_{1}, λ_{2}, λ_{3}) ∈ R^{m_{1}} × R^{m_{2}} × R^{m_{3}}, λ ≠ 0, with

⟨λ, d⟩ ≥ 0  ∀d ∈ D,
⟨λ_{1}, y⟩ ≥ 0  ∀y ∈ K_{1},
⟨λ_{2}, y⟩ ≥ 0  ∀y ∈ L^{∗},

hence λ_{1} ∈ K_{1}^{∗}, λ_{2} ∈ L ⊆ K_{2}^{∗}, and

⟨λ_{2}, f_{2}(x_{0})⟩ = 0.

For to prove proposition 2, we need the following lemma.

Lemma 2. Let D ∈ R^{m} be an K-derived convex cone for a function f : X → R^{m} at x_{0} ∈ S. If there are some d_{1} ∈ −int K_{1}, and d_{2} ∈ −int L^{∗} with

(d_{1}, d_{2}, d_{3}) ∈ D ∀d_{3} ∈ R^{m_{3}},

so there exists a sequence {x_{n}} ∈ X (n = 1, 2, …) converging to x_{0} such that

f_{1}(x_{n}) − f_{1}(x_{0}) ∈ −int K_{1}  ∀n,  (12a)
f_{2}(x_{n}) ∈ −K_{2}  ∀n,  (12b)
f_{3}(x_{n}) = 0  ∀n.  (12c)

Proof. Let be

a_{i} := ( \begin{matrix}d_{1} \\ d_{2} \\ 0^{m_{3}} \end{matrix} ) + ( \begin{matrix}0^{m_{1}} \\ 0^{m_{2}} \\ e_{i} \end{matrix} ) (i = 1, … m_{3})

and

a_{0} := ( \begin{matrix}d_{1} \\ d_{2} \\ 0^{m_{3}} \end{matrix} ) − ∑_{i=1}^{m_{3}} ( \begin{matrix}0^{m_{1}} \\ 0^{m_{2}} \\ e_{i} \end{matrix} ) .

(Here, e_{i} denotes the i-th unit vector of the space R^{m_{3}}.) By assumptions, all a_{i} (i = 0, 1, …, m_{3}) belong in D. According to Definition 2, for the (m + 1)- tuple {a_{0}, a_{1}, …, a_{m_{3}}, 0^{m_{1}}, 0^{m_{2}}} we find some r, ω, ϱ with the properties (A), (B), (C1), (C2), (C3). For short, we set

ω̄(t) := ω(t, 0^{m_{1}}, 0^{m_{2}}) : B_{+}^{m_{3}+1}(r) → X,
ϱ̄(t) := ϱ(t, 0^{m_{1}}, 0^{m_{2}}) : B_{+}^{m_{3}+1}(r) → R^{m}.

Then, (A) implies especially for (t, 0^{m_{1}}, 0^{m_{2}}) with t ∈ B_{+}^{m_{3}+1}(r)

f_{1}(ω̄(t)) − f_{1}(x_{0}) − (∑_{i=0}^{m_{3}} t^{i}) d_{1} − ∥t∥ϱ̄_{1}(t) ∈ −K_{1} ∀t ∈ B_{+}^{m_{3}+1}(r),(13a)
f_{2}(ω̄(t)) − f_{2}(x_{0}) − (∑_{i=0}^{m_{3}} t^{i}) d_{2} − ∥t∥ϱ̄_{2}(t) ∈ −K_{2} ∀t ∈ B_{+}^{m_{3}+1}(r),(13b)
f_{3}(ω̄(t)) − ∑_{i=0}^{m_{3}} t^{i}a_{i3} − ∥t∥ϱ̄_{3}(t) = 0 ∀t ∈ B_{+}^{m_{3}+1}(r). (13c)

Now, we can prove the following three assertions. Assertion 1. There is a constant r_{1} ∈ (0, r], such that

f_{1}(ω̄(t)) − f_{1}(x_{0}) ∈ −int K_{1} ∀t ∈ B_{+}^{m_{3}+1}(r_{1}) \ {0}. (14)

By (C1), there exists a point y_{1}^{0} ∈ K_{1} so that ∀ε > 0 ∃r_{ε} ∈ (0, r] with

ϱ̄_{1}(t) ∈ εy_{1}^{0} − K_{1} ∀t ∈ B_{+}^{m_{3}+1}(r_{ε}).

Due to d_{1} ∈ −int K_{1}, one can find ε_{0} > 0 sufficiently small such that

\frac{∑_{i=0}^{m_{3}} t^{i}}{∥t∥} d_{1} + ε_{0}y_{1}^{0} ∈ −int K_{1} ∀t = (t^{0}, t^{1}, …, t^{m_{3}}) ∈ R_{+}^{m_{3}+1} \ \{0\}.

With r_{1} := r_{ε_{0}} it follows from (13a)

f_{1}(ω̄(t)) − f_{1}(x_{0}) ∈ (∑_{i=0}^{m_{3}} t^{i}) d_{1} + ∥t∥ϱ̄_{1}(t) − K_{1}
⊆ (∑_{i=0}^{m_{3}} t^{i}) d_{1} + ε_{0}∥t∥y_{1}^{0} − K_{1}
⊆ −int K_{1}  ∀t ∈ B_{+}^{m_{3}+1}(r_{1}) \ {0}.

Assertion 2. There is a constant r_{2} ∈ (0, r], such that

f_{2}(ω̄(t)) ∈ −K_{2} ∀t ∈ B_{+}^{m_{3}+1}(r_{2}). (15)

Regarding (C2) and d_{2} ∈ −int L^{∗}, analogously to the proof of Assertion 1 one can find a constant r′ ∈ (0, r] such that

(∑_{i=0}^{m_{3}} t^{i}) d_{2} + ∥t∥ϱ̄_{2}(t) ∈ −int L^{∗} ∀t ∈ B_{+}^{m_{3}+1}(r′) \ {0}.

Given a multiplier μ ∈ L, it follows

⟨μ, f_{2}(x_{0}) + (∑_{i=0}^{m_{3}} t^{i}) d_{2} + ∥t∥ϱ̄_{2}(t)⟩ ≤ 0 ∀t ∈ B_{+}^{m_{3}+1}(r′).

For every multiplier μ ∈ K_{2}^{∗} \ L, we also find because of ⟨μ, f_{2}(x_{0})⟩ < 0 a sufficient small constant r_{μ} > 0 such that

⟨μ, f_{2}(x_{0}) + (∑_{i=0}^{m_{3}} t^{i}) d_{2} + ∥t∥ϱ̄_{2}(t)⟩ ≤ 0 ∀t ∈ B_{+}^{m_{3}+1}(r_{μ}).

Thus, there exists to every μ ∈ K_{2}^{∗} a r_{μ} ∈ (0, r], such that the above inequality holds. Since the cone K_{2}^{∗} is generated by a compact base, we can fix a r_{2} ∈ (0, r] independent from μ such that

⟨μ, f_{2}(x_{0}) + (∑_{i=0}^{m_{3}} t^{i}) d_{2} + ∥t∥ϱ̄_{2}(t)⟩ ≤ 0 ∀t ∈ B_{+}^{m_{3}+1}(r_{2}) ∀μ ∈ K_{2}^{∗}.

It follows

f_{2}(x_{0}) + (∑_{i=0}^{m_{3}} t^{i}) d_{2} + ∥t∥ϱ̄_{2}(t) ∈ −K_{2} ∀t ∈ B_{+}^{m_{3}+1}(r_{2}),

and by (13b)

f_{2}(ω̄(t)) ∈ −K_{2} ∀t ∈ B_{+}^{m_{3}+1}(r_{2}).

Assertion 3. There is a sequence {t_{n}} ⊂ B_{+}^{m_{3}+1}(r) \ {0} convering to zero, such that

f_{3}(ω̄(t_{n})) = 0  ∀n.  (16)

This step requires an implicit function theorem. We will apply Theorem 8.2. in [6]. Set h = (1, …, 1) ∈ R^{m_{3}+1}. Choose a δ > 0, such that

∥τ(h + σ)∥ ≤ r ∀τ ∈ [0, δ] ∀σ ∈ B^{m_{3}+1}(1).

Because of h + σ ∈ R_{+}^{m_{3}+1} for all σ ∈ B^{m_{3}+1}(1), we also have

τ(h + σ) ∈ B_{+}^{m_{3}+1}(r) ∀τ ∈ [0, δ] ∀σ ∈ B^{m_{3}+1}(1).

Consider the vector–valued function Φ : B^{m_{3}+1}(1) × [0, δ] → R^{m_{3}}, defined componentwise by

Φ^{k}(σ, τ) := \{ \begin{matrix}\frac{1}{τ} f_{3}^{k}(ω̄(τ(h + σ))), & if τ > 0 \\ ∑_{i=0}^{m_{3}} a_{i3}^{k}σ^{i}, & if τ = 0 \end{matrix} (k = 1, …, m_{3}).

Obviously Φ is continuous everywhere, even in τ = 0 cause it is regarding (13c)

lim_{τ→+0} Φ^{k}(σ, τ) = lim_{τ→+0} \frac{f_{3}^{k}(ω̄(τ(h + σ)))}{τ}
= lim_{τ→+0} (\frac{∑_{i=0}^{m_{3}} τ(h^{i} + σ^{i})a_{i3}^{k}}{τ} + \frac{∥τ(h + σ)∥}{τ}ϱ̄_{3}^{k}(τ(h + σ)))

= ∑_{i=0}^{m_{3}}(h^{i} + σ^{i})a_{i3}^{k} + ∥(h + σ)∥ lim_{τ→+0} ϱ̄_{3}^{k}(τ(h + σ))

= ∑_{i=0}^{m_{3}} σ^{i}a_{i3}^{k}  (k = 1, …, m_{3})

uniformly for all σ ∈ B^{m_{3}+1}(1). Moreover it holds

Φ(σ, 0) = Aσ

with

A = ( \begin{matrix}−1 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ −1 & 0 & ⋯ & 1 \end{matrix} ) ∈ R^{m_{3}×(m_{3}+1)},

where the matrix A has rank m_{3}. Applying the implicit function theorem mentioned above on Φ, there exist a constant δ′ ∈ (0, δ], and a function σ : [0, δ′] → B^{m_{3}+1}(1) with

Φ(σ(τ), τ) = 0  ∀τ ∈ [0, δ′]  (17)

and

lim_{τ→+0} σ(τ) = σ(0) = 0.  (18)

Let {τ_{n}} ⊂ (0, δ′] (n = 1, 2, …) be a sequence of positive numbers converging to zero, and let {t_{n}} ⊂ R^{m_{3}+1} be the sequence defined by

t_{n} = τ_{n}(h + σ(τ_{n})) (n = 1, 2, …).

This sequence fulfills {t_{n}} ⊂ B_{+}^{m_{3}+1}(r), and due to τ_{n} > 0 ∀n and (18) moreover

t_{n} ∈ B_{+}^{m_{3}+1}(r) \ {0} ∀n.

Furthermore we have lim_{n→∞} t_{n} = 0, and by (17) finally

f_{3}(ω̄(t_{n})) = f_{3}(ω̄(τ_{n}(h + σ(τ_{n}))))
= τ_{n}Φ(σ(τ_{n}), τ_{n})
= 0  ∀n.

Since {t_{n}} converges to zero, there is a number n_{0} such that t_{n} ∈ B_{+}^{m_{3}+1}(r_{1}) and {t_{n}} ⊂ B_{+}^{m_{3}+1}(r_{2}) for n > n_{0}. So, the seqence {x} ⊂ X

x_{n} := ω̄(t_{n+n_{0}}) (n = 1, 2, …).

converges by (B) to x_{0} and fulfills by (14), (15), and (16) the relations stated in the lemma.

Proof. (of Proposition 2) Take a vector b_{1} ∈ int K_{1}, and a vector b_{2} ∈ int L^{∗}. To b_{1} and b_{2}, always one can find a vector b_{3} ∈ R^{m_{3}} such that

− ( \begin{matrix}b_{1} + K_{1} \\ b_{2} + L^{∗} \\ b_{3} \end{matrix} ) ∩ D = ∅.  (19)

Else, we would have

− ( \begin{matrix}b_{1} + K_{1} \\ b_{2} + L^{∗} \\ b_{3} \end{matrix} ) ∩ D ≠ ∅ ∀b_{3} ∈ R^{m_{3}}.

Thus, there would be d_{1} ∈ −b_{1} −K_{1} ⊆ −intK_{1}, and d_{2} ∈ −b_{2} −L^{∗} ⊆ −intL^{∗} with

( \begin{matrix}d_{1} \\ d_{2} \\ −b_{3} \end{matrix} ) ∈ D ∀b_{3} ∈ R^{m_{3}}.

But by Lemma 2, then there must exist a sequence {x_{n}} ∈ X converging to x_{0} such that

f_{1}(x_{n}) − f_{1}(x_{0}) ∈ −int K_{1}  ∀n,
f_{2}(x_{n}) ∈ −K_{2}  ∀n,
f_{3}(x_{n}) = 0  ∀n.

This contradicts the local K_{1}-minimality of x_{0}. Hence (19) must be true. The sequence {b_{k}} ⊂ R^{m} defined by

b_{k} := \frac{1}{k} ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} ) (k = 1, 2, …)

converges to zero and fulfills by (19) property (11).

3 An additional complementarity condition

In Breckner’s Multiplier rule, to the constraint f_{2}(x) ∈ −K_{2}, there corresponds a complementary slackness condition ⟨λ_{2}, f_{2}(x_{0})⟩ = 0. We asked if there is also such a property (6) valid for f_{3}(x) ∈ −K_{3}.

The only difference between the two constraints is the demand on K_{2} to have a nonempty interior. If the cone K_{3} has a nonempty interior, too, equation (6) must hold by reasons of analogy. If, on the other hand, we have K_{3} = {0}, equation (6) holds trivially. So, the problem is to show the desired complementarity condition for cones K_{3} with int K_{3} = ∅, but K_{3} ≠ {0}. We show how that case can be reduced on the two easy cases.

Let M := span(K_{3}) be the subspace of R^{m_{3}} spanned up by the elements of K_{3}. Set k := dim(M). Obviously 0 ≤ k ≤ m_{3}. (Here, if int K_{3} ≠ ∅, it is k = m_{3}, whereas if K_{3} = {0}, it is m_{3} = 0.) Let N be the orthogonal complement of M with respect to R^{m_{3}}. Choose an orthonormal basis {η_{1}, …, η_{k}} of M as well as orthonormal basis {η_{k+1}, …, η_{m_{3}}} of N. Then {η_{1}, …, η_{m_{3}}} is an orthonormal basis of R^{m_{3}}.

Consider now the orthonormal transformation^{3} A : R^{m_{3}} → R^{m_{3}} defined by

A(η_{i}) = e_{i} (i = 1, …, m_{3}),

where e_{i} is the i-th unit vector of the space R^{m_{3}}. Let be K̃_{3} ∈ R^{k} the set generated by the first k elements of the image of K_{3} transformed by A;

K̃_{3} := {( A^{1}(y) ; ⋮ ; A^{k}(y) ); y ∈ K_{3}} .

Of course, K̃_{3} is a closed convex cone, too. By construction, it is span(K̃_{3}) = R^{k}, hence int K̃_{3} ≠ ∅ relatively to the space R^{k}. Since K_{3} ⊆ M ⊥ N, we have A^{i}(y) = 0 (i = k + 1, …, m_{3}) for every y ∈ K_{3}. That means

A[K_{3}] = K̃_{3} × {0^{m_{3}−k}}.  (20)

We define a function f̃_{2} : X → R^{m_{2}+k} by

f̃_{2}(x) := ( f_{2}(x) ; A^{1}(f_{3}(x)) ; ⋮ ; A^{k}(f_{3}(x)) ) ∀x ∈ X,

as well as a function f̃_{3} : X → R^{m_{3}−k} by

f̃_{3}(x) := ( A^{k+1}(f_{3}(x)) ; ⋮ ; A^{m_{3}}(f_{3}(x)) ) ∀x ∈ X,

3 The author is indebted to an anonymous referee for a hint on formulating the transformation mapping in such a compact way.

and a cone K̃_{2} ⊂ R^{m_{2}+k} with int K̃_{2} ≠ ∅ by

K̃_{2} := K_{2} × K̃_{3}.

Thus, the set

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

can be described equivalently by

S = {x ∈ X; f̃_{2}(x) ∈ −K̃_{2}, f̃_{3}(x) = 0^{m_{3}−k}},  (22)

where the cone K̃_{2} has a nonempty interior relatively to R^{m_{2}+k}.

As shown above, every problem fulfilling the requirements initially made can be transformed into a problem with the feasible set in form (22). So, the property K_{3} = {0} can be assumed for each such problem without loss of generality. Then the question about a relation like (6) becomes uninterestingly. But, from an other point of view, we can construct by this transformation also such an additional complementarity relation for problems with a cone K_{3} of general nature.

Given a problem with a feasible set in form (21), let x_{0} ∈ X be a local weakly K_{1}-mimimal point for the function f_{1} over S, and let D ∈ R^{m} be an K-derived convex cone for f at x_{0}. It is easily seen, that

D̃ := D_{1} × ( D_{2} ; A^{1}[D_{3}] ; ⋮ ; A^{k}[D_{3}] ) × ( A^{k+1}[D_{3}] ; ⋮ ; A^{m_{3}}[D_{3}] )

is a (K_{1} × K̃_{2} × {0^{m_{3}−k}})-derived cone for the function (f_{1}, f̃_{2}, f̃_{3}) at x_{0}.

Applying Theorem 1 on the transformed problem, there exists a multiplier vector λ̃ = (λ̃_{1}, λ̃_{2}, λ̃_{3}) ∈ K_{1}^{∗} × K̃_{2}^{∗} × R^{m_{3}−k}, λ̃ ≠ 0, such that

⟨λ̃, d⟩ ≥ 0  ∀d ∈ D̃,
⟨λ̃_{2}, f̃_{2}(x_{0})⟩ = 0.

Setting

λ_{1} := λ̃_{1},

λ_{2} := ( λ̃_{2}^{1} ; ⋮ ; λ̃_{2}^{m_{2}} ) ,

λ_{3} := A^{⊤} ( λ̃_{2}^{m_{2}+1} ; ⋮ ; λ̃_{2}^{m_{2}+k} ; λ̃_{3} ) ,

we get λ_{1} ∈ K_{1}^{∗}, λ_{2} ∈ K_{2}^{∗}, λ = (λ_{1}, λ_{2}, λ_{3}) ≠ 0, and

⟨λ, d⟩ ≥ 0  ∀d ∈ D,
⟨λ_{2}, f_{2}(x_{0})⟩ = 0.

But furthermore, from (20) it follows

λ_{3} ∈ A^{⊤}[K̃_{3}^{∗} × R^{m_{3}−k}] ⊆ K_{3}^{∗},

and finally

⟨λ_{3}, f_{3}(x_{0})⟩ = ⟨A(λ_{3}), A(f_{3}(x_{0}))⟩

= ⟨( λ̃_{2}^{m_{2}+1} ; ⋮ ; λ̃_{2}^{m_{2}+k} ) , ( f̃_{2}^{m_{2}+1} ; ⋮ ; f̃_{2}^{m_{2}+k} )⟩ + ⟨λ̃_{3}, f̃_{3}(x_{0})⟩

= 0.

By this deduction we are able to propose:

Theorem 2. Let x_{0} ∈ X be a local weakly K_{1}-minimal point for the function f_{1} over S 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,
⟨λ_{3}, f_{3}(x_{0})⟩ = 0.

4 Regularity conditions

Usually a multiplier rule is equipped with a so–called regularity condition. A regularity condition ensures that the multiplier corresponding with the objective function does not vanish. For Theorem 1 we were missing such a condition. The idea for the following result was taken from a regularity condition by Hestenes [6] (Corollary on page 377).

Theorem 3. Let the assumptions of Theorem 1 be fulfilled.

(a) If there is a vector e ∈ int K_{1} with

(−e, 0, 0) ∈ D + K_{1} × L^{∗} × K_{3},

so for the multiplier λ in Theorem 1 it holds λ_{1} = 0.

(b) If there is an arbitrary vector e ∈ R^{m_{1}} with

(−e, 0, 0) ∉ D + K_{1} × L^{∗} × K_{3},

so in Theorem 1 a multiplier λ can be chosen with λ_{1} ≠ 0.

Proof. (a) Since (−e, 0, 0) ∈ D+K_{1} ×L^{∗} ×K_{3}, there is a vector (x_{1}, x_{2}, x_{3}) ∈ K_{1} × L^{∗} × K_{3}, such that

(−e, 0, 0) − (x_{1}, x_{2}, x_{3}) ∈ D.

Let be λ the multiplier existing along Theorem 1. Then it is

⟨λ, (−e, 0, 0) − (x_{1}, x_{2}, x_{3})⟩ ≥ 0.

Because of λ_{1} ∈ K_{1}^{∗}, λ_{2} ∈ K_{2}^{∗}, and λ_{3} ∈ K_{3}^{∗}, it follows

⟨λ_{1}, e⟩ = −⟨λ, (−e, 0, 0)⟩
≤ −⟨λ, (x_{1}, x_{2}, x_{3})⟩
= −⟨λ_{1}, x_{1}⟩ − ⟨λ_{2}, x_{2}⟩ − ⟨λ_{3}, x_{3}⟩
≤ 0.

But we have ⟨λ_{1}, x⟩ ≥ 0 ∀x ∈ K_{1}, hence ⟨λ_{1}, e⟩ = 0. By e ∈ int K_{1} it follows λ_{1} = 0.

(b) Every such vector can be written as

(−e, 0, 0) = x − λ

with

x ∈ D + K_{1} × L^{∗} × K_{3},
−λ ∈ −[D + K_{1} × L^{∗} × K_{3}]^{∗},

and ⟨λ, x⟩ = 0. It follows λ ≠ 0, else (−e, 0, 0) = x ∈ D + K_{1} × L^{∗} × K_{3}. Due to D ⊆ D + K_{1} × L^{∗} × K_{3} or [D + K_{1} × L^{∗} × K_{3}]^{∗} ⊆ D^{∗}, it follows λ ∈ D^{∗}, hence

⟨λ, d⟩ ≥ 0 ∀d ∈ D.

Due to K_{1}×L^{∗}×K_{3} ⊆ D+K_{1}×L^{∗}×K_{3} or [D+K_{1}×L^{∗}×K_{3}]^{∗} ⊆ K_{1}^{∗}×L×K_{3}^{∗}, we have

λ ∈ K_{1}^{∗} × L × K_{3}^{∗}.

Moreover it is

⟨λ_{1}, e⟩ = −⟨λ, (−e, 0, 0)⟩ = −⟨λ, x⟩ + ⟨λ, λ⟩ = ∥λ∥^{2} > 0.

Assuming λ_{1} = 0, we would get a contradiction.

Remark 3. Indeed, the conditions in (a) und (b) are contradictory. If there is a vector e′ ∈ intK_{1} with (−e′, 0, 0) ∈ D + K_{1} × L^{∗} × K_{3}, so there cannot be a vector e′′ ∈ R^{m_{1}} with (−e′′, 0, 0) ∉ D + K_{1} × L^{∗} × K_{3}, and vice versa.

Proof. Let be given e′ ∈ intK_{1} with (−e′, 0, 0) ∈ D + K_{1} × L^{∗} × K_{3}. That means −e′ ∈ D_{1} +K_{1}. Additionally we have e′ ∈ D_{1} +intK_{1} ⊆ int(D_{1} +K_{1}). So, it is

0 = e′ − e′ ∈ int(D_{1} + K_{1}) + (D_{1} + K_{1}) ⊆ int(D_{1} + K_{1}),

hence D_{1} + K_{1} = R^{m_{1}}. Let us assume there would be e′′ ∈ R^{m_{1}} with (−e′′, 0, 0) ∉ D + K_{1} × L^{∗} × K_{3}. That would mean −e′′ ∉ D_{1} + K_{1}, contradicting to D_{1} + K_{1} = R^{m_{1}}. So, it is shown

∃e′ ∈ int K_{1} : (−e′, 0, 0) ∈ D + K_{1} × L^{∗} × K_{3}
⟹ ∄e′′ ∈ R^{m_{1}} : (−e′′, 0, 0) ∉ D + K_{1} × L^{∗} × K_{3},

and by negation

∃e′′ ∈ R^{m_{1}} : (−e′′, 0, 0) ∉ D + K_{1} × L^{∗} × K_{3}
⟹ ∄e′ ∈ int K_{1} : (−e′, 0, 0) ∈ D + K_{1} × L^{∗} × K_{3}.

References

1. Breckner, W. W. (1994) Derived sets in multiobjective optimization. Z. Anal. Anw. 13, 725–738

2. Breckner, W. W., Göpfert, A. (1996) Multiplier rules for weak pareto optimization problems. Optimization 38 No. 1, 23–37

3. Gittleman, W. (1971) A general multiplier rule. JOTA 7, 29–38

4. Hestenes, M. R. (1965) On variational theory and optimal control theory. SIAM J. Control 3, 23–48

5. Hestenes, M. R. (1966) Calculus of variations and optimal control theory. John Wiley & Sons, New York London Sydney Toronto

6. Hestenes, M. R. (1975) Optimization theory: The finite dimensional case. John Wiley & Sons, New York London Sydney Toronto

7. Kruger, A. Ya., Mordukhovich, B. Sh. (1978) Minimization of nonsmooth functionals in optimal control problems. Engineerg. Cybern. 16, 126–133

8. Nieuwenhuis, J. W. (1980) A general multiplier rule. JOTA 31, 167–176

9. Tuy, H. (1974) On the convex approximation of nonlinear inequalities. Math. Operationsforsch. Statist. 5, Heft 6, 451–466