Geometrical and analytical characterizations of piecewise affine mappings

V. V. Gorokhovik

Trudy Instituta matematiki, Tome 15 (2007) no. 1, pp. 22-32.

Résumé

Let $X$ and $Y$ be finite dimensional normed spaces, $\mathcal{F}(X,Y)$ a collection of all mappings from $X$ into $Y$. A mapping $P\in\mathcal{F}(X,Y)$ is said to be piecewise affine if there exists a finite family of convex polyhedral subsets covering $X$ and such that the restriction of $P$ on each subset of this family is an affine mapping. In the paper we prove a number of characterizations of piecewise affine mappings. In particular we prove that a mapping $P\colon X\to Y$ is piecewise affine if and only if for any partial order $\preceq$ defined on $Y$ by a polyhedral convex cone both the $\preceq$-epigraph and the $\preceq$-hypograph of $P$ can be represented as a union of finitely many of convex polyhedral subsets of $X\times Y$. Without any restriction of generality we can suppose in addition that the space $Y$ is ordered by a minihedral cone or equivalently that $Y$ is a vector lattice. Then as is well known the collection $\mathcal{F}(X,Y)$ endowed with standard pointwise algebraic operations and the pointwise ordering are a vector lattice too. In the paper we show that the collection of piecewise affine mappings coincides with the smallest vector sublattice of $\mathcal{F}(X,Y)$ containing all affine mappings. Moreover we prove that each convex (with respect to an ordering of $Y$ by a minihedral cone) piecewise affine mapping is the least upper bound of finitely many of affine mappings. The collection of all convex piecewise affine mappings is a convex cone in $\mathcal{F}(X,Y)$ the linear envelope of which coincides with the vector subspace of all piecewise affine mappings.

Bibliographie

[1] Rurk K., Sanderson B., Vvedenie v kusochno lineinuyu topologiyu, Mir, M., 1974 | MR

[2] Subbotin A.I., Minimaksnye neravenstva i uravneniya Gamiltona–Yakobi, Nauka, M., 1991 | MR

[3] Subbotin A.I., Shagalova L.G., “Kusochno-lineinoe reshenie zadachi Koshi dlya uravneniya Gamiltona–Yakobi”, Dokl. RAN, 325:5 (1992), 932–936 | MR | Zbl

[4] Gorokhovik V.V., Zorko O.I., “Poliedralnaya kvazidifferentsiruemost veschestvennoznachnykh funktsii”, Dokl. AN Belarusi, 36:5 (1992), 393–397 | MR | Zbl

[5] Gorokhovik V.V., Zorko O.I., “Piecewise affine functions and polyhedrel sets”, Optimization, 31:3 (1994), 3–17 | DOI | MR

[6] Gorokhovik V.V., Zorko O.I., “Nevypuklye mnogogrannye mnozhestva i funktsii i ikh analiticheskie predstavleniya”, Dokl. AN Belarusi, 39:1 (1995), 5–9 | MR

[7] Grünbaum B., Convex Polytopes, John Wiley Sons, London–New York–Sydney, 1967 | MR

[8] Rokafellar R., Vypuklyi analiz, Mir, M., 1973

[9] Leikhtveis K., Vypuklye mnozhestva, Nauka, M., 1985 | MR

[10] Brensted A., Vvedenie v teoriyu vypuklykh mnogogrannikov, Mir, M., 1988 | MR

[11] Robinson S., “Some continuity properties of polyhedral multifunctions”, Mathematical Programming Study, 14 (1981), 206–214 | MR | Zbl

[12] Chernikov S.N., Lineinye neravenstva, Nauka, M., 1968 | MR | Zbl

[13] Dantsig Dzh., Lineinoe programmirovanie, ego primeneniya i obobscheniya, Progress, M., 1966

[14] Ashmanov S.A., Lineinoe programmirovanie, Nauka, M., 1981 | Zbl

[15] Birkgof G., Teoriya reshetok, Nauka, M., 1984 | MR

[16] Grettser G., Obschaya teoriya reshetok, Mir, M., 1982 | MR

[17] Melzer D., “On the expressibility of piecewise-linear continuous functions as the difference of two piecewise-linear convex functions”, Mathematical Programming Study, 29 (1986), 118–134 | MR | Zbl

[18] Kripfganz A., Schulze R., “Piecewise affine functions as the difference of two convex functions”, Optimization, 18:1 (1987), 23–29 | DOI | MR | Zbl

[19] Burbaki N., Obschaya topologiya. Ispolzovanie veschestvennykh chisel v obschei topologii. Funktsionalnye prostranstva. Svodka rezultatov, Nauka, M., 1975

[20] Glazman I.M., Lyubich Yu.I., Konechnomernyi lineinyi analiz, Nauka, M., 1969 | MR | Zbl