A Proximal Point Algorithm for Control

Approximation Problems

Part I: Theoretical Background

H.Benker  A.Hamel  Chr.Tammer

Abstract

We consider the optimization problem

f(x) := (c, x) + ∑_{i=1}^{n} α_{i} ∥A^{i}x − a^{i}∥^{β_{i}} → min_{x∈D},

which is an extension of a problem studied by Idrissi, Lefebvre and Michelot [7]. This class of problems contains many practically important special cases so as approximation, location and optimal control problems, perturbed linear programming problems and surrogate problems for linear programming. Necessary and sufficient optimality conditions are derived using the subdifferential calculus. A proximal point algorithm is modified by the method of partial inverse [13] in order to solve the optimality conditions.

1 Introduction

Many authors have studied generalizations of the well known Fermat-Weber problem from the theoretical and computational point of view (see [2], [3], [4], [5], [7], [8], [9], [10], [11], [17], [18], [19]). The aim of this paper is to extend the results of Michelot and Lefebvre [11] and Idrissi, Lefebvre and Michelot [7] to the following general approximation problem

f(x) = (c, x) + ∑_{i=1}^{n} α_{i} ∥A^{i}x − a^{i}∥^{β_{i}} → min_{x∈D},  (1)

where c ∈ H , a^{i} and x ∈ H , α_{i} ≥ 0 , β_{i} ≥ 1, A^{i} ∈ L (H → H), (i = 1, ..., n), (L(H → H) denotes the space of linear continuous operators from H to H), H is a Hilbert space , D_{j} ⊂ H ( j = 1, ..., m) are closed and convex sets, D_{0} ⊆ H is a linear subspace and D = ⋂_{j=0}^{m} D_{j}.

N_{D_{j}}(x^{0}) denotes the normal cone to D_{j} at x^{0} ∈ H defined by

N_{D_{j}} = \{ \begin{matrix}\{x ∈ H : (x, x′ − x^{0}) ≤ 0 ∀x′ ∈ D_{j}\} : & x^{0} ∈ D_{j} \\ ∅ : & otherwise. \end{matrix}

In the following we assume that any one of constraint qualifications (generalized Slater condition or stability, see Göpfert [6]) is fulfilled. Furthermore, B^{0} denotes the unit sphere associated with the dual norm of the norm || . ||. P_{D}(e) denotes the projection of e onto a set D. We assume that the inverse operator (A^{iT})^{−1} of the adjoint operator A^{iT} to A^{i} exists for all i=1,...,n .

Remark 1:

1) If a set D_{j} is bounded (j = 1, ..., m), then the existence of a solution of the problem (1) is assured.

2) The problem (1) contains the following practically important special cases:

• linear programming if α_{i} = 0 ∀i,

• surrogate problems for linear programming problems

f(x) := (c, x) ⟶ minimum

subject to

x ∈ D and A^{i}x = a^{i} (i = 1, ..., n),

for which the feasible set is empty but D is nonempty,

• perturbed linear programming problems,

• approximation and location problems if c = 0, • optimal control problems (optimal regulator problems) of the form

(c = 0, n = 2, β_{i} = p)

∥Au − r∥^{p} + α ∥u∥^{p} → min_{u∈U⊂H} .

The paper is organized as follows: In chapter 2 we apply duality assertions in order to obtain lower bounds for the approximation problem (1). Furthermore, in chapter 3 we derive optimality conditions for problem (1) using the subdifferential calculus. These optimality conditions are useful for an application of Spingarn’s proximal point algorithm (see [7], [11] and [13]) for solving problem (1) in chapter 4. In chapter 4.1 we present a first proximal point algorithm and in chapter 4.2 another one for different subspaces in the formulation of the algorithm. Moreover, we study in chapter 4.1 two special cases of (1).

2 Lower Bounds

Duality theorems can be used in order to obtain lower bounds for the problem (1). For the special case

f(x) = ∑_{i=1}^{n} ∥A^{i}x − a^{i}∥^{p} + α ∥x∥^{p} → min_{x∈H},  (2)

where α > 0 and p = 1 or 2,

we can apply a duality theorem of approximation theory such that we obtain the following lower bounds for the problem (2) (see [1]).

Lemma 1 For p=1 we have the estimation

minimum_{x∈H} (∑_{i=1}^{n} ∥A^{i}x − a^{i}∥ + α ∥x∥) ≥ \frac{∑_{i=1}^{n} ∥a^{i}∥}{maximum \{1, \frac{1}{α} ∑_{i=1}^{n} ∥A^{i}∥\}} (3)

and for p=2

minimum_{x∈H}  (∑_{i=1}^{n} ∥A^{i}x − a^{i}∥^{2} + α ∥x∥^{2})  ≥  \frac{α ( ∑_{i=1}^{n} ∥a^{i}∥^{2})}{α + ∑_{i=1}^{n} ∥A^{i}∥^{2}}. (4)

Proof: With Ax := (A^{1}x, ..., A^{n}x) we define a linear continuous operator A ∈ L(H → H^{n}). Now, we can write the problem (2) in the form

∥Ax − a∥_{H^{n}}^{p} + α ∥x∥_{H}^{p} → min_{x∈H},

where

a := (a^{1}, ..., a^{n})

and

∥a∥_{H^{n}}^{2} = (a, a)_{H^{n}} := ∑_{i=1}^{n} (a^{i}, a^{i})_{H} = ∑_{i=1}^{n} ∥a^{i}∥_{H}^{2} for p=2

and

∥a∥_{H^{n}} := ∑_{i=1}^{n} ∥a^{i}∥_{H} for p=1.

For p = 2 we obtain

∥A∥^{2} ≤ ∑_{i=1}^{n} ∥A^{i}∥^{2}

and for p = 1

|| A ||≤ ∑_{i=1}^{n} || A^{i} || .

Finally, lemma 1 from [1] yields the lower bounds (3) and (4). q.e.d.

Applying a general duality theorem we can also calculate lower bounds for another special case of problem (1). Let us consider the problem

(P) :  f(x) = (c, x) + ∑_{i=1}^{n} α_{i} || A^{i}x − a^{i} ||⟶ min_{x∈K_{H},Bx−b∈K_{V}} ,

where additionally to the assumptions given above V is a reflexive Banach space, B ∈ L(H ⟶ V), b ∈ V, K_{H} ⊂ H and K_{V} ⊂ V are closed convex cones and K_{H}^{∗} and K_{V}^{∗} the corresponding dual cones. We have shown in [15] that the following problem (D) can be considered as the dual problem to (P):

(D) : g(y, z) = ∑_{i=1}^{n} α_{i}y_{i}a^{i} + zb ⟶ max_{(y,z)∈D},

where

D = {(y, z) | y = (y_{1}, ..., y_{n}), y_{i} ∈ H, α_{i} || y_{i} ||_{∗}≤ α_{i} (i = 1, ..., n), z ∈ K_{V}^{∗} ,

c − ∑_{i=1}^{n} α_{i}A^{iT} y_{i} − B^{T} z ∈ K_{H}^{∗}}.

Here || . ||_{∗} denotes the dual norm to || . || .

Lemma 2 Consider the problems (P) and (D).

1. For any (y, z) ∈ D we have

inf_{x∈K_{H},Bx−b∈K_{V}} ((c, x) + ∑_{i=1}^{n} α_{i} || A^{i}x − a^{i} ||) ≥ ∑_{i=1}^{n} α_{i}y_{i}a^{i} + zb.

2. Assume that there exist an element x̄ ∈ K_{H} with Bx̄ − b ∈ int K_{V} and an element (ȳ, z̄) ∈ D with c − ∑_{i=1}^{n} α_{i}A^{iT} ȳ_{i} − B^{T} z̄ ∈ int K_{H}^{∗}. Then the problems (P) and (D) have optimal solutions x^{o} and (y^{o}, z^{o}) and it holds

(c, x^{o}) + ∑_{i=1}^{n} α_{i} || A^{i}x^{o} − a^{i} ||= ∑_{i=1}^{n} α_{i}y_{i}^{o}a^{i} + z^{o}b.

Proof: Analogous to the proof of duality assertions in [15] it is possible to derive the assertions from a general saddle point theorem (Theorem 47.1 in Zeidler [20]). q.e.d.

3 Optimality Conditions

The following approach is motivated by recent papers of Michelot and Lefebvre [11] and Idrissi, Lefebvre and Michelot [7]. Using the indicator functions χ_{D_{j}} of D_{j} defined by χ_{D_{j}}(x) = 0 if x ∈ D_{j} and χ_{D_{j}}(x) = +∞ otherwise the problem (1) is equivalent to the following unconstrained minimization problem

F (x) = (c, x) + ∑_{i=1}^{n} ∥A^{i}x − a^{i}∥^{β_{i}} + ∑_{j=0}^{m} χ_{D_{j}}(x) → min_{x∈H},  (5)

where we put α_{i} = 1(i = 1, ..., n) without loss of generality. The functional F (x) is convex under the given assumptions. Therefore, the subdifferential-condition

0 ∈ ∂F (x^{0})  (6)

is necessary and sufficient for the optimality of x^{0}. Applying the rule for sums of subdifferentials and the known formula for the subdifferential of a indicator function (∂χ_{D_{j}}(·) = N_{D_{j}}(·)) on the functional F in (5) we can write (6) equivalently in the form (7), (8), (9):

q_{i} ∈ ∂( ∥A^{i}x^{0} − a^{i}∥^{β_{i}}),  i = 1, 2, ..., n,  (7)

r_{j} ∈ N_{D_{j}}(x^{0}),  j = 1, 2, ..., m,  (8)

c + ∑_{i=1}^{n} q_{i} + ∑_{j=1}^{m} r_{j} ∈ D_{0}^{⊥}.  (9)

In order to reformulate the optimality conditions (7) - (9) in a more practical way we introduce a Hilbert space E, suitable subspaces A, B and an operator T. This will be done in different ways. For the first algorithm we will use the following notation:

We introduce the Hilbert space

E := (H)^{n+m+1}

with the inner product

(u, v) := ∑_{i=1}^{n+m+1}(u_{i}, v_{i})

for u = (u_{1}, ..., u_{n+m+1}) and v = (v_{1}, ..., v_{n+m+1}) ∈ E

and the subspaces

A := {y ∈ E | y = (y_{1}, ..., y_{n+m+1}) ; y_{j} = x , j = 1, ..., n + m + 1 ; x ∈ D_{0}} ,

B := {  p ∈ E  |  p = (p_{1}, ..., p_{n+m+1}) ,  ∑_{i=1}^{n+m+1} p_{i} ∈ D_{0}^{⊥}}

and the operator T defined on E by

T (y) := ∏_{i=1}^{n+m+1} T^{i}(x) = (T^{1}(x), ..., T^{n+m+1}(x)),  (10)

where

T^{i}(x) := ∂(∥A^{i}x − a^{i}∥^{β_{i}}), i = 1, ..., n,
T^{n+j}(x) := N_{D_{j}}(x), j = 1, ..., m,
T^{n+m+1}(x) := c.

With this notations the optimality conditions (7)-(9) can be rewritten as:

Find (y^{0}, p^{0}) ∈ A × B such that p^{0} ∈ T (y^{0}). (11)

Remark 2:

1) Obviously, A and B are closed linear subspaces of E with A⊥B. We prove additionally, that the subspaces A and B are complementary, i.e., E = A ⊕ B:

We define the operator

P_{A}(e) = \frac{1}{n + m + 1} (P_{D_{0}}( ∑_{i=1}^{n+m+1} e_{i}), ..., P_{D_{0}}( ∑_{i=1}^{n+m+1} e_{i})) ,

where e = (e_{1}, ..., e_{n+m+1}) ∈ E is arbitrary.

Trivially, we have B = Ker(P_{A}). Applying the necessary and sufficient condition

(e − P_{A}(e), a) = 0 ∀a ∈ A

for an operator P_{A} to be a projection onto A, we see that P_{A} is the projection of E onto A, i.e., R(P_{A}) = A .

2) It is well known that a set-valued function T is a monotone operator (compare [13]) if (x − x′, y − y′) ≥ 0 whenever y ∈ T (x) and y′ ∈ T (x′). If the graph of T is not properly contained in the graph of any other monotone operator, then T is maximal monoton. So it is easy to see that the operator T, defined in (10), realizes a maximal monotone multifunction since T is composed by subdifferentials. For a numerical solution we need the condition (11) in the form 0 ∈ T (y^{0}) − p^{0} but the new multifunction T̃(y, p) := T (y) − p is not maximal monotone. Therefore, we use in the following an idea of Spingarn [13].

Now, applying the results of Spingarn [13] the problem (11) is equivalent to:

Find (y^{0}, p^{0}) ∈ A × B such that

0 ∈ T_{A}(y^{0} + p^{0}),  (12)

where T_{A} is the partial inverse of T with respect to A. T_{A} is described by its graph in the following way

{(y_{A} + p_{B}, p_{A} + y_{B}) | p ∈ T (y), p = p_{A} + p_{B} , y = y_{A} + y_{B} } ,

where v_{A} and v_{B} are the projections of v onto A and B, respectively . T_{A} is maximal monotone iff T is maximal monoton. Setting

z = z_{A} + z_{B}

and

z_{A} = y z_{B} = p

then the problem (12) has the following form:

Find z^{0} ∈ E  such that 0 ∈ T_{A}(z^{0}).  (13)

4 Application of the Proximal Point Algorithm

4.1 Algorithm I

Now we can apply the proximal point algorithm f or solving (13) (compare Michelot/Lefebvre [11] and Idrissi/Lefebvre/Michelot [7]). This algorithm has the form

z^{k+1} = (I + c_{k}T_{A})^{−1}z^{k}  k = 1, 2, ...,  (14)

where the starting point z^{1} is arbitrary and c_{k} is a sequence of positive real numbers. If (c_{k}) is bounded away from zero (we set c_{k} = 1) then either (z^{k}) converges weakly to a zero of T_{A} or ∥z^{k}∥ → ∞ and T_{A} has no zeros (see [12]). The iteration (14) can be rewritten in the form

y^{k+1} + p^{k+1} = (I + T_{A})^{−1}(y^{k} + p^{k})

which is equivalent to

y^{k} − y^{k+1} + p^{k} − p^{k+1} ∈ T_{A}(y^{k+1} + p^{k+1}).  (15)

Now, we will realize this iteration in terms of the multifunction T instead of T_{A}. Setting

p̃^{k} = y^{k} − y^{k+1} + p^{k+1},
ỹ^{k} = p^{k} − p^{k+1} + y^{k+1}

which yields

ỹ^{k} + p̃^{k} = y^{k} + p^{k},  y^{k+1} = (ỹ^{k})_{A},  p^{k+1} = (p̃^{k})_{B}

and applying the definition of the partial inverse T_{A} , we obtain the iteration (15) as

p̃^{k} ∈ T (ỹ^{k}) or p̃^{k} ∈ T (y^{k} + p^{k} − p̃^{k}).  (16)

Further, considering the definition of the operator T , the iteration (16) is equivalent to:

p̃_{i}^{k} ∈ ∂(∥A^{i}(x^{k} + p_{i}^{k} − p̃_{i}^{k}) − a^{i}∥^{β_{i}})  i = 1, ..., n,  (17)
p̃_{n+j}^{k} ∈ N_{D_{j}}(x^{k} + p_{n+j}^{k} − p̃_{n+j}^{k}),  j = 1, ..., m,  (18)
p̃_{n+m+1}^{k} = c.  (19)

For an implementation of the iteration algorithm (17)-(19) it remains to calculate the subdifferential from (17) and the normal cone from (18). Setting

z_{i}^{k} := A^{i}(x^{k} + p_{i}^{k} − p̃_{i}^{k}) − a^{i}

we get for the subdifferential from (17)

∂(∥ z_{i}^{k}∥^{β_{i}}) = A^{iT} β_{i} ∥z_{i}^{k}∥^{ß_{i}−1} ∂(∥ z_{i}^{k}∥)

and the iteration condition (17) has now the following form

(A^{iT})^{−1}β_{i}^{−1}p̃_{i}^{k} ∈ ∥z_{i}^{k}∥^{ß_{i}−1} ∂(∥ z_{i}^{k}∥).  (20)

To apply this expression in practice, a computable form is needed. This is only possible for special cases.

4.1.1 Special case 1: Let be β_{i} = 1 for i = 1, ..., n. Then (20) has the form

(A^{iT} )^{−1} p̃_{i}^{k} ∈ ∂(∥ z_{i}^{k}∥) = {z_{i}^{∗} ∈ H | ∥ z_{i}^{∗}∥ = 1 , ( z_{i}^{∗}, z_{i}^{k}) = ∥ z_{i}^{k}∥} . Hence

∥(A^{iT} )^{−1} p̃_{i}^{k}∥ = 1

and

∥z_{i}^{k}∥ = ((A^{iT} )^{−1} p̃_{i}^{k}, z_{i}^{k}).

Using the inequality

∥z_{i}^{k}∥ ≥ ( z_{i}^{∗}, z_{i}^{k}) ∀ z_{i}^{∗} with ∥ z_{i}^{∗}∥ = 1 (⇔ z_{i}^{∗} ∈ B^{0}), we get

((A^{iT} )^{−1} p̃_{i}^{k}, z_{i}^{k}) ≥ ( z_{i}^{∗}, z_{i}^{k}).

It follows that

( z_{i}^{∗} − (A^{iT} )^{−1} p̃_{i}^{k}, z_{i}^{k}) ≤ 0 ∀z_{i}^{∗} ∈ B^{0} .

Substituting the definition for z_{i}^{k} into the last inequaltity we get

( z_{i}^{∗} − (A^{iT} )^{−1} p̃_{i}^{k}, A^{i}(x^{k} + p_{i}^{k} − p̃_{i}^{k}) − a^{i}) ≤ 0 ∀z_{i}^{∗} ∈ B^{0}  (21)

which is equivalent to

z_{i}^{k} = A^{i}(x^{k} + p_{i}^{k} − p̃_{i}^{k}) − a^{i} ∈ N_{B^{0}}((A^{iT} )^{−1} p̃_{i}^{k}).

Now we can transform the inequality (21) in the following form

(p̃_{i}^{k} − x^{k} − p_{i}^{k} + (A^{i})^{−1} a^{i}, A^{iT} z_{i}^{∗} − p̃_{i}^{k}) ≥ 0 ∀z_{i}^{∗} ∈ B^{0}  (22)

which is equivalent to

p̃_{i}^{k} ∈ P_{M}(x^{k} + p_{i}^{k} − (A^{i})^{−1} a^{i}),  (23)

where P_{M} is the projection operator onto the set

M = { A^{iT} z_{i}^{∗} | z_{i}^{∗} ∈ B^{0}} .

Therefore, we have to solve the minimization problem

∥v − Bu∥^{2} → min_{u∈B^{0}},

where

v := x^{k} + p_{i}^{k} − (A^{i})^{−1} a^{i} and B := A^{iT} .

We find the solution of this quadratic minimization problem as a solution of the operator equation

(B^{T} B + λI)u = B^{T} v,

where λ is to determine such that ∥u∥ = 1 . This operator equation follows from the Lagrange multiplier rule. This completes the calculation of the iteration (17). It remains to solve the iteration (18), which is equivalent to

y_{n+j}^{k} − y_{n+j}^{k+1} + p_{n+j}^{k+1} ∈ N_{D_{j}}(x^{k} + p_{n+j}^{k} − p̃_{n+j}^{k}),  (24)

where

y_{n+j}^{k} = x^{k} and y_{n+j}^{k+1} = x^{k+1}.

The last relation (24) can be transformed into the form

x^{k+1} + p_{n+j}^{k} − p_{n+j}^{k+1} = P_{D_{j}}(x^{k} + p_{n+j}^{k}).  (25)

The algorithm for the special case 1 thus takes the following final form:

Algorithm :

• Choose the starting points

x^{1} ∈ D_{0} and p^{1} ∈ E  with ∑_{i=1}^{n+m+1} p_{i}^{1} ∈ D_{0}^{⊥}.  (26)

• Compute x^{k+1} and p^{k+1} from

x^{k} − x^{k+1} + p_{i}^{k+1} = P_{M}(x^{k} + p_{i}^{k} − (A^{i})^{−1} a^{i}),  i = 1, ..., n,  (27)
x^{k+1} + p_{n+j}^{k} − p_{n+j}^{k+1} = P_{D_{j}}(x^{k} + p_{n+j}^{k}),  j = 1, ..., m,  (28)
x^{k} − x^{k+1} + p_{n+m+1}^{k+1} = c,  (29)

with

∑_{i=1}^{n+m+1} p_{i}^{k+1} ∈ D_{0}^{⊥}  and x^{k+1} ∈ D_{0}.  (30)

That means that we must first calculate the projections on M and D_{j} in the right hand side of the equations (27) and (28). Then we have to solve the linear equations (27)-(29) such that the relations (30) are satisfied. The solution of the linear equations (27)-(29) is very simple since we can eliminate the variables in the following way:

Setting

b_{i}^{k} = P_{M}(x^{k}+p_{1}^{k}−(A^{i})^{−1} a^{1})−P_{M}(x^{k}+p_{i+1}^{k}−(A^{i+1})^{−1} a^{i+1}), i = 1, ..., n−1,

b_{n+j−1}^{k} = P_{M}(x^{k}+p_{1}^{k}−(A^{i})^{−1} a^{1})+P_{D_{j}}(x^{k}+p_{n+j}^{k})−x^{k}+p_{n+j}^{k}, j = 1, ..., m,

b_{n+m}^{k} = P_{M}(x^{k} + p_{1}^{k} − (A^{i})^{−1} a^{1}) − c

we obtain immediately the solutions

p_{i}^{k+1} = p_{1}^{k+1} − b_{i−1}^{k},  i = 2, ..., n + m + 1,  (31)

where p_{1}^{k+1} is determined by the relations (30):

(n+m+1) p_{1}^{k+1}− ∑_{i=1}^{n+m} b_{i}^{k} ∈ D_{0}^{⊥} and (x^{k+1} =) x^{k} −c+p_{1}^{k+1}−b_{n+m}^{k} ∈ D_{0}.

(32)

Remark 3:

1) The determination of p_{1}^{k+1} from the relations (32) is only possible if the subspace D_{0} is concretely given, for example, if D_{0} = H then from (32) follows

p_{1}^{k+1} = \frac{1}{n + m + 1} ∑_{i=1}^{n+m} b_{i}^{k}  and x^{k+1} = x^{k} − c + p_{1}^{k+1} − b_{n+m}^{k}. (33)

2) Another possibility for the solution of the equations (27)-(29) is given in the following way: Using the definitions given above:

p̃^{k} = y^{k} − y^{k+1} + p^{k+1},
ỹ^{k} = p^{k} − p^{k+1} + y^{k+1}

which yields

ỹ^{k} + p̃^{k} = y^{k} + p^{k},  y^{k+1} = (ỹ^{k})_{A},  p^{k+1} = (p̃^{k})_{B},

we obtain

p̃_{1}^{k}, ..., p̃_{n}^{k}

from (27) ,

ỹ_{n+1}^{k} , ..., ỹ_{n+m+1}^{k}

from (28),(29) and the remaining components from

p̃_{n+j}^{k} = x^{k} + p_{n+j}^{k} − ỹ_{n+j}^{k} (j = 1, ..., m) and ỹ_{i}^{k} = x^{k} + p_{i}^{k} − p̃_{i}^{k} (i = 1, .., n).

Now, we obtain the solution vectors

p^{k+1} = ( p_{1}^{k+1} , ..., p_{n+m+1}^{k+1}) and y^{k+1} = ( x^{k+1} , ..., x^{k+1})

by calculating the projections (p̃^{k})_{B} and (ỹ^{k})_{A} from p̃^{k} and ỹ^{k} onto the subspaces B and A respectively.

4.1.2 Special case 2:

Let be β_{i} = β ≥ 1 and c = 0, i.e., we consider the problem

f(x) = ∑_{i=1}^{n} ∥A^{i}x − a^{i}∥^{β} → min_{x∈D= ⋂_{j=0}^{m} D_{j}} .  (34)

Defining an operator A ∈ L(H → H^{n}) by

Ax := (A^{1}x, A^{2}x, ..., A^{n}x)

and a norm on H^{n} = H × H × ... × H by

∥u∥_{H^{n}} := (∑_{i=1}^{n} ∥u^{i}∥^{β})^{1/β}, where u = (u^{1}, u^{2}, ..., u^{n}),

and using the indicator functions χ_{D_{j}} of D_{j} , the problem (34) is equivalent to the following unconstrained minimization problem

F (x) = ∥Ax − a∥_{H^{n}} + ∑_{j=0}^{n} χ_{D_{j}}(x) → min_{x∈H},  (35)

where a = (a^{1}, a^{2}, ..., a^{n}) . Now, using the optimality condition 0 ∈ ∂F (x^{0}) we obtain analogously to problem (1) the following necessary and sufficient conditions for the problem (35):

q ∈ ∂(∥Ax^{0} − a∥_{H^{n}}),  (36)
r_{j} ∈ N_{D_{j}}(x^{0}),  j = 1, ..., m,  (37)
q + ∑_{j=1}^{m} r_{j} ∈ D_{0}^{⊥}.  (38)

It remains to verify condition (36), since the other conditions (37) and (38) are the same as in (8) and (9). So we introduce the following subspaces:

A_{1} := {y ∈ E | y = (y_{1}, ..., y_{m+1}) ; y_{j} = x , j = 1, ..., m + 1 ; x ∈ D_{0}} , and

B_{1}  :=  { p ∈ E | p = (p_{1}, ..., p_{m+1})  ∑_{i=1}^{m+1} p_{i} ∈ D_{0}^{⊥} } ,

where E = H^{m+1}.

Using these subspaces A_{1} and B_{1} we can compute the subdifferential (36) in a similar manner as for the special case 1 and obtain

p̃_{1}^{k} = P_{M}(x^{k} + p_{1}^{k} − A^{−1}a),

where P_{M} is the projection operator onto the set

M = { A^{T} z^{∗} | z^{∗} ∈ B^{0}} ,

where

B^{0} = { z^{∗} ∈ H^{n} | ∥z^{∗}∥_{H^{n}} = 1}

and

A^{T} z^{∗} = (A^{1T} z_{1}^{∗} + ... + A^{nT} z_{n}^{∗}) ∈ H .

Now, the given algorithm for the special case 1 can be applied.

4.2 Algorithm II

If we define the subspaces A and B in a different way as in chapter 3 we get another specification of Spingarn’s algorithm again with the convergence assertions investigated by Spingarn [13]. Now, we introduce the following subspaces A_{2} and B_{2}:

A_{2} := {y ∈ E | y = (A^{1}x, ..., A^{n}x, y_{n+1}, ..., y_{n+m+1}); y_{n+j} = x;
j = 1, ..., n + m + 1 ; x ∈ D_{0}},
B_{2} := {p ∈ E | p = ((A^{1})^{−1T} p_{1}, ..., (A^{n})^{−1T} p_{n}, p_{n+1, ...,} p_{n+m+1}),

∑_{i=1}^{n+m+1} p_{i} ∈ D_{0}^{⊥}}.

Remark 4:

The subspaces A_{2} and B_{2} are obviously closed linear subspaces of E and A_{2}⊥B_{2}. We have only to prove that the subspaces A_{2} and B_{2} are complementary, i.e., H = A_{2} ⊕ B_{2} :

Using the operator P_{A_{2}} of the orthogonal projection onto the subspace A_{2} , we have A_{2} = R(P) .

Thus it remains to show that B_{2} = Ker(P) :

a) Let b ∈ B_{2} . We have (b − P_{A_{2}}(b) , a) = 0 , ∀a ∈ A_{2} . This yields

(P_{A_{2}}(b) , a) = (b , a) = 0 , ∀a ∈ A_{2} .

Now setting a = P_{A_{2}}(b) we obtain (P_{A_{2}}(b) , P_{A_{2}}(b)) = 0 and it follows P_{A_{2}}(b) = 0, which gives B_{2} ⊂ Ker(P) .

b) Let e ∈ Ker(P) .

We have P_{A_{2}}(b) = 0 and (e, a) = ∑_{i=1}^{n+m+1}(e_{i}, a_{i}) = 0 , ∀a ∈ A_{2} .

This yields with a = (A^{1}x , ..., A^{n}x, x, ..., x)

0 = ∑_{i=1}^{n+m+1}(e_{i}, a_{i}) = ∑_{i=1}^{n}(e_{i}, A^{i}x) + ∑_{j=n+1}^{n+m+1}(e_{j}, x)

= (∑_{i=1}^{n} A^{iT} e_{i} + ∑_{j=n+1}^{n+m+1} e_{j}, x) ∀x ∈ D_{0},

and thus we have e = ((A^{1T})^{−1}p_{1} , ..., (A^{nT})^{−1}p_{n}, p_{n+1}, ..., p_{n+m+1})

where ∑_{i=1}^{n+m+1} p_{i} ∈ D_{0}^{⊥} , which gives e ∈ B_{2} ⟹ Ker(P_{A_{2}}) ⊂ B_{2} .

Defining the operator T (y) in the same manner as in (10) the optimality conditions (7)-(9) have for the special case β_{i} = 1 the following form :

\overline{p}_{i} = (A^{i})^{−1T} p_{i} ∈ T^{i}(y_{i}) = ∂ (∥y_{i} − a^{i}∥) , i = 1 , ..., n,

\overline{p}_{n+j} = p_{n+j} ∈ T^{n+j}(x) = N_{D_{j}}(x) , j = 1 , ..., m,

\overline{p}_{n+m+1} = p_{n+m+1} = T^{n+m+1}(x) = c,

where

p = (\overline{p}_{1}, ... , \overline{p}_{n+m+1}) = ((A^{1})^{−1T} p_{1}, ..., (A^{n})^{−1T} p_{n}, p_{n+1, ...,} p_{n+m+1}) ∈ B_{2}, which is equivalent to

p ∈ T (y) and 0 ∈ T_{A_{2}}(y + p),

where p ∈ B_{2} and y ∈ A_{2} . Applying the proximal point algorithm (14)-(16) we get the following iteration formulas :

p̃_{i}^{k} = P_{B^{0}}(y_{i}^{k} + p_{i}^{k} − a^{i}) ; i = 1 , ..., n;

where

B^{0} = {b ∈ H | ∥b∥ = 1} ,
ỹ_{n+j}^{k} = P_{D_{j}}(y_{n+j}^{k} + p_{n+j}^{k}) ; j = 1 , ..., m,
p̃_{n+j}^{k} = y_{n+j}^{k} + p_{n+j}^{k} − ỹ_{n+j}^{k} ; j = 1 , ..., m,
ỹ_{i}^{k} = y_{i}^{k} + p_{i}^{k} − p̃_{i}^{k} ; i = 1 , ..., n,

and the new iterates p^{k+1} and y^{k+1} may be calculate by the projections

p^{k+1} = (p̃^{k})_{B_{2}}

and

y^{k+1} = (ỹ^{k})_{A_{2}}

onto the subspaces A_{2} and B_{2} respectively .

5 Comments

Finally, we remark that the general convergence results for Spingarn’s algorithm (compare [13] and chapter 4.1) also hold for our application of the proximal point algorithm. In a further paper we will present applications of the given algorithm to location and optimal control problems and discuss numerical results. Furthermore, we will apply the given algorithm to an objective functional f(x) containing different norms of the form

f(x) = (c, x) + ∑_{i=1}^{n} α_{i} ∥A^{i}x − a^{i}∥_{i} → min_{x∈D}  (39)

References

[1] Benker, H.(1985): Upper and lower bounds for minimal norm problems under linear constraints. Banach Center Publications Warsaw, vol.14, 35-45

[2] Cooper, L.; Katz, I.N.(1981): The Weber problem revisited. Computers and Mathematics with Applications (7), 225-234

[3] Durier, R.(1984): On efficient points and Fermat-Weber problem. Working Paper, Universite de Bourgogne, Dijon, France

[4] Durier, R.; Michelot, C.(1985): Geometrical properties of the Fermat-Weber problem. European Journal of Operational Research 20, 332-343

[5] Francis, R.L. ; White, J.A. (1974): Facility Layout and Location: An Analytical Approach. Prentice-Hall, Englewood Cliffs, NJ

[6] Göpfert, A. (1973): Mathematische Optimierung in Allgemeinen Vektorräumen. BSB B.G. Teubner Verlagsgesellschaft, Leipzig

[7] Idrissi, H.; Lefebvre, O.; Michelot, C.(1988): A Primal-Dual Algorithm for a constrained Fermat-Weber Problem Involving Mixed Norms. Recherche operationnelle / Operations Research 22 (4), 313-330 [8] Jahn, J.(1983): Zur vektoriellen linearen Tschebyscheff - Approximation.

Math. Operationsforsch. Statist. Ser. Optim. 14, 577-591

[9] Jahn, J.(1986): Mathematical Vector Optimization in Partially Ordered Spaces. Lang Verlag Frankfurt, Bern, New York

[10] Kuhn, H.W.(1973): A note on Fermat’s problem. Mathematical Programming 4, 98-107

[11] Michelot, C.; Lefebvre, O.(1987): A Primal-dual Algorithm for the Fermat-Weber Problem Involving Mixed Gauges. Mathematical Programming 39, 319-335.

[12] Rockafellar, R.T.(1976): Monotone operators and the proximal point algorithm. SIAM J. Contr.Optim.(14), 877-898

[13] Spingarn, J.E.(1983): Partial inverse of a monontone operator. Applied Mathematics and Optimization (10), 247-265

[14] Spingarn, J.E.(1985): Applications of the Method of partial inverses to convex programming: decomposition. Mathematical Programming (32), 199-223

[15] Tammer, Ch.; Tammer, K.(1991): Generalization and sharpening of some duality relations for a class of vector optimization problems. ZOR-Methods and Models of Operations Research (35), 249-265

[16] Tammer, Ch.(1993): Necessary conditions for approximately efficient solutions of vector approximation problems. Proceedings of the 2nd Conference on Approximation and Optimization, Havana 1993, (to appear)

[17] Weiszfeld, E.(1937): Sur le point pour lequel la somme des distances de n points donnes est minimum. The Tohoku Mathematical Journal (43) , 355-386

[18] Wendell, R.E.; Peterson, E.L.(1984): A dual approach for obtaining lower bounds to the Weber problem. Journ. of Regional Science (24), 219-228 [19] Witzgall, C.(1964): Optimal location of a central facility: Mathemat-

ical models and concepts. National Bureau of Standards, Report 8388, Washington

[20] Zeidler, E.(1978): Vorlesungen über nichtlineare Funktionalanalysis III - Variationsmethoden und Optimierung. Teubner Verlagsgesellschaft, Leipzig.