Approximation of set-valued functions by single-valued one

Ginchev, Ivan ; Hoffmann, Armin

Discussiones Mathematicae. Differential Inclusions, Control and Optimization, Tome 22 (2002) no. 1, pp. 33-66.

Résumé

Let Σ: M → 2^Y{∅ be a set-valued function defined on a Hausdorff compact topological space M and taking values in the normed space (Y,||·||). We deal with the problem of finding the best Chebyshev type approximation of the set-valued function Σ by a single-valued function g from a given closed convex set V ⊂ C(M,Y). In an abstract setting this problem is posed as the extremal problem sup_t ∈ M ρ(g(t), (t)) → inf, g ∈ V. Here ρ is a functional whose values ρ(q,S) can be interpreted as some distance from the point q to the set S ⊂ Y. In the paper, we are confined to two natural distance functionals ρ = H and ρ = D. H(q,S) is the Hausdorff distance (the excess) from the point q to the set cl S, and D(q,S) is referred to as the oriented distance from the point q to set cl conv S. We prove that both these problems are convex optimization problems. While distinguishing between the so called regular and irregular case problems, in particular the case V = C(M,Y) is studied to show that the solutions in the irregular case are obtained as continuous selections of certain set-valued maps. In the general case, optimality conditions in terms of directional derivatives are obtained of both primal and dual type.

Détail

Keywords: Chebyshev approximation, set-valued functions, convex optimization

Bibliographie

[1] J.P. Aubin and A. Cellina, Differential Inclusions, Springer, Berlin, Heidelberg, New York, Tokyo 1984.

[2] P.K. Belobrov, K voprosu o chebyshevskom sentre mnozhestva, Izvestija vysshich uchebnych zavedenij 38 (1) (1964), 3-9. (in Russian)

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

[4] F.H. Clarke, Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, A Wiley-Interscience Publication, John Wiley Sons, New York 1983.

[5] V.F. Demjanov and A.M. Rubinov, Constructive Nonsmooth Analysis, Verlag Peter Lang, Frankfurt am Main 1995.

[6] A.L. Garkavi, On the best net and the best cut of a set in a normed space, Izv. Akad. Nauk SSSR, Ser. Mat. 26 (1962), 87-106. (in Russian)

[7] A.L. Garkavi, On the Chebyshev center and the convex hull of a set, Usp. Mat. Nauk 19 (6) (1964), 139-145, (120). (in Russian)

[8] A.L. Garkavi, Minimax balayge theorem and an inscribed ball problem, Matematicheskie Zametki 30 (1) (1981), 109-121. (in Russian)

[9] I. Ginchev and A. Hoffmann, On the best approximation of set-valued functions, in: P. Gritzmann, R. Horst, E. Sachs, R. Tichatschke (eds.), Recent Advances in Optimization (Proc. of the 8th French-German Conference on Optimization, Trier, July 21-26, 1996, Lect. Notes Econ. Math. Syst. 452, Springer, Berlin Heidelberg 1997, 61-74.

[10] P.M. Gruber, The space of convex bodies, in: P.M. Gruber, J.M. Wills (eds.), Handbook of Convex Geometry, Volume A, North-Holland, Amsterdam 1993, 301-318.

[11] R. Hettich and P. Zencke, Numerische Methoden der Approximation und Semi-Infiniten Optimierung, B.G. Teubner, Leipzig 1982.

[12] A. Hoffmann, The distance to the intersection of two convex sets expressed by the distances to each of them, Math. Nachr. 157 (1992), 81-98.

[13] J.B. Hiriart Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Springer Verlag, Berlin 1993.

[14] R.B. Holmes, Geometric Functional Analysis and its Applications, Graduate Texts in Mathematics 24, Springer, New York-Heidelberg-Berlin 1975.

[15] R. Horst and H. Tuy, Global Optimization, Deterministic Approaches, Springer, Berlin etc. 1990.

[16] P. Kosmol, Optimierung und Approximation, Walter de Gruyter, Berlin 1991.

[17] P.J. Laurent, Approximation et Optimisation, Enseignement des Sciences 13, Hermann, Paris 1972.

[18] K. Leichtweiss, Konvexe Mengen, Deutscher Verlag der Wissenschaften, Berlin 1980.

[19] L.E. Rybiński, Continuous Selections and Variational Systems, Monografie 61, Institute of Mathematics, Higher College of Engineering, Zielona Góra, Poland 1992, 100 pp, ISSN 0239-7390.

[20] R.T. Rockafellar and R.J.B. Wets, Variational Analysis, Grundlehren der mathematischen Wissenschaften 317, Springer, Berlin 1998.

[21] I. Singer, Best Approximation in Normed Linear Spaces by Elements of Linear Subspaces, Grundlehren der mathematischen Wissenschaften 171, Springer, Berlin 1970.