An Algorithm for Vectorial Control Approximation Problems

H.Benker A.Hamel Chr.Tammer

Martin-Luther-University Halle-Wittenberg, D-06099 Halle, Germany

Abstract

We consider a convex vectorial control approximation problem and derive necessary and sufficient optimality conditions for solutions of a corresponding scalarized problem using the subdifferential calculus. These optimality conditions can be solved by a proximal point algorithm introduced in [3]. This fact together with some stability results form the base of a dialogue algorithm to generate approximate solutions of the vectorial problem.

Keywords. Approximation problem, stability, dialogue algorithm

1 Introduction

Several authors have studied vectorial and scalar location and approximation problems from the theoretical as well as the computational point of view (see [5], [6], [7], [12], [13], [16], [18], [21], [22], [23]). The aim of this paper is to extend the results of Michelot and Lefebvre [16] and Idrissi, Lefebvre and Michelot [12] to a general vectorial control approximation problem. In order to formulate this problem we suppose that

(A) a^{i}, x ∈ X , α_{i} ≥ 0 , β_{i} ≥ 1, C ∈ L(X → R^{n}), A^{i} ∈ L (X → Y_{i}), (i = 1, ..., n), (L(X → Y) denotes the space of linear continuous operators from X to Y),

(B) D_{j} ⊂ X ( j = 1, ..., m) are closed and convex sets, D_{0} ⊆ X is a closed

linear subspace and D = ⋂_{j=0}^{m} D_{j} is non-empty and bounded.

(C) One of the following conditions (C1) or (C2) is fulfilled:

(C1) H is a Hilbert space and X = Y_{i} = H for all i = 1, ..., n

(C2) X = R^{k} and Y_{i} = R^{m_{i}} for all i = 1, ..., n.

(D) K ⊂ R^{n} is a convex cone with cl K + (R_{+}^{n} \ {0}) ⊂ int K.

Now, we consider the following vectorial control approximation problem

(P) :  Compute the set  Eff(f[D], K),

where

f(x) := C(x) + ( \begin{matrix}α_{1} || A^{1}(x) − a^{1} ||^{β_{1}} \\ ⋯ \\ α_{n} || A^{n}(x) − a^{n} ||^{β_{n}} \end{matrix} )  (1)

and

Eff(f[D], K) := {f(x) | x ∈ D, f[D] ∩ (f(x) − (K \ {0})) = ∅}.

Remark 1: Problem (P) can be considered as an extension of a scalar problem studied by Idrissi, Lefebvre and Michelot [12]:

∑_{i=1}^{n} α_{i} || x − a^{i} ||_{i}⟶ min_{x∈D}

with D_{j} ⊂ R^{p} (j = 0, 1, ..., m), x, a^{i} ∈ R^{p} (i = 1, ..., n).

Remark 2: The class of problems (P) contains many practically important special cases:

1. Linear vector optimization problems (α_{i} = 0, i = 1, ..., n).

2. Surrogate problems for linear vector optimization problems

Eff(f_{1}[D], K),

where

f_{1}(x) := C(x), D = {x ∈ D | A^{i}(x) = a^{i}(i = 1, ..., n)},

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

3. Perturbed respectively regularized linear vector optimization problems.

4. Vector-valued optimal control problems of the form (see Benker and

Kossert [2]):

Eff(f_{2}[U], R_{+}^{2}),

with

f_{2}(u) := ( \begin{matrix}|| Au − a ||^{p} \\ || u ||^{p} \end{matrix} ) , u ∈ U ⊂ X,

where C = 0, n = 2, β_{i} = p (i = 1, 2), H_{1} and H_{2} are Hilbert spaces, A ∈ L(H_{1} ⟶ H_{2}), a ∈ H_{2}, U ⊂ H_{1} is a nonempty closed convex set and R_{+}^{2} denotes the usually ordering cone in R^{2}. Here u denotes the so called control variable, the image z = Au denotes the state variable.

5. Vectorial approximation and location problems (cf. Jahn [14], Gerth and Pöhler [8], Wanka [21] ).

In order to derive a primal-dual algorithm we assume in the following that any suitable constraint qualification (generalized Slater condition, stability ...) is fulfilled (cf. [9]). Moreover, we suppose that the inverse operator (A^{iT})^{−1} of the adjoint operator A^{iT} to A^{i} exists for all i = 1, ..., n. Furthermore, N_{D_{j}}(x^{0}) denotes the normal cone to D_{j} at x^{0} ∈ X defined by

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

B^{0} denotes the unit sphere associated with the dual norm of the norm || . ||. P_{D}(e) denotes the projection of the element e ∈ X onto the set D. The paper is organized as follows: In Chapter 2 we introduce a suitable scalarization of the vectorial control approximation (P). Furthermore, in Chapter 3 we derive optimality conditions for the scalarized problem using the subdifferential calculus. These optimality conditions are useful for applying Spingarn’s proximal point algorithm (see [12], [16] and [17]) for solving problem (P) in Chapter 4. Finally, in Chapter 5 we derive a dialogue algorithm for the vectorial control approximation problem using a surrogate parametric optimization problem and taking into account stability results of this special parametric optimization problem.

2 A suitable scalarization of the vector optimization problem

Under the given assumptions it is easy to see that the vector-valued objective function f : X ⟶ R^{n} in (1) is (R_{+}^{n}) - convex, i.e., for all x_{1}, x_{2} ∈ X, μ ∈ [0, 1] it holds μf(x_{1}) + (1 − μ)f(x_{2}) ∈ f(μx_{1} + (1 − μ)x_{2}) + R_{+}^{n}. Then we can show (compare [14]) that for each element f(x^{0}) ∈ Eff(f[D], K) there exists a parameter λ ∈ int K^{∗} (K^{∗} denotes the dual cone to K) such that x^{0} solves the real-valued optimization problem

(P (λ)) : f(x, λ) := ∑_{i=1}^{n} λ_{i}(C_{i}(x) + α_{i} || A^{i}(x) − a^{i} ||^{β_{i}}) ⟶ min_{x∈D} .

In the following for the case α_{i} > 0 for all i = 1, ..., n without loss of generality we replace (P (λ)) by

(P′_{s}) : (c, x) + ∑_{i=1}^{n} || A^{i}(x) − a^{i} ||^{β_{i}}⟶ min_{x∈D},

where c ∈ X^{∗}. 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 (P′_{s}) is equivalent to the following unconstrained minimization problem

(P_{s}) : F (x) = (c, x) + ∑_{i=1}^{n} ∥A^{i}x − a^{i}∥^{β_{i}} + ∑_{j=0}^{m} χ_{D_{j}}(x) → min_{x∈X} . (2)

3 Optimality conditions for the scalarized problem

At first we consider the case of ((A), (B), (C1)). Obviously, under the given assumptions the functional F in (2) is convex. Therefore, the subdifferentialcondition

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

is necessary and sufficient for the optimality of a feasible x^{0} (compare Zeidler [24]). Applying the rule for sums of subdifferentials and the known formula for the subdifferential of a indicator function (∂χ_{D_{j}}(·) = N_{D_{j}}(·)) to the functional F in (2) we can write (3) equivalently in the form that there are q_{i} (i = 1, ..., n), r_{j} (j = 1, ..., m) with

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

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

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

(compare [3]). In order to reformulate the optimality conditions (4) - (6) in a more practical way we introduce a 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,

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) := (T^{1}(x), ..., T^{n+m+1}(x)), y = (x, ..., x),  (7)

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 (4)-(6) can be rewritten as:

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

Remark 3: Under the assumptions ((A), (B), (C2)) we can define the space E and the subspaces A and B analogously with R^{k} instead of H.

4 Application of the proximal point algorithm

In [3] we have shown that under ((A), (B), (C1)) the assumptions for a successful application of the proximal point algorithm of Spingarn [17] for the solution of (8) are fulfilled. This algorithm has the form

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

where the starting point z^{1} is arbitrary and {c_{k}} is a sequence of positive real numbers and T_{A} is the partial inverse of T with respect to A. If {c_{k}} is bounded away from zero (for simplicity 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 [17]). Taking into account the structure of the subdifferential of the norm and some relations of this subdifferential to certain normal cones and projections we have derived in [3] the following proximal point algorithm PPACAP for solving (P_{s}) in the special β_{i} = 1 for all i = 1, ..., n. For the case β_{i} = β ≥ 1 compare subsection 4.1.2 in [3], where we have transformed the problem in such a way that we can use the following algorithm too. Algorithm (PPACAP):

• Choose arbitrary initial points

x^{1} ∈ D_{0}  and  p^{1} ∈ B.  (10)

• 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,  (11)

x^{k+1} + p_{n+j}^{k} − p_{n+j}^{k+1} = P_{D_{j}}(x^{k} + p_{n+j}^{k}),  j = 1, ..., m,  (12)
x^{k} − x^{k+1} + p_{n+m+1}^{k+1} = c,  (13)

with

p_{i}^{k+1} ∈ B  and  x^{k+1} ∈ D_{0},  (14)

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

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

Remark 4: According to Remark 3 under the assumptions (A), (B), (C2)) it is possible to derive the algorithm in the same way. In this case the weak convergence of the sequence {z^{k}} implies even the norm convergence.

5 A dialogue algorithm for the vectorial control approximation problem (P)

In this section we present a dialogue algorithm, in which we have to solve the special parametric optimization problem from Chapter 2 under the assumptions ((A), (B), (C1)) or ((A), (B), (C2)) :

(P (λ)) : f(x, λ) = ∑_{i=1}^{n} λ_{i}(C_{i}(x) + α_{i} || A^{i}(x) − a^{i} ||^{β_{i}}) ⟶ min_{x∈D},

where λ ∈ Λ ⊂ int K^{∗}.

Stability results for parametric optimization problems are important for an effective dialogue algorithm. With other words, we need various types of semicontinuity of the optimal value function

φ(λ) := inf{f(x, λ) | x ∈ D},

of the optimal set mapping

ψ(λ) := {x ∈ D | f(x, λ) = φ(λ)}

or of the ϵ-optimal set mappings

ψ_{ϵ}(λ) := {x ∈ D | f(x, λ) < φ(λ) + ϵ}

and

ψ̄(λ, ϵ) := {x ∈ D | f(x, λ) ≤ φ(λ) + ϵ}

By stability of the mappings φ, ψ, ψ_{ϵ} and ψ̄ we mean in particular certain continuity attributes of these mappings. We use the concept of semicontinuity according to Berge ([4]):

Definition 1 A point-to-set mapping Γ : Λ ⟶ 2^{X}, where (X, d_{X}) and (Λ, d_{Λ}) are metric spaces, is called:

1. upper semicontinuous in the sense of Berge at a point λ^{o}, if for each open set Ω containing Γ(λ^{o}) there exists a δ- neighbourhood V_{δ}{λ^{o}} of λ^{o} such that

Γ(λ) ⊂ Ω  for all  λ ∈ V_{δ}{λ^{o}};

2. lower semicontinuous in the sense of Berge at a point λ^{o} , if for each open set Ω satisfying Ω ∩ Γ(λ^{o}) ≠ ∅ there exists a δ-neighbourhood V_{δ}{λ^{o}} of λ^{o} such that

Γ(λ) ∩ Ω ≠ ∅  for all  λ ∈ V_{δ}{λ^{o}}.

The existence of continuous selection functions is closely related to the condition that ψ is lower semicontinuous in the sense of Berge and all optimal sets are non-empty and convex. If one considers ϵ- optimal solutions then the strong condition of lower semicontinuity of ψ may be avoided.

Theorem 1 Let the assumptions ((A), (B), (C1)) are fulfilled. Then for each ϵ > 0 the ϵ-optimal set mapping ψ_{ϵ} is lower semicontinuous in the sense of Berge.

Proof: The assumptions of Theorem 4.2.4. in [1] are fulfilled, since f is continuous on X × Λ, D is closed and does not depend on the parameter λ and φ is continuous regarding the continuity of f on the set D. Theorem 4.2.4 in [1] yields that for each ϵ > 0 the ϵ-optimal set mapping ψ_{ϵ} is lower semicontinuous .

In the finite dimensional case we can derive some additional results:

Theorem 2 We consider the problem (P (λ)) subject to the assumptions ((A), (B) and (C2)) . Suppose that ψ(λ^{0}) is non-empty and bounded. Then

• the the optimal value function φ is continuous at λ^{0},

• the optimal set mapping ψ is upper semicontinuous in the sense of Berge at λ^{0},

• the ϵ-optimal set mapping ψ_{ϵ} is lower semicontinuous in the sense of Berge at λ^{0} for each ϵ > 0,

• the mapping ψ̄ defined by

ψ̄(λ, ϵ) := {x ∈ M | f(x, λ) ≤ φ(λ) + ϵ}, λ ∈ Λ, ϵ ≥ 0,

is upper semicontinuous in the sense of Berge at (λ^{0}, 0).

Proof: The results follow immediately from Theorem 9 in Hogan [11].

Remark 5: The last property is of interest if the problems corresponding to the parameters λ^{t}, t = 1, 2, ..., λ^{t} ⟶ λ^{0}, constitute certain substitute problems with respect to the problem to be solved, (P (λ^{0})), and the problems (P (λ^{t})) are solved with increasing accuracy ϵ_{t} ⟶ 0. Then each sequence {x^{t}} of ϵ_{t}-optimal solutions of (P (λ^{t})) possesses an accumulation point and each of its accumulation points is contained in the solution set ψ(λ^{0}).

Moreover, under the assumptions of Theorem 2 a Continuous Selection Theorem of Michael [15] can be used if we additionally assume the compactness of Λ.

Theorem 3 Assume ((A), (B), (C)) and Λ is a compact set. Then there exists a function g ∈ C(Λ, X) such that

g(λ) ∈ cl ψ_{ϵ}(λ) ∀λ ∈ Λ.

Proof: We can conclude from Theorem 1 and 2 respectively that ψ_{ϵ} is lower semicontinous in the sense of Berge. Moreover, the image sets ψ_{ϵ}(λ) are nonempty and convex for all λ ∈ Λ. Then we get the desired result from the Continuous Selection Theorem of Michael [15].

Using these stability statements we can derive the following dialogue algorithm for the vectorial control approximation problem (P) with the help of them at least under ((A), (B), (C2)) it is possible to seek for elements of a neighbourhood of the set of proper efficient points which corresponds to the individual interest of the decision maker (compare [10], [20]).

Step 1: Choose λ̄ ∈ Λ. Compute an approximate solution (x^{0}, p^{0}) with the primal-dual algorithm (PPACAP). If (x^{0}, p^{0}) is accepted by the decision-maker, then stop. Otherwise go to Step 2.

Step 2: Put k = 0, t_{0} = 0. Choose λ̂ ∈ Λ, λ̂ ≠ λ̄. Go to Step 3.

Step 3: Choose t_{k+1} with t_{k} < t_{k+1} ≤ 1 and compute an approximate solution (x^{k+1}, p^{k+1}) of

P (t_{k+1}, λ̄, λ̂) : min_{x∈D}{∑_{i=1}^{n}(λ̄_{i}+t_{k+1}(λ̂_{i}−λ̄_{i}))(C_{i}(x)+α_{i} || A^{i}(x)−a^{i} ||^{β_{i}}}

with the algorithm PPACAP and use (x^{k}, p^{k}) as starting point. If an approximate solution of P (t, λ̄, λ̂) cannot be found for t > t_{k}, then go to Step 1. Otherwise go to Step 4.

Step 4: The point (x^{k+1}, p^{k+1}) is to be evaluated by the decision-maker. If it is accepted by the decision-maker, then stop. Otherwise go to Step 5.

Step 5: If t_{k+1} ≥ 1, then go to Step 1. Otherwise set k = k + 1 and go to Step 3.

Remark 6: Under the assumptions ((A), (B), (C2)) of Theorem 3 a sufficiently good approximation of a solution of (P (t_{k+1}, λ̄, λ̂) can be generated if we use an approximate solution of (P (t_{k}, λ̄, λ̂)) as starting point.

References

[1] Bank, B.; Guddat, J.; Klatte, D.; Kummer, B.; Tammer, K. : Non-Linear Parametric Optimization. Akademie-Verlag, Berlin 1982

[2] Benker, H. and Kossert, S. : Remarks on quadratic optimal control problems in Hilbert spaces. Zeitschrift für Analysis und ihre Anwendungen 1 (3) (1982) 13-21

[3] Benker, H.; Hamel, A.; Tammer, Chr. : A Proximal Point Algorithm for Control Approximation Problems. To appear: ZOR (1994)

[4] Berge, C.: Topological spaces. Oliver and Boyd, London 1963

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

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

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

[8] Gerth (Tammer), Chr.; Pöhler, K. : Dualität und algorithmische Anwendung beim vektoriellen Standortproblem. Optimization 19 (1988) 491-512

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

[10] Guddat, J.; Guerra Vasquez, F.; Tammer, K.; Wendler, K. : Multiobjective and Stochastic Optimization Based on Parametric Optimization. Akademie-Verlag, Berlin 1985

[11] Hogan, W.W. : Point-to-set maps in mathematical programming. SIAM Rev. 15 (1973) 591-603 [12] Idrissi, H.; Lefebvre, O.; Michelot, C.: A Primal-Dual Algorithm for a

constrained Fermat-Weber Problem Involving Mixed Norms. Recherche operationnelle / Operations Research 22 (4) (1988) 313-330

[13] Jahn, J.: Zur vektoriellen linearen Tschebyscheff - Approximation. Math. Operationsforsch. Statist. Ser. Optim. 14 (1983) 577-591

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

[15] Michael, E. : Topologies on spaces of subsets. Trans. Amer. Math. Soc. 71 (1951) 152-182

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

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

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

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

[20] Tammer, Chr.: Stability results for approximately efficient solutions. OR Spektrum 16 (1994) 47-52

[21] Wanka, Gert: Duality in Vectorial Control Approximation Problems with Inequality Restrictions. Optimization 22 (1991) 755-764

[22] Wendell, R.E.; Peterson, E.L.: A dual approach for obtaining lower bounds to the Weber problem. Journ. of Regional Science 24 (1984) 219-228

[23] Witzgall, C.: Optimal location of a central facility: Mathematical models and concepts. National Bureau of Standards, Report 8388, Washington (1964)

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