CONVEXITY AND CONE-VEXING S. S. KUTATELADZE
1. Agenda Convexity stems from the remote ages and reigns in geometry, optimization, and functional analysis. The union of abstraction and convexity has produced abstract convexity which is a vast area of today’s research, sometimes profitable but sometimes bizarre. Cone-vexing is a popular fixation of vexing conic icons. The idea of convexity feeds generation, separation, calculus, and approximation. Generation appears as duality; separation, as optimality; calculus, as representation; and approximation, as stability. This is an overview of the origin, evolution, and basics of convexity. Study of convexity in the Sobolev Institute was initiated by Leonid Kantorovich (1912–1986) and Alexander Alexandrov (1912–1999). This talk is a part of their memory.
2. Elements, Book I Mathematics resembles linguistics sometimes and pays tribute to etymology, hence, history. Today’s convexity is a centenarian, and abstract convexity is much younger. Vivid convexity is full of abstraction, but traces back to the idea of a solid figure which stems from Euclid. Book I of his Elements [1] has expounded plane geometry and defined a boundary and a figure as follows: Definition 13. A boundary is that which is an extremity of anything. Definition 14. A figure is that which is contained by any boundary or boundaries.
3. Elements, Book XI Narrating solid geometry in Book XI, Euclid travelled in the opposite direction from solid to surface: Definition 1. A solid is that which has length, breadth, and depth. Definition 2. An extremity of a solid is a surface.
He proceeded with the relations of similarity and equality for solids: Definition 9. Similar solid figures are those contained by similar planes equal in multitude. Definition 10. Equal and similar solid figures are those contained by similar planes equal in multitude and magnitude. 1
2
S. S. KUTATELADZE
4. The Origin of Convexity Euclid’s definitions seem vague, obscure, and even unreasonable if applied to the figures other than convex polyhedra. Euclid also introduced a formal concept of “cone” which has a well-known natural origin. However, convexity was ubiquitous in his geometry by default. The term “conic sections” was coined as long ago as 200 BCE by Apollonius of Perga. However, it was long before him that Plato had formulated his famous allegory of cave [2]. The shadows on the wall are often convex. Euclid’s definitions imply the intersection of half-spaces. However, the concept of intersection belongs to set theory which appeared only at the end of the nineteenth century. It is wiser to seek for the origins of the ideas of Euclid in his past rather than his future. Euclid was a scientist not a foreteller. 5. Harpedonaptae The predecessors of Euclid are the harpedonaptae of Egypt as often sounds at the lectures on the history of mathematics. The harpedonaptae or rope stretchers measured tracts of land in the capacity of surveyors. They administered cadastral surveying which gave rise to the notion of geometry. If anyone stretches a rope that surrounds however many stakes, he will distinguish a convex polyhedron, which is up to infinitesimals a typical compact convex set or abstract subdifferential of the present-day mathematics. The rope-stretchers discovered convexity experimentally by measurement. Hence, a few words are in order about these forefathers of their Hahn–Banach next of kin of today. 6. The History of Herodotus Herodotus wrote in Item 109 of Book II Enerpre [3] as follows: Egypt was cut up: and they said that this king distributed the land to all the Egyptians, giving an equal square portion to each man, and from this he made his revenue, having appointed them to pay a certain rent every year: and if the river should take away anything from any man’s portion, he would come to the king and declare that which had happened, and the king used to send men to examine and to find out by measurement how much less the piece of land had become, in order that for the future the man might pay less, in proportion to the rent appointed: and I think that thus the art of geometry was found out and afterwards came into Hellas also.
7. Sulva Sutras Datta [4] wrote: . . . One who was well versed in that science was called in ancient India as samkhyajna (the expert of numbers), parimanajna (the expert in measuring), sama-sutraniranchaka (uniform-rope-stretcher), Shulba-vid (the expert in Shulba) and Shulba-pariprcchaka (the inquirer into the Shulba).
´ Shulba also written as Sulva or Sulva was in fact the geometry of vedic times as ´ codified in Sulva S u ¯tras.
CONVEXITY AND CONE-VEXING
3
8. Veda Since “veda” means knowledge, the vedic epoch and literature are indispensable for understanding the origin and rise of mathematics. In 1978 Seidenberg [5] wrote: Old-Babylonia [1700 BC] got the theorem of Pythagoras from India or that both Old-Babylonia and India got it from a third source. Now the Sanskrit scholars do not give me a date so far back as 1700 B.C. Therefore I postulate a pre-OldBabylonian (i.e., pre-1700 B.C.) source of the kind of geometric rituals we see preserved in the Sulvasutras, or at least for the mathematics involved in these rituals.
Some recent facts and evidence prompt us that the roots of rope-stretching spread in a much deeper past than we were accustomed to acknowledge. 9. Vedis Epoch The exact chronology still evades us and Kak [6] commented on the Seidenberg paper: That was before archaeological finds disproved the earlier assumption of a break in Indian civilization in the second millennium B.C.E.; it was this assumption of the Sanskritists that led Seidenberg to postulate a third earlier source. Now with our new knowledge, Seidenberg’s conclusion of India being the source of the geometric and mathematical knowledge of the ancient world fits in with the new chronology of the texts. . . . in the absence of conclusive evidence, it is prudent to take the most conservative of these dates, namely 2000 B.C.E. as the latest period to be associated with the Rigveda.
10. Mathesis and Abstraction Once upon a time mathematics was everything. It is not now but still carries the genome of mathesis universalis. Abstraction is the mother of reason and the gist of mathematics. It enables us to collect the particular instances of any many with some property we observe or study. Abstraction entails generalization and proceeds by analogy which is tricky and might be misleading. Inventory of the true origins of any instance of abstraction are in order from time to time. “Scholastic” differs from “scholar.” Abstraction is limited by taste, tradition, and common sense. The challenge of abstraction is alike the call of freedom. But no freedom is exercised in solitude. The holy gift of abstraction coexists with gratitude and respect to the legacy of our predecessors who collected the gems of reason and saved them in the treasure-trove of mathematics. 11. Enter Abstract Convexity Stretching a rope taut between two stakes produces a closed straight line segment which is the continuum in modern parlance. Rope stretching raised the problem of measuring the continuum. The continuum hypothesis of set theory is the shadow of the ancient problem of harpedonaptae. Rope stretching independent of the position of stakes is uniform with respect to direction in space. The mental experiment of uniform rope stretching yields a compact convex figure. The harpedonaptae were experts in convexity.
4
S. S. KUTATELADZE
Convexity has found solid grounds in set theory. The Cantor paradise became an official residence of convexity. Abstraction becomes an axiom of set theory. The abstraction axiom enables us to reincarnate a property, in other words, to collect and to comprehend. The union of convexity and abstraction was inevitable. Their child is abstract convexity [7]–[14]. 12. Minkowski Duality Let E be a complete lattice E with the adjoint top > := +∞ and bottom ⊥ := −∞. Assume further that H is some subset of E which is by implication a (convex) cone in E, and so the bottom of E lies beyond H. A subset U of H is convex relative to H or H-convex provided that U is the H-support set UpH := {h ∈ H : h ≤ p} of some element p of E. Alongside the H-convex sets we consider the so-called H-convex elements. An element p ∈ E is H-convex provided that p = sup UpH ; i.e., p represents the supremum of the H-support set of p. The H-convex elements comprise the cone which is denoted by C (H, E). We may omit the references to H when H is clear from the context. It is worth noting that convex elements and sets are “glued together” by the Minkowski duality ϕ : p 7→ UpH . This duality enables us to study convex elements and sets simultaneously [15]. 13. Enter the Reals Optimization is the science of choosing the best. To choose, we use preferences. To optimize, we use infima and suprema (for bounded subsets) which is practically the least upper bound property. So optimization needs ordered sets and primarily Dedekind complete lattices. To operate with preferences, we use group structure. To aggregate and scale, we use linear structure. All these are happily provided by the reals R, a one-dimensional Dedekind complete vector lattice. A Dedekind complete vector lattice is a Kantorovich space. 14. Legendre in Disguise An abstract minimization problem is as follows: x ∈ X,
f (x) → inf .
Here X is a vector space and f : X → R is a numeric function taking possibly infinite values. The sociological trick includes the problem into a parametric family yielding the Young–Fenchel transform of f : f ∗ (l) := sup (l(x) − f (x)), x∈X #
of l ∈ X , a linear functional over X. The epigraph of f ∗ is a convex subset of X # and so f ∗ is convex. Observe that −f ∗ (0) is the value of (∗). 15. Order Omnipresent A convex function is locally a positively homogeneous convex function, a sublinear functional. Recall that p : X → R is sublinear whenever epi p := {(x, t) ∈ X × R : p(x) ≤ t}
CONVEXITY AND CONE-VEXING
5
is a cone. Recall that a numeric function is uniquely determined from its epigraph. Given C ⊂ X, put H(C) := {(x, t) ∈ X × R+ : x ∈ tC}, the H¨ ormander transform of C [16]. Now, C is convex if and only if H(C) is a cone. A space with a cone is a (pre)ordered vector space.
16. Fermat’s Criterion The subdifferential of f at x ¯ is defined as ∂f (¯ x) := {l ∈ X # : (∀x ∈ X) l(x) − l(¯ x) ≤ f (x) − f (¯ x)}. A point x ¯ is a solution to the minimization problem of §14 if and only if 0 ∈ ∂f (¯ x). This Fermat criterion turns into the Rolle Theorem in a smooth case and is of little avail without effective tools for calculating ∂f (¯ x). A convex analog of the “chain rule” is in order.
17. Enter Hahn–Banach The Dominated Extension, an alias of Hahn–Banach, takes the form ∂(p ◦ ι)(0) = (∂p)(0) ◦ ι, with p a sublinear functional over X and ι the identical embedding of some subspace of X into X. In fact, the situation is even more spectacular: Theorem. A preordered vector space X admits dominated extension of linear operators if and only if X has the least upper bound property.
18. Nonoblate Cones Consider cones K1 and K2 in a topological vector space X and put κ := (K1 , K2 ). Given a pair κ define the correspondence Φκ from X 2 into X by the formula Φκ := {(k1 , k2 , x) ∈ X 3 : x = k1 − k2 ∈ Kı }. Clearly, Φκ is a cone or, in other words, a conic correspondence. The pair κ is nonoblate whenever Φκ is open at the zero. Since Φκ (V ) = V ∩ K1 − V ∩ K2 for every V ⊂ X, the nonoblateness of κ means that κV := (V ∩ K1 − V ∩ K2 ) ∩ (V ∩ K2 − V ∩ K1 ) is a zero neighborhood for every zero neighborhood V ⊂ X.
6
S. S. KUTATELADZE
19. Open Correspondences Since κV ⊂ V − V , the nonoblateness of κ is equivalent to the fact that the system of sets {κV } serves as a filterbase of zero neighborhoods while V ranges over some base of the same filter. Let ∆n : x 7→ (x, . . . , x) be the embedding of X into the diagonal ∆n (X) of X n . A pair of cones κ := (K1 , K2 ) is nonoblate if and only if λ := (K1 × K2 , ∆2 (X)) is nonoblate in X 2 . Cones K1 and K2 constitute a nonoblate pair if and only if the conic correspondence Φ ⊂ X × X 2 defined as Φ := {(h, x1 , x2 ) ∈ X × X 2 : xı + h ∈ Kı (ı := 1, 2)} is open at the zero. 20. General Position of Cones Cones K1 and K2 in a topological vector space X are in general position iff (1) the algebraic span of K1 and K2 is some subspace X0 ⊂ X; i.e., X0 = K1 − K2 = K2 − K1 ; (2) the subspace X0 is complemented; i.e., there exists a continuous projection P : X → X such that P (X) = X0 ; (3) K1 and K2 constitute a nonoblate pair in X0 . 21. General Position of Operators Let σn stand for the rearrangement of coordinates σn : ((x1 , y1 ), . . . , (xn , yn )) 7→ ((x1 , . . . , xn ), (y1 , . . . , yn )) which establishes an isomorphism between (X × Y )n and X n × Y n . Sublinear operators P1 , . . . , Pn : X → E ∪ {+∞} are in general position if so are the cones ∆n (X) × E n and σn (epi(P1 ) × · · · × epi(Pn )). Given a cone K ⊂ X, put πE (K) := {T ∈ L (X, E) : T k ≤ 0 (k ∈ K)}. Clearly, πE (K) is a cone in L (X, E). Theorem. Let K1 , . . . , Kn be cones in a topological vector space X and let E be a topological Kantorovich space. If K1 , . . . , Kn are in general position then πE (K1 ∩ · · · ∩ Kn ) = πE (K1 ) + · · · + πE (Kn ). This formula opens a way to various separation results. 22. Separation Sandwich Theorem. Let P, Q : X → E ∪ {+∞} be sublinear operators in general position. If P (x) + Q(x) ≥ 0 for all x ∈ X then there exists a continuous linear operator T : X → E such that −Q(x) ≤ T x ≤ P (x)
(x ∈ X).
Many efforts were made to abstract these results to a more general algebraic setting and, primarily, to semigroups and semimodules. Tropicality chases separation [17, 18].
CONVEXITY AND CONE-VEXING
7
23. Enter Kantorovich The matching of convexity and order was established in two steps. Hahn–Banach–Kantorovich Theorem. Every Kantorovich space admits dominated extension of linear operators. This theorem by Kantorovich is the first theorem of the theory of K-spaces. Bonnice–Silvermann–To Theorem. Each ordered vector space admitting dominated extension of linear operators is a Kantorovich space. 24. Canonical Operator Consider a Kantorovich space E and an arbitrary nonempty set A. Denote by l∞ (A, E) the set of all order bounded mappings from A into E; i.e., f ∈ l∞ (A, E) if and only if f : A → E and the set {f (α) : α ∈ A} is order bounded in E. It is easy to verify that l∞ (A, E) becomes a Kantorovich space if endowed with the coordinatewise algebraic operations and order. The operator εA,E acting from l∞ (A, E) into E by the rule εA,E : f 7→ sup{f (α) : α ∈ A}
(f ∈ l∞ (A, E))
is called the canonical sublinear operator given A and E. We often write εA instead of εA,E when it is clear from the context what Kantorovich space is meant. The notation εn is used when the cardinality of A equals n and we call the operator εn finitely-generated. 25. Support Hull Consider a set A of linear operators acting from a vector space X into a Kantorovich space E. The set A is weakly order bounded if {αx : α ∈ A} is order bounded for every x ∈ X. Denote by hAix the mapping that assigns the element αx ∈ E to each α ∈ A, i.e. hAix : α 7→ αx. If A is weakly order bounded then hAix ∈ l∞ (A, E) for every fixed x ∈ X. Consequently, we obtain the linear operator hAi : X → l∞ (A, E) that acts as hAi : x 7→ hAix. Associate with A one more operator pA : x 7→ sup{αx : α ∈ A}
(x ∈ X).
The operator pA is sublinear. The support set ∂pA is denoted by cop(A) and referred to as the support hull of A. 26. Hahn–Banach in Disguise Theorem. If p is a sublinear operator with ∂p = cop(A) then P = εA ◦ hAi. Assume further that p1 : X → E is a sublinear operator and p2 : E → F is an increasing sublinear operator. Then ∂(p2 ◦ p1 ) = {T ◦ h∂p1 i : T ∈ L+ (l∞ (∂p1 , E), F ) ∧ T ◦ ∆∂p1 ∈ ∂p2 }. Moreover, if ∂p1 = cop(A1 ) and ∂p2 = cop(A2 ) then ∂(p2 ◦p1 ) = T ◦hA1 i : T ∈ L+ (l∞ (A1 , E), F ) ∧ ∃α ∈ ∂εA2 T ◦ ∆A1 = α ◦ hA2 i .
8
S. S. KUTATELADZE
27. Enter Boole Cohen’s final solution of the problem of the cardinality of the continuum within ZFC gave rise to the Boolean-valued models by Vopˇenka, Scott, and Solovay. Takeuti coined the term “Boolean-valued analysis” for applications of the new models to functional analysis [19]. Let B be a complete Boolean algebra. Given an ordinal α. put (B)
Vα(B) := {x : (∃β ∈ α) x : dom(x) → B & dom(x) ⊂ Vβ
}.
The Boolean-valued universe V(B) is V(B) :=
[
Vα(B) ,
α∈On
with On the class of all ordinals. Truth value [[ϕ]] ∈ B is assign to each formula ϕ of ZFC relativized to V(B) 28. Enter Descent Given ϕ, a formula of ZFC, and y, a subset VB ; put Aϕ := Aϕ(·, ϕ(x, y)}. The descent Aϕ↓ of a class Aϕ is
y)
:= {x :
Aϕ↓:= {t : t ∈ V(B) & [[ϕ(t, y)]] = 1}. If t ∈ Aϕ↓, then it is said that t satisfies ϕ(·, y) inside V(B) . The descent x↓ of an element x ∈ V(B) is defined by the rule x↓:= {t : t ∈ V(B) & [[t ∈ x]] = 1}, i.e. x↓= A·∈x ↓. The class x↓ is a set. Moreover, x↓⊂ mix(dom(x)), where mix is the symbol of the taking of the strong cyclic hull. If x is a nonempty set inside V(B) then (∃z ∈ x↓)[[(∃z ∈ x) ϕ(z)]] = [[ϕ(z)]]. 29. The Reals in Disguise There is an object R inside V(B) modeling R, i. e., [[R is the reals ]] = 1. Here R is the carrier of R, the reals inside V(B) . Implement the descent of structures from R to R↓ as follows: x + y = z ↔ [[x + y = z]] = 1; xy = z ↔ [[xy = z]] = 1; x ≤ y ↔ [[x ≤ y]] = 1; λx = y ↔ [[λ∧ x = y]] = 1 (x, y, z ∈ R↓, λ ∈ R). Gordon Theorem. The set R ↓ with descended structures is a universally complete Kantorovich space with base B(R↓) isomorphic to B.
CONVEXITY AND CONE-VEXING
9
30. Approximation Convexity of harpedonaptae was stable in the sense that no variation of stakes within the surrounding rope can ever spoil the convexity of the tract to be surveyed. Study of stability in abstract convexity is accomplished sometimes by introducing various epsilons in appropriate places. One of the earliest excrsions in this direction is connected with the classical Hyers–Ulam stability theorem for ε-convex functions [20]. Exact calculations with epsilons and sharp estimates are sometimes bulky and slightly mysterious. Some alternatives are suggested by actual infinities, which is illustrated with the conception of infinitesimal optimality. 31. Enter Epsilon and Monad Assume given a convex operator f : X → E ∪ +∞ and a point x in the effective domain dom(f ) := {x ∈ X : f (x) < +∞} of f . Given ε ≥ 0 in the positive cone E+ of E, by the ε-subdifferential of f at x we mean the set ∂ εf (x) := T ∈ L(X, E) : (∀x ∈ X)(T x − F x ≤ T x − f x + ε) , with L(X, E) standing as usual for the space of linear operators from X to E. Distinguish some downward-filtered subset E of E that is composed of positive elements. Assuming E and E standard, define the monad µ(E ) of E as µ(E ) := T {[0, ε] : ε ∈ ◦E }. The members of µ(E ) are positive infinitesimals with respect to E . As usual, ◦E denotes the external set of all standard members of E, the standard part of E . 32. Subdifferential Halo Assume that the monad µ(E ) is an external cone over ◦ R and, moreover, µ(E ) ∩ E = 0. In application, E is usually the filter of order-units of E. The relation of infinite proximity or infinite closeness between the members of E is introduced as follows:
◦
e1 ≈ e2 ↔ e1 − e2 ∈ µ(E ) ∧ e2 − e1 ∈ µ(E ). Now
\ Df (x) :=
[ ∂ε f (x) =
ε∈◦ E
∂ε f (x); ε∈µ(E )
the infinitesimal subdifferential of f at x. The elements of Df (x) are infinitesimal subgradients of f at x. 33. Exeunt Epsilon Theorem. Let f1 : X × Y → E ∪ +∞ and f2 : Y × Z → E ∪ +∞ be convex operators. Suppose that the convolution f2 M f1 is infinitesimally exact at some point (x, y, z); i.e., (f2 M f1 )(x, y) ≈ f1 (x, y) + f2 (y, z). If, moreover, the convex sets epi(f1 , Z) and epi(X, f2 ) are in general position then D(f2 M f1 )(x, y) = Df2 (y, z) ◦ Df1 (x, y). This talk bases on the recent book [21] which covers other relevant topics.
10
S. S. KUTATELADZE
34. Models Galore The essence of mathematics resides in freedom, and abstraction is the freedom of generalization. Freedom is the loftiest ideal and idea of man, but it is demanding, limited, and vexing. So is abstraction. So are its instances in convexity. Abstract convexity starts with repudiating the heritage of harpedonaptae, which is annoying and vexing but may turn out rewarding. Freedom of set theory empowered us with the Boolean valued models yielding various realizations of the continuum with idempotents galore. Many promising opportunities are open to modeling the diverse ways of reasoning and verification. Convexity is a topical illustration of the wisdom and strength of our ever fresh art and science of calculus. References [1] Heaves Th. (1956) The Thirteen Books of Euclid’s Elements. Vol. 1–3. New York: Dover Publications. [2] Ferrari G. R. F. (Ed.) (2000) Plato: The Republic. Berkeley : University of California (Translated by Tom Griffith). [3] Macaulay G. C. (Tr.) (1890) The History of Herodotus. London and New York: Macmillan. [4] Datta B. (1993) Ancient Hindu Geometry: The Science of the Sulba.; New Delhi: Cosmo Publishers. [5] Seidenberg A. (1978) “The origin of mathematics.” Archive for History of Exact Sciences. 18, pp. 301-342. [6] Kak S.C. (1997) Science in Ancient India. In: Sridhar S.R. and Mattoo N. K. (eds.)Ananya: A portrait of India, AIA: New York, 399–420 [7] Kutateladze S. S. and Rubinov A. M. (1972) Minkowski duality and its applications. Russian Math. Surveys, 27:3, 137–191. [8] Kutateladze S. S. and Rubinov A. M. (1976) Minkowski Duality and Its Applications. Novosibirsk: Nauka Publishers [in Russian]. [9] Fuchssteiner B. and Lusky W. (1981) Convex Cones. Amsterdam: North-Holland. [10] H¨ ormander L. (1994) Notions of Convexity. Boston: Birkh¨ auser. [11] Singer I. (1997) Abstract Convex Analysis. New York: John Wiley & Sons. [12] Pallaschke D. and Rolewicz S. (1998) Foundations of Mathematical Optimization, Convex Analysis Without Linearity. Dordrecht: Kluwer Academic Publishers. [13] Rubinov A. M. (2000) Abstract Convexity and Global Optimization. Dordrecht: Kluwer Academic Publishers. [14] Ioffe A. D. and Rubinov A. M. (2002) Abstract convexity and nonsmooth analysis. Global aspects. Adv. Math. Econom., 4, 1–23. [15] Fenchel W. (1953) Convex Cones, Sets, and Functions. Princeton: Princeton Univ. Press. [16] H¨ ormander L. (1955) Sur la fonction d’appui des ensembles convexes dans une espace lokalement convexe. Ark. Mat., 3:2, 180–186 [in French]. [17] Litvinov G. L., Maslov V. P., and Shpiz G. B. (2001) Idempotent functional analysis: an algebraic approach. Math. Notes, 69:5, 758–797. [18] Cohen G., Gaubert S., aand Quadrat J.-P. (2002) Duality and Separation Theorems in Idempotent Semimodules. Rapporte de recherche No. 4668, Le Chesnay CEDEX: INRIA Rocquetcourt. 26 p. [19] Kusraev A. G. and Kutateladze S. S. (2005) Introduction to Boolean Valued Analysis. Moscow: Nauka Publishers [in Russian]. [20] Dilworth S. J., Howard R., and Roberts J. W. (2006) A general theory of almost convex functions. Trans. Amer. Math. Soc., 358:8, 3413–3445. [21] Kusraev A. G. and Kutateladze S. S. (2007) Subdifferential Calculus: Theory and Applications. Moscow: Nauka Publishers [in Russian].
