Cap´ıtulo 1

Los conjuntos convexos y sus propiedades

TEMARIO Lecci´ on Lecci´ on Lecci´ on Lecci´ on Lecci´ on Lecci´ on

1.1 1.2 1.3 1.4 1.5 1.6

Los conjuntos convexos y sus propiedades. Proyecci´on m´etrica, soporte y separaci´on. Dualidad. Representaciones extremales, politopos. La funci´on soporte. La m´etrica de Hausdorff. El Teorema de Selecci´on de Blaschke.

a convexidad tiene una larga historia. Ya en el famoso “Los Elementos” de Euclides (≈300 L a.C.) aparecen varias contribuciones a esta materia, relativas principalmente a propiedades de los pol´ıgonos y poliedros. Sin embargo, fue Arqu´ımedes (287?–212 a.C.) el primero en dar una definici´ on precisa de lo que se entend´ıa por una curva o una superficie convexa (en su libro “Sobre la esfera y el cilindro”). Entre las diferentes propiedades obtenidas por Arqu´ımedes sobre convexidad, merecen especial menci´on los postulados y resultados referentes al centro de gravedad de conjuntos planos y su descripci´on de los 13 poliedros semiregulares, tambi´en conocidos como s´ olidos arquimedianos. Los s´olidos arquimedianos fueron re-descubiertos muy posteriormente por Kepler (1571-1630) en su libro “Harmonices mundi” (1619), demostrando que, efectivamente, s´olo pod´ıan existir 13. Respecto a resultados sobre el famoso problema isoperim´etrico, el origen del cual data aproximadamente del a˜ no 810 a.C., los debidos a Zenodorus (≈200 a.C.) para el caso de pol´ıgonos convexos parecen ser los m´as antiguos.

2

Los conjuntos convexos y sus propiedades

Adem´as de otras contribuciones espor´adicas, a finales del siglo XIX aparecieron diversos resultados de gran importancia en convexidad, gracias a matem´aticos como Brunn o Minkowski; sin embargo, el inter´es real por la Geometr´ıa Convexa es relativamente reciente, pues un primer estudio sistem´atico no lo encontramos hasta 1934, en el libro de Bonnesen y Fenchel “Theorie der konvexen K¨orper”. A lo largo de los a˜ nos 40 y 50 se descubrieron numerosas aplicaciones importantes de los conjuntos convexos, principalmente en el campo de la optimizaci´on geom´etrica, lo que acrecent´ o el inter´es de esta teor´ıa. Este primer cap´ıtulo de nuestro programa est´a dedicado a estudiar los conceptos y resultados fundamentales de la Teor´ıa de los Conjuntos Convexos, as´ı como las herramientas b´asicas que se utilizar´an en el posterior desarrollo de la materia.

1.1.

Los conjuntos convexos y sus propiedades. Sumario. Combinaciones lineal, af´ın, positiva y convexa. Conjunto convexo. Envoltura convexa, af´ın y positiva. El Teorema de Carath´eodory. La convexidad y las propiedades topol´ogicas. Cuerpo convexo. Teoremas de Radon y Helly.

ntes de definir propiamente lo que es un conjunto convexo, resulta conveniente recordar algunos A conceptos previos bien conocidos. As´ı por ejemplo: Definici´ on 1.1. Se dice que un vector x de Rn es una combinaci´on lineal de los vectores x1 , . . . , xk si existen λ1 , . . . , λk ∈ R adecuados tales que x = λ1 x1 + · · · + λk xk . Adem´ as: – Si los λi verifican λ1 + · · · + λk = 1, entonces se dice que x es una combinaci´on af´ın de los xi . – Si los λi verifican λi ≥ 0, i = 1, . . . , k, entonces x es una combinaci´on positiva de los xi . – Finalmente, si se verifican ambas condiciones a la vez sobre los n´ umeros λi , esto es, si λ1 + · · · + λk = 1

y

λi ≥ 0,

i = 1, . . . , k,

entonces se dice que x es una combinaci´on convexa de los xi . Definici´ on 1.2. Se dice que un conjunto K de Rn es convexo si, dados dos puntos cualesquiera de K, el segmento que los une est´ a totalmente contenido en el conjunto, es decir, si la combinaci´ on convexa (1 − λ)x + λy ∈ K para x, y ∈ K y 0 ≤ λ ≤ 1. Otro concepto interesante es el de cono convexo, que podemos definir de la siguiente forma. Definici´ on 1.3. Un cono (convexo) es un subconjunto A de Rn que es convexo, no vac´ıo y tal que si x est´ a en A, entonces λx tambi´en est´ a en A para todo λ ≥ 0. En definitiva, un subconjunto no vac´ıo A de Rn es un cono convexo si es cerrado para la suma y el producto por n´ umeros reales no negativos.

1.1 Los conjuntos convexos y sus propiedades.

3

Definici´ on 1.4. Dado un conjunto arbitrario A, se define la envoltura convexa de A, y se representa por conv A, como la intersecci´ on de todos los subconjuntos convexos de Rn que contienen a A. An´ alogamente se definen la envoltura af´ın y la envoltura positiva de A, y se representan por aff A y pos A, respectivamente, como la intersecci´ on de todos los subespacios afines, en el primer caso, o de todos los conos convexos, en el segundo, de Rn que contienen a A. En definitiva, conv A (respectivamente, aff A o pos A) no es otra cosa que el menor conjunto convexo (respectivamente, subespacio af´ın o cono positivo) que contiene a A. Adem´as, dado un subconjunto cualquiera A de Rn , su envoltura convexa no es otra cosa que el conjunto de todas las combinaciones convexas de una cantidad finita cualquiera de elementos de A. Resultados an´alogos se demuestran para las envolturas af´ın y convexa de un conjunto A; por lo tanto, las envolturas af´ın y positiva de un conjunto A coinciden con los conjuntos de todas las combinaciones afines y positivas, respectivamente, de cualquier cantidad finita de elementos de A. Uno de los resultados fundamentales sobre la generaci´on de las envolturas convexas es el Teorema de Carath´eodory (1907). Ya sabemos que un punto x ∈ conv A es una combinaci´on convexa de una cantidad finita de elementos de A; sin embargo, este resultado no establece restricci´on alguna sobre el n´ umero de puntos de A necesarios para construir dicha combinaci´on. El Teorema de Carath´eodory nos dice, precisamente, cu´al es el n´ umero m´aximo de puntos requeridos. Teorema 1.5 (Carath´ eodory, 1907). Si A es un subconjunto no vac´ıo de Rn , entonces todo x ∈ conv A puede expresarse como una combinaci´ on convexa de, a lo sumo, n + 1 puntos de A. Especial inter´es presentan los conjuntos obtenidos como la envoltura convexa de puntos: Definici´ on 1.6. La envoltura convexa de un n´ umero finito de puntos se denomina politopo (convexo), en general, o pol´ıgono (convexo), en el caso del plano eucl´ıdeo. En particular, un k-s´ımplice es a la envoltura convexa de k + 1 puntos af´ınmente independientes. Es sencillo demostrar que todo punto de un k-s´ımplice tiene una u ´nica representaci´on como combinaci´on convexa de sus v´ertices. Adem´as, el Teorema de Carath´eodory establece entonces que la envoltura convexa de un conjunto A es la uni´on de todos los s´ımplices con v´ertices en A. Definici´ on 1.7. La dimensi´on de un conjunto cualquiera A de Rn no es m´ as que la dimensi´ on del menor subespacio af´ın que lo contiene, y se denota por dim A. Representaremos por relint A (respectivamente relbd A) el interior relativo de A, es decir, el interior (frontera) del conjunto A relativo al menor subespacio af´ın que lo contiene. Observaci´ on 1. Dado un conjunto convexo K, si x ∈ int K e y ∈ cl K, entonces el segmento semiabierto [x, y) ⊂ int K. Esto permite demostrar, entre otros, los siguientes resultados: – Si K es un conjunto convexo de Rn , entonces int K y cl K son tambi´en convexos. – Si K = conv{x1 , . . . , xk+1 } es un s´ımplice k-dimensional, entonces relint K 6= ∅.

4

Los conjuntos convexos y sus propiedades

– Si K es un conjunto convexo y no vac´ıo de Rn , entonces su interior relativo relint K 6= ∅. – Si K es un conjunto convexo de Rn , entonces relint K = relint cl K y cl K = cl relint K. – Si A es un conjunto abierto de Rn , entonces conv A tambi´en es abierto. – La envoltura convexa de un conjunto compacto es compacta. A partir de ahora, cuando se hable de un cuerpo convexo nos estaremos refiriendo a un conjunto convexo y compacto de Rn no vac´ıo. Representaremos por Kn el conjunto de todos los cuerpos convexos del espacio eucl´ıdeo n-dimensional.

1.1.1.

Teoremas tipo Helly.

l Teorema de Carath´eodory establec´ıa cu´al es el n´ umero m´aximo de puntos de un conjunto A E necesarios para construir, mediante una combinaci´on convexa, un punto cualquiera de conv A. Otro resultado igualmente sencillo e importante sobre envolturas convexas es el siguiente: Teorema 1.8 (Radon, 1921). Todo subconjunto de puntos af´ınmente dependientes de Rn (en particular, cualquier conjunto con, al menos, n + 2 puntos) puede expresarse como la uni´ on de dos conjuntos disjuntos cuyas envolturas convexas tienen un punto en com´ un. A partir del Teorema de Radon puede deducirse f´acilmente el conocido Teorema de Helly, un resultado fundamental y t´ıpico de la Geometr´ıa Combinatoria de conjuntos convexos. La primera demostraci´on de este teorema fue publicada por Radon en 1921, a quien Helly hab´ıa enviado su enunciado ocho a˜ nos antes. En 1923, Helly da a conocer su propia demostraci´on del resultado. Teorema 1.9 (Helly, 1921–23). Sean K1 , . . . , Kr conjuntos convexos del espacio eucl´ıdeo Rn . Si cualquier colecci´ on de n + 1 de tales subconjuntos tienen un punto en com´ un, entonces todos los Ki tienen un punto en com´ un. Este teorema es el m´as representativo de toda una clase de resultados conocidos como los Teoremas de Tipo Helly, los cuales responden a la siguiente formulaci´on general: Sea F una familia de conjuntos y sea r un entero positivo. Si r conjuntos cualesquiera de F satisfacen la propiedad P, entonces toda la familia F verifica la propiedad Q.

1.2.

Proyecci´ on m´ etrica, soporte y separaci´ on. Sumario. La proyecci´on m´etrica. Los hiperplanos soporte. Conjuntos separados y fuertemente separados. Teoremas de separaci´on.

n lo que sigue, vamos a representar por B (x, ρ) la bola eucl´ıdea cerrada n-dimensional con E centro x y radio ρ. Cuando el centro sea el origen de coordenadas, escribiremos simplemente B (ρ). n

n

Finalmente, Bn ser´a la bola unidad centrada en el origen.

´ n me ´trica, soporte y separacio ´ n. 1.2 Proyeccio

5

 Un hiperplano (af´ın) H de Rn puede expresarse de la forma H = x ∈ Rn : hx, ui = c , donde u 6= 0 (unitario) es el vector normal a H y c es un n´ umero real fijo. Representamos epor H + y H − los dos semiespacios cerrados determinados por H, esto es,  H + = x ∈ Rn : hx, ui ≥ c

y

 H − = x ∈ Rn : hx, ui ≤ c .

Consideremos un conjunto convexo y cerrado K de Rn , no vac´ıo. Entonces, para cada x ∈ Rn , existe un u ´nico punto p(K, x) ∈ K verificando x − p(K, x) ≤ |x − y| para todo y de K. Esta propiedad permite considerar una aplicaci´on bien definida, p(K, · ), como se define a continuaci´ on. Definici´ on 1.10. La aplicaci´ on p(K, · ) : Rn −→ K que a cada x de Rn le asigna el u ´nico punto n p(K, x) ∈ R que verifica x − p(K, x) ≤ |x − y|, para todo y ∈ K, se denomina la proyecci´on m´etrica o aplicaci´on punto m´as pr´oximo de K. Claramente, se tiene que x − p(K, x) = d(K, x) no es m´as que la distancia (usual) de x al conjunto K. Vamos a representar entonces por u(K, x) el vector unitario que marca la direcci´on desde el punto m´as pr´oximo p(K, x) a x, esto es, u(K, x) =

x − p(K, x) . d(K, x)

Entre otras propiedades, destacamos las siguientes:  Lema 1.11. Sean x ∈ Rn \ K e y ∈ R(K, x) := p(K, x) + λu(K, x) : λ ≥ 0 (el rayo que pasa por x con punto final p(K, x)). Entonces, p(K, x) = p(K, y). Teorema 1.12. La proyecci´ on m´etrica es una aplicaci´ on contractiva, esto es, verifica que p(K, x) − p(K, y) ≤ |x − y|, para cualesquiera x, y ∈ Rn . Lema 1.13. Sea Bn una bola que contiene a K en su interior. Entonces, p(K, bd Bn ) = bd K. Adem´as, la existencia de una u ´nica proyecci´on m´etrica es caracter´ıstica de los conjuntos convexos, lo que nos ofrece una primera caracterizaci´on de este tipo de figuras: Teorema 1.14 (Bunt, Motzkin, 1934–1935). Un conjunto K de Rn es convexo si, y s´ olo si, n para cada x de R existe un u ´nico punto m´ as pr´ oximo en K. Dado un conjunto convexo K de Rn , se dice que un hiperplano H soporta K en un punto x ∈ K si x ∈ K ∩ H y K est´a contenido en uno de los dos semiespacios H + o H − que dicho hiperplano determina. Esta idea permite definir el concepto fundamental de hiperplano soporte a un conjunto.

6

Los conjuntos convexos y sus propiedades

Definici´ on 1.15. Dado un conjunto convexo K de Rn , se dice que H es un hiperplano soporte a K si H soporta K en alg´ un punto x, el cual ser´ a, necesariamente, un punto de su frontera. Adem´as, si el hiperplano H soporta K y K ⊂ H − (respectivamente, K ⊂ H + ), entonces se dice que H − (respectivamente, H + ) es un semiespacio soporte a K. Este nuevo concepto y el de proyecci´on m´etrica se relacionan del siguiente modo: Lema 1.16. Sea K un conjunto convexo y cerrado de Rn no vac´ıo, y sea x un punto que no est´ a en K. Entonces, el hiperplano H que pasa por el punto m´ as pr´ oximo p(K, x), ortogonal al vector u(K, x), soporta K. Por otro lado, la existencia de hiperplanos soporte permite establecer una nueva caracterizaci´ on de los conjuntos convexos (cerrados con interior no vac´ıo). Teorema 1.17. Si K es un conjunto convexo y cerrado de Rn , entonces por cada punto frontera de K existe un hiperplano soporte a K. Adem´ as, si K es acotado, para cada vector no nulo u existe un hiperplano soporte a K con vector normal exterior u. Teorema 1.18. Si K es un conjunto cerrado de Rn con interior no vac´ıo, y tal que por cada uno de sus puntos frontera existe un hiperplano soporte a K, entonces K es convexo. Estudiamos finalmente el problema de “separar” conjuntos convexos por medio de hiperplanos. Definici´ on 1.19. Sean A y B dos subconjuntos de Rn . Se dice que un hiperplano H separa A y B si A ⊂ H − y B ⊂ H + , o viceversa. H se denomina entonces hiperplano de separaci´on de A y B. Adem´ as, se dice que esta separaci´ on es propia si A y B no est´ an ambos en H. Los conjuntos A y B est´ an estrictamente separados por H si A ⊂ int H − y B ⊂ int H + , o viceversa.  Se dice que A y B est´ an fuertemente separados por H = x ∈ Rn : hx, ui = c si existe ε > 0 de   forma que Hc−ε = x ∈ Rn : hx, ui = c − ε y Hc+ε = x ∈ Rn : hx, ui = c + ε separan A y B. Los resultados que establecen condiciones que aseguran si dos conjuntos cualesquiera pueden o no separarse se conocen como teoremas de separaci´ on. Comencemos considerando el caso m´ as sencillo: el de un conjunto y un punto. Teorema 1.20. Si K es un conjunto convexo y x ∈ Rn \K, entonces K y x pueden separarse. Adem´ as, si K es cerrado, entonces K y x pueden separarse fuertemente. Corolario 1.21. Todo conjunto convexo y cerrado K de Rn no vac´ıo es la intersecci´ on de sus semiespacios soporte. El teorema anterior tiene una gran importancia, ya que la separaci´on de pares de conjuntos puede reducirse al estudio de la separaci´on de un conjunto y un punto: Lema 1.22. Sean A, B ⊂ Rn no vac´ıos. Entonces A y B pueden separarse (separarse fuertemente) si, y s´ olo si, A − B y el origen de coordenadas 0 pueden separarse (separarse fuertemente).

1.3 Dualidad.

7

Las propiedades – si K y K 0 son convexos, entonces K − K 0 es convexo, – si K es compacto y K 0 es cerrado, K − K 0 es cerrado, – 0 6∈ K − K 0 si y s´olo si K ∩ K 0 = ∅, junto con el Teorema 1.20 y el Lema 1.22, permiten deducir el siguiente resultado: Teorema 1.23. Si K, K 0 ⊂ Rn son conjuntos convexos no vac´ıos tales que K ∩ K 0 = ∅, entonces K y K 0 pueden separarse. Adem´ as, si K es compacto y K 0 es cerrado, entonces K y K 0 pueden separarse fuertemente. Existen muchas extensiones y reformulaciones de este teorema que son de particular inter´es. Por ejemplo, si se suprime la condici´on de convexidad en los conjuntos obtenemos el siguiente resultado. Teorema 1.24. Sean A y B dos subconjuntos compactos no vac´ıos de Rn . Entonces, existe un hiperplano H que separa fuertemente A y B si, y s´ olo si, conv A ∩ conv B = ∅. Por otro lado, existen conjuntos convexos que se pueden separar, incluso si no son disjuntos. La condici´on precisa para que esto sea posible se da en el siguiente teorema. Teorema 1.25. Sean K y K 0 conjuntos convexos de Rn no vac´ıos. Entonces K y K 0 pueden separarse propiamente si, y s´ olo si, relint K ∩ relint K 0 = ∅.

1.3.

Dualidad. Sumario. Conjunto polar o dual. El conjunto doble-polar.

n muchas ramas de las matem´aticas aparece el t´ermino dualidad, en general, referido a dos E ideas o teor´ıas similares que est´an relacionadas entre s´ı, usualmente de forma inversa. En nuestro caso, asociados a los conjuntos convexos, existen objetos duales de la misma clase. Esta dualidad nos permite, por ejemplo, trasladar ciertos resultados sobre puntos frontera de conjuntos convexos a resultados sobre hiperplanos soporte y viceversa. Pero existen adem´as otras muchas aplicaciones. Definici´ on 1.26. Sea A un subconjunto cualquiera de Rn con interior no vac´ıo. Se define el conjunto polar o dual de A como n o A∗ = x ∈ Rn : hx, yi ≤ 1 para todo y ∈ A . Es sencillo comprobar que el conjunto polar de un punto y 6= 0 es un semiespacio, el determinado  por el hiperplano x ∈ Rn : hx, yi = 1 que contiene a 0 en su interior; que el polar del propio origen de coordenadas es todo el espacio Rn ; y que para la bola eucl´ıdea centrada en el origen se tiene que Bn (r)∗ = Bn (1/r). Es m´as, se puede demostrar que A∗ = A si, y s´olo si, A = Bn (1).

8

Los conjuntos convexos y sus propiedades

Una propiedad muy importante del conjunto polar es que A∗ siempre es cerrado y convexo (para cualquier subconjunto A ⊂ Rn ), y que 0 ∈ int A∗ . Adem´as, para subconjuntos cualesquiera A, B ⊂ Rn , se verifica que:  ∗ i) A ∪ B = A∗ ∩ B ∗ (la igualdad sigue siendo cierta para uniones numerables). ii) Si A ⊂ B, entonces B ∗ ⊂ A∗ . iii) Si λ > 0, entonces (λA)∗ = (1/λ)A∗ . Teorema 1.27. Sea A un subconjunto cualquiera de Rn . Entonces 
 A∗∗ = cl conv A ∪ {0} . En particular, si A es convexo, cerrado, y contiene el origen en su interior, entonces A∗∗ = A. Lema 1.28. Dados dos cuerpos convexos K1 , K2 ∈ K0n , se verifica la relaci´ on (K1 ∩ K2 )∗ = conv(K1∗ ∪ K2∗ ). Adem´ as, si K1 ∪ K2 es convexo, entonces K1∗ ∪ K2∗ es tambi´en convexo, y por tanto (K1 ∩ K2 )∗ = K1∗ ∪ K2∗ .

1.4.

Representaciones extremales. Politopos. Sumario. Punto extremo. Teorema de Krein-Milman. Punto expuesto. Teorema de Straszewicz. Caras. Conos soporte y normal. Politopos. Paralelotopos, zonotopos, s´ımplices y crosspolitopos. Teorema Principal de los Politopos. F´ormula de Euler.

Uno de los prop´ositos de esta lecci´on es dar respuesta a las siguientes preguntas: Dado un conjunto convexo K, ¿es siempre posible expresarlo como la envoltura convexa de alg´ un subconjunto propio S de K? Y a´ un m´ as: ¿cu´ al es el subconjunto m´ as peque˜ no S ⊂ K tal que conv S = K? Si K est´a formado por m´as de un punto, la respuesta a la primera cuesti´on es afirmativa: t´omese S = K\{x}, donde x ∈ relint K. Adem´as, si K es compacto, podemos considerar S = bd K. La siguiente pregunta surge entonces de forma natural: ¿es la frontera de un cuerpo convexo el subconjunto m´as peque˜ no que verifica esta propiedad? Basta pensar en un tri´angulo para darnos cuenta de que la respuesta es negativa. Nos preguntamos ahora: ¿existe siempre el menor subconjunto S de K tal que conv S = K? Y si existe, ¿puede caracterizarse de alguna manera? Lema 1.29. Sea K un conjunto convexo cerrado de Rn . Entonces K 6= conv relbd K si, y s´ olo si, K es un k-plano o un semiespacio (k-dimensional).

1.4 Representaciones extremales. Politopos.

9

Por tanto, a partir de ahora supondremos que el conjunto convexo K no es ninguna de estas dos figuras. En particular, si consideramos conjuntos convexos compactos, entonces s´ı es claro que K = conv relbd K. Pero en general, no todos los puntos de la frontera relativa son necesarios. Para responder a las preguntas que nos estamos planteando necesitamos la siguiente definici´ on. Definici´ on 1.30. Sea K un conjunto convexo. Un punto x de K se dice que es un punto extremo si no existe ning´ un segmento de recta (no degenerado) en K que contenga a x en su interior relativo; o equivalentemente, si x no puede escribirse como x = (1 − λ)y + λz, con y, z ∈ K y 0 < λ < 1. El conjunto de todos los puntos extremos de un conjunto convexo K se representa por ext K, y suele llamarse el perfil de K. Un punto x de un conjunto convexo K es extremo si, y s´olo si, el conjunto K \ {x} es convexo. Luego cualquier subconjunto S de K para el cual conv S = K contiene el perfil de K. Si tenemos tambi´en en cuenta los conjuntos convexos abiertos o los no acotados, entonces el menor subconjunto S ⊂ K cuya envoltura convexa es K puede contener propiamente a ext K. Sin embargo, si nos restringimos a la familia de los cuerpos convexos, la compacidad nos va a asegurar, necesariamente, la existencia de alg´ un punto extremo, y la respuesta a la cuesti´on que nos plante´abamos al comienzo de la lecci´on la encontramos en el siguiente resultado: Teorema 1.31 (Minkowski, Krein-Milman, 1911–40). Todo cuerpo convexo K de Rn es la envoltura convexa de sus puntos extremos. Y adem´as, el conjunto de los puntos extremos no puede reemplazarse por otro conjunto menor, ya que x ∈ K es un punto extremo de K si, y s´olo si, K \ {x} es convexo. Este teorema fue probado originalmente por Minkowski en 1911 para el espacio eucl´ıdeo finitodimensional Rn . De particular importancia es su extensi´on a espacios infinito-dimensionales, resultado que fue demostrado en 1940 por Krein y Milman, por lo que a partir de entonces se bautiz´ o, incluido el caso de Rn , como Teorema de Krein-Milman: todo subconjunto convexo y compacto de un espacio localmente convexo es la envoltura convexa y cerrada de sus puntos extremos. Es interesante comentar que, para conjuntos que no son compactos no existe caracterizaci´ on posible; bien porque K no sea acotado, bien porque K no sea cerrado, puede ocurrir cualquier cosa, tanto que conv ext K = K, como que conv ext K 6= K. La noci´on de punto extremo de un conjunto convexo K involucra combinaciones convexas de puntos en K, y en consecuencia, est´a relacionada con una descripci´on “intr´ınseca” del conjunto. Si miramos ahora un conjunto convexo desde “fuera”, nos vemos dirigidos hacia una clase diferente, aunque estrechamente relacionada, de puntos especiales de la frontera de K. Definici´ on 1.32. Un punto x de un conjunto convexo K es un punto expuesto de K si existe un hiperplano H soporte a K tal que H ∩ K = {x}. El conjunto de los puntos expuestos de K se representa por exp K.

10

Los conjuntos convexos y sus propiedades

Claramente se tiene que exp K ⊂ ext K, pero incluso para cuerpos convexos del plano eucl´ıdeo, esta inclusi´on es, en general, estricta. Sin embargo, cada punto extremo de un cuerpo convexo (realmente, basta con suponerlo cerrado) es un l´ımite de puntos expuestos: Teorema 1.33 (Straszewicz, 1935). Si K es un cuerpo convexo del espacio eucl´ıdeo Rn , entonces ext K ⊂ cl exp K, y en consecuencia, K = cl(conv exp K).

1.4.1.

La estructura facial de un conjunto convexo.

l estudio de la frontera de un conjunto convexo resulta de gran importancia, pues determinaE dos puntos (o estructuras) de la frontera “capturan” una gran cantidad de informaci´on sobre el propio conjunto (tanto en dimensi´on finita como infinita). Sin duda alguna, todos estamos familiarizados con el t´ermino cara cuando ´este se aplica a los poliedros convexos. En la presente lecci´ on vamos a introducir el concepto de cara para conjuntos convexos (cerrados) arbitrarios, lo que nos permitir´a describir la estructura de la frontera relativa de un conjunto convexo. Definici´ on 1.34. Una cara de un conjunto convexo cerrado K de Rn es un subconjunto convexo F de K de forma que, si λx + (1 − λ)y ∈ F , donde x, y ∈ K y 0 < λ < 1, entonces x, y ∈ F . Se considera que tanto el conjunto vac´ıo ∅ como el propio conjunto K son caras de K, denominadas caras impropias de K; todas las dem´as caras se dicen propias. Adem´as, para hacer referencia a la dimensi´on de las caras se hablar´a de i-caras del conjunto. En lo sucesivo, representaremos por F(K) el conjunto de todas las caras del conjunto K, y por Fi (K) el conjunto de todas las caras i-dimensionales de K. Las siguientes propiedades son de sencilla demostraci´on: Proposici´ on 1.35. Sea K un conjunto convexo cerrado de Rn . i) Las 0-caras son los puntos extremos del conjunto. ii) Las caras de un conjunto convexo cerrado K son cerradas. iii) Si F 6= K es una cara de K, entonces F ∩ relint K = ∅. iv) En particular, F ⊂ relbd K y dim F < n. v) La intersecci´ on de cualquier colecci´ on no vac´ıa de caras de K es una cara de K. vi) Si F es una cara de K y G es una cara de F , entonces G tambi´en es una cara de K. vii) Si F1 , F2 ∈ F(K) son dos caras distintas de K, entonces relint F1 ∩relint F2 = ∅. Esto permite  deducir adem´ as que el sistema relint F : F ∈ F(K) es una descomposici´ on disjunta de K. Si H es un hiperplano soporte al conjunto K, entonces H ∩ K es una cara de K. Esto nos permite establecer la siguiente definici´on: Definici´ on 1.36. La intersecci´ on de un conjunto convexo cerrado K de Rn con uno de sus hiperplanos soporte recibe el nombre de cara expuesta de K (o i-cara expuesta de K).

1.4 Representaciones extremales. Politopos.

11

Obs´ervese que una cara expuesta G de una cara expuesta F del conjunto K no tiene por qu´e ser, necesariamente, una cara expuesta de K. Definici´ on 1.37. Sean K ∈ Kn y x ∈ K. El cono soporte de K en x es el conjunto  S(K, x) := cl λ(y − x) : y ∈ K, λ > 0 . Se define el cono normal de K en x como  N (K, x) := u ∈ Rn \{0} : x ∈ H(K, u) ∪ {0}. Si x ∈ K ∩ H(K, u), entonces se dice que u es un vector normal exterior a K en x. Por lo tanto, N (K, x) no es otra cosa que el conjunto de todos los vectores normales exteriores a K en x junto con el vector nulo. Claramente, N (K, x) es un cono convexo cerrado, y adem´as N (K, x) = S(K, x)∗ . El siguiente resultado describe el comportamiento de los conos soporte y normal respecto a la suma y la intersecci´on de conjuntos. Teorema 1.38. Sean K y L dos cuerpos convexos de Rn . i) Si x ∈ K e y ∈ L, S(K + L, x + y) = S(K, x) + S(L, y), N (K + L, x + y) = N (K, x) ∩ N (L, y). ii) Si x ∈ K ∩ L y relint K ∩ relint L 6= ∅, S(K ∩ L, x) = S(K, x) ∩ S(L, x), N (K ∩ L, x) = N (K, x) + N (L, x).

1.4.2.

Los politopos.

os poliedros (politopos convexos tridimensionales), especialmente los regulares, han fascinado a L la humanidad desde la antig¨ uedad. La construcci´on de los cinco s´olidos regulares en R (tetraedro, 3

cubo, octaedro, dodecaedro e icosaedro) en el “Libro XIII”, fue uno de los puntos m´as relevantes del famoso “Los Elementos” de Euclides (∼325-265 A.C.). Estos poliedros reciben el nombre de s´ olidos plat´ onicos, debido a que Plat´on (∼427-347 A.C.) hace menci´on expresa de ellos en el “Timeo”. La primera demostraci´on conocida del hecho de que s´ olo existen 5 poliedros regulares en R3 se remonta a los pitag´oricos (Pit´agoras, ∼580-500 A.C.). Como ya sabemos, se define un politopo como la envoltura convexa de un conjunto finito (posiblemente vac´ıo) de puntos en Rn . Adem´as de los famosos s´olidos plat´onicos, algunos ejemplos sencillos de politopos son los siguientes: i) Los paralelotopos: politopos generados mediante la suma de un n´ umero finito de vectores n linealmente independientes de R . Entre ellos, los m´as sencillos son los cubos: un cubo n-dimensional no es m´as que el producto cartesiano [−1, 1]n .

12

Los conjuntos convexos y sus propiedades

ii) Los zonotopos: suma vectorial de un n´ umero finito de segmentos en Rn . iii) Los k-s´ımplices: envoltura convexa de k + 1 puntos af´ınmente independientes. iv) Los crosspolitopos: un crosspolitopo k-dimensional es la envoltura convexa de k segmentos linealmente independientes en Rn cuyos puntos medios coinciden. Tal crosspolitopo se dice regular si todos los segmentos tienen la misma longitud y son adem´as mutuamente ortogonales. Los v´ertices de un politopo P = conv{x1 , . . . , xk } son los puntos extremos de P , y coinciden a S su vez con los puntos x1 , . . . , xk si, y s´olo si, para cada i = 1, . . . , k, xi 6∈ conv j6=i xj . Los politopos son los cuerpos convexos que tienen una cantidad finita de puntos extremos. Otras propiedades de los politopos son las siguientes: – Si P y Q son dos politopos en Rn y α ∈ R, entonces P + Q y αP son politopos. – Si H es un hiperplano soporte de P = conv{x1 , . . . , xk }, entonces H ∩ P es un politopo, pues
H ∩ P = conv H ∩ {x1 , . . . , xk } . – Es innecesaria la distinci´on entre caras y caras expuestas, pues toda cara propia de un politopo P es la intersecci´on de P con alg´ un hiperplano soporte. En particular, cada punto extremo de un politopo es un punto expuesto. Un politopo se ha definido como la envoltura convexa de un n´ umero finito de puntos. De manera alternativa, se puede ver como la intersecci´on de un n´ umero finito de semiespacios: Teorema 1.39 (Teorema Principal de los Politopos). Todo politopo es la intersecci´ on de una cantidad finita de semiespacios cerrados. Adem´ as, toda intersecci´ on acotada de una cantidad finita de semiespacios cerrados es un politopo. Lema 1.40. El cuerpo polar de un politopo es de nuevo un politopo. Si consideramos los cinco s´olidos plat´onicos, se tiene que el cubo y el octaedro son politopos duales, que el dodecaedro y el icosaedro son tambi´en polares y que el tetraedro es dual de s´ı mismo. En 1752, Euler descubri´o que, para los politopos 3-dimensionales, se verificaba la hoy conocida f´ormula f − e + v = 2, donde f representa el n´ umero de caras, e el n´ umero de aristas y v el n´ umero de v´ertices del politopo. El caso general fue demostrado por Poincar´e en 1899, por lo que dicha relaci´on se conoce a menudo con el nombre de f´ ormula de Euler-Poincar´e. Vamos a representar por fr (P ) el n´ umero de r-caras que presenta un n-politopo P de Rn para r = −1, 0, 1, . . . , n, donde f−1 (P ) = fn (P ) = 1. De forma general, si r < −1 ´o r > n se considera que fr (P ) = 0. Teorema 1.41 (La f´ ormula de Euler-Poincar´ e, 1752–1899). Sea P un m-politopo no vac´ıo n en R . Entonces m−1 X (−1)r fr (P ) = 1 − (−1)m . r=0

´ n soporte. 1.5 La funcio

1.5.

13

La funci´ on soporte. Sumario. Funci´on soporte de un conjunto convexo. Hiperplano y semiespacio soportes. Anchura de un cuerpo convexo en una direcci´on. Anchura m´ınima y di´ametro. Anchura media. Funci´on gauge. Funci´on radial.

unque las funciones convexas aparecen en numerosos contextos y aplicaciones, existen algunas A de particular inter´es por su estrecha relaci´on con la geometr´ıa de los conjuntos convexos. Una de ellas es la denominada funci´ on soporte. Dado que un conjunto convexo cerrado es la intersecci´ on de sus semiespacios soporte, dicho conjunto puede describirse convenientemente especificando la posici´on de sus hiperplanos soporte, dados sus vectores normales exteriores. Esta descripci´on se lleva a cabo por medio de la funci´on soporte. Definici´ on 1.42. Si K es un conjunto convexo cerrado de Rn no vac´ıo, se define la funci´on soporte h(K, · ) = hK de K como  h(K, u) = sup hx, ui : x ∈ K , para cada u ∈ Rn . Adem´as, si u ∈ dom hK \{0}, representamos por H(K, u) y H − (K, u) los conjuntos  H(K, u) = x ∈ Rn : hx, ui = h(K, u)

y

 H − (K, u) = x ∈ Rn : hx, ui ≤ h(K, u) ,

denominados, respectivamente, el hiperplano soporte y el semiespacio soporte del conjunto K con vector normal exterior u. Obs´ervese que estas definiciones de hiperplano y semiespacio soportes “extienden” las ya estudiadas en la Lecci´on 1.2. En definitiva, el hecho de que para un conjunto convexo compacto K, el hiperplano de ecuaci´on n o H(K, u) = x ∈ Rn : hx, ui = h(K, u) soporte a K en el punto m´as pr´oximo p(K, x), justifica el nombre de funci´on soporte para h(K, ·). Observaci´ on 2. Si u ∈ Sn−1 ∩dom h(K, ·), entonces h(K, u) es la distancia con signo del hiperplano soporte a K determinado por u, H(K, u), al origen de coordenadas; la distancia ser´ a negativa si, y s´ olo si, el vector u apunta hacia el interior del semiespacio abierto que contiene el origen. Proposici´ on 1.43. Sea K un conjunto convexo cerrado de Rn no vac´ıo. Entonces: i) El dominio de h(K, · ) es un cono convexo con v´ertice en el origen. ii) h(K, · ) = hz, · i si, y s´ olo si, K = {z}. iii) h(K + t, u) = h(K, u) + ht, ui para todo t ∈ Rn . iv) h(K, λu) = λh(K, u) si λ ≥ 0 y h(K, u + v) ≤ h(K, u) + h(K, v); por tanto, la funci´ on soporte es una funci´ on convexa.

14

Los conjuntos convexos y sus propiedades

v) h(K, · ) ≤ h(L, · ) si, y s´ olo si, K ⊂ L. vi) Si representamos por K| E la proyecci´ on ortogonal del conjunto K sobre un subespacio vecn torial E de R , se tiene que h(K| E, u) = h(K, u) para todo u ∈ E. vii) h(λK, · ) = λh(K, · ) para todo λ ≥ 0, y adem´ as h(−K, u) = h(K, −u). Adem´as, si K es un conjunto convexo cerrado no vac´ıo de Rn y h(K, · ) es su funci´on soporte, entonces se tiene que n o o \ n K = x ∈ Rn : hx, ui ≤ h(K, u) para todo u ∈ dom hK = x ∈ Rn : hx, ui ≤ h(K, u) . u∈dom hK

Obs´ervese que, si K es un cuerpo convexo, el supremo en la definici´on de h(K, u) se alcanza y es un valor finito para cada u, siendo entonces h(K, · ) una funci´on sublineal. Y rec´ıprocamente: se pueden caracterizar los cuerpos convexos por medio de sus funciones soporte, en el sentido que precisamos a continuaci´on. Teorema 1.44. Si f : Rn −→ R es una funci´ on sublineal, entonces existe un u ´nico cuerpo convexo n K en R cuya funci´ on soporte es f . Una propiedad fundamental de la funci´on soporte es que ´esta es aditiva en su primer argumento respecto a la suma vectorial de conjuntos: si K y L son dos cuerpos convexos de Rn , entonces h(K + L, · ) = h(K, · ) + h(L, · ). En general, una funci´on f definida sobre Kn se dice Minkowski-aditiva o aditiva en el sentido de Minkowski si verifica, precisamente, que f (K + L) = f (K) + f (L). Una primera consecuencia es que la igualdad K +M = L+M para los cuerpos convexos implica forzosamente que K = L, de donde se deduce que la familia de los cuerpos convexos con la llamada suma de Minkowski es un semigrupo conmutativo con la ley de la cancelaci´on. Definici´ on 1.45. Sea K ∈ Kn . Se define la anchura de K en la direcci´on u como ω(K, u) = h(K, u) + h(K, −u),

u ∈ Sn−1 .

Es decir, ω(K, u) es la distancia entre los dos hiperplanos soporte a K ortogonales a la direcci´ on n−1 dada u. Obs´ervese que, para cada u ∈ S , la anchura de K en la direcci´on u es ω(K, u) = h(K, u) + h(K, −u) = h(K, u) + h(−K, u) = h(K − K, u), es decir, es la funci´on soporte del llamado cuerpo diferencia DK = K − K. Definici´ on 1.46. El m´ınimo de todos los valores ω(K, u) cuando u var´ıa en todas las direcciones  posibles se denomina la anchura m´ınima de K, esto es, ω(K) = m´ın ω(K, u) : u ∈ Sn−1 . An´ alogamente, se define el di´ametro de K como el m´ aximo de los valores ω(K, u) cuando u var´ıa  en todas las direcciones posibles, esto es, D(K) = m´ax ω(K, u) : u ∈ Sn−1 .

´ n soporte. 1.5 La funcio

15

Obviamente, di´ametro y anchura (m´ınima) no son funciones Minkowski-aditivas, pues s´olo se tienen las desigualdades D(K + L) ≤ D(K) + D(L)

y

ω(K + L) ≥ ω(K) + ω(L).

Otra magnitud de especial relevancia es la llamada anchura media, b(K), definida como el valor medio de la funci´on anchura sobre Sn−1 , es decir, Z 2 h(K, u) du. b(K) = nvol(Bn ) Sn−1 Al contrario de lo que ocurr´ıa con la anchura m´ınima y el di´ametro, la anchura media b(K) es una funci´on Minkowski-aditiva. Adem´as de la funci´on soporte, existen otras funciones que pueden utilizarse para describir un cuerpo convexo anal´ıticamente. Definici´ on 1.47. Sea K un cuerpo convexo de Rn con 0 ∈ int K. Se define la funci´on gauge o funci´on distancia de Minkowski de K como la funci´ on g(K, · ) : Rn −→ R dada por  g(K, x) = m´ın λ ≥ 0 : x ∈ λK . Se define la funci´on radial de K como la funci´ on ρ(K, · ) : Rn \{0} −→ R dada por  ρ(K, x) = m´ax λ ≥ 0 : λx ∈ K =

1 . g(K, x)

La funci´on gauge fue definida originariamente por Minkowski en 1911, y proporciona un m´etodo muy u ´til para obtener una norma (y por tanto una topolog´ıa) en espacios vectoriales generales finito (e infinito)-dimensionales. En efecto, se demuestra que dado un cuerpo convexo K centralmente sim´etrico respecto al origen de coordenadas (se dice K es centralmente sim´etrico respecto a 0 si para todo p ∈ K se tiene que −p ∈ K, es decir, si K = −K), la expresi´on |x|K := g(K, x),

x ∈ Rn ,

define una norma en Rn para la cual K es la bola unidad. Es inmediato comprobar, utilizando las definiciones, que  i) K = x ∈ Rn : g(K, x) ≤ 1 , |x| si x ∈ Rn \{0}, λ > 0, λx ∈ bd K, y |λx| iii) ρ(K, x)x ∈ bd K para todo x ∈ Rn \{0}. ii) g(K, x) =

iv) La funci´on gauge es sublineal. La funci´on gauge est´a estrechamente relacionada con la funci´on soporte: Teorema 1.48. Si K es un cuerpo convexo que contiene el origen en su interior, entonces g(K, · ) = h(K ∗ , · ).

16

Los conjuntos convexos y sus propiedades

1.6.

La m´ etrica de Hausdorff. El Teorema de Selecci´ on de Blaschke. Sumario. La m´etrica de Hausdorff. Compacidad local del espacio m´etrico (C n , δ). El Teorema de Selecci´on de Blaschke. Continuidad. Aproximaci´on.

n muchos problemas de optimizaci´on geom´etrica, demostrar la existencia de una soluci´on es E esencial. Para ello, resulta de gran utilidad considerar ciertas familias de conjuntos convexos y poder asegurar que dentro de la familia es posible seleccionar un conjunto particular que verifique las propiedades deseadas. El principal objetivo de esta lecci´on es demostrar el Teorema de Selecci´ on de Blaschke. Este resultado permite concluir que la colecci´on de los subconjuntos convexos cerrados de un conjunto acotado en Rn puede dotarse de una m´etrica para la cual es un espacio compacto. En consecuencia, dado que toda funci´on real continua alcanza un m´aximo y un m´ınimo sobre un compacto, se puede establecer la existencia de conjuntos verificando ciertas propiedades extremales. Existen diversos m´etodos razonables, desde un punto de vista geom´etrico, de dotar a la familia con estructura de espacio m´etrico. Para ello, necesitamos tener una medida de la “distancia” entre dos subconjuntos A y B de Rn . Parece natural considerar, como tal distancia, el valor  d(A, B) = inf d(x, y) : x ∈ A e y ∈ B . (1) Kn

Sin embargo, esta definici´on es inadecuada para nuestro prop´osito, ya que no permite una distinci´ on suficiente entre los conjuntos: queremos que la distancia sea peque˜ na s´olo si los conjuntos son “pr´acticamente el mismo”, similitud que se refiere tanto a la forma como a la posici´on. Es por este motivo que se define la m´etrica de Hausdorff, particularmente conveniente e importante. Representaremos por C n la familia de los conjuntos compactos de Rn (no necesariamente convexos), dominio natural de esta m´etrica. Definici´ on 1.49. Dados dos conjuntos compactos A y B de Rn , se define la distancia de Hausdorff entre A y B como   δ(A, B) = m´ax sup inf |x − y|, sup inf |x − y| , x∈A y∈B

x∈B y∈A

o equivalentemente, n o δ(A, B) = m´ın λ ≥ 0 : A ⊂ B + λBn , B ⊂ A + λBn . Es sencillo ver que δ es una m´etrica en C n , denominada la m´etrica de Hausdorff. Cn

A partir de ahora, se entender´a que todas las nociones m´etricas y topol´ogicas que se refieran a o a Kn son las correspondientes a la m´etrica de Hausdorff y a la topolog´ıa por ella inducida.

Lema 1.50. Si {Ak : k ∈ N} es una sucesi´ on decreciente en C n , entonces l´ım Ak =

k→∞

∞ \ i=1

Ai .

´trica de Hausdorff. El Teorema de Seleccio ´ n de Blaschke. 1.6 La me

17

Esta propiedad permite demostrar el siguiente resultado: Teorema 1.51. El espacio m´etrico (C n , δ) es completo. Se dice que una subfamilia de C n es uniformemente acotada si existe una bola de un determinado radio en Rn que contiene todos los elementos de la subfamilia. Se puede probar entonces que: Teorema 1.52. De cada sucesi´ on uniformemente acotada en C n se puede extraer una subsucesi´ on convergente. Teorema 1.53. En (C n , δ), todo subconjunto cerrado y acotado es compacto. Y en particular, podemos concluir que el espacio m´etrico (C n , δ) es localmente compacto. Una vez demostrado el resultado que busc´abamos para conjuntos compactos, es momento de restringir nuestras consideraciones al espacio Kn de los cuerpos convexos. Teorema 1.54. Kn es un subconjunto cerrado de C n . Finalmente, a partir de los Teoremas 1.52 y 1.54 se obtiene el famoso Teorema de Selecci´ on de Blaschke, que establece lo siguiente: Teorema 1.55 (Teorema de Selecci´ on de Blaschke, 1916). De cualquier sucesi´ on uniformemente acotada de conjuntos convexos compactos se puede extraer una subsucesi´ on convergente a un conjunto convexo y compacto. Al haber dotado a C n y a Kn con una topolog´ıa, es natural preguntarse por la continuidad de las aplicaciones que nos hemos encontrado en las lecciones previas. As´ı, son continuos: i) El operador envoltura convexa conv : C n −→ Kn , pues δ(conv A, conv B) ≤ δ(A, B). ii) El operador suma vectorial + : C n × C n −→ C n , pues δ(A + A0 , B + B 0 ) ≤ δ(A, B) + δ(A0 , B 0 ). iii) La proyecci´on m´etrica p : Kn × Rn −→ Rn es continua en ambas variables, pues dados
K, L ∈ Kn y x, y ∈ Rn , llamando D := D K ∪ L ∪ {x, y} , se tiene que p p(K, x) − p(L, y) ≤ |x − y| + 5Dδ(K, L). iii) La funci´on soporte h : Kn × Rn −→ R es continua como funci´on de dos variables: si K, L ∈ Kn est´an contenidos en una bola Bn (R) para un determinado radio R > 0, y u, v ∈ Rn , entonces  h(K, u) − h(L, v) ≤ R|u − v| + m´ax |u|, |v| δ(K, L). iv) Dadas las relaciones existentes entre la funci´on soporte y las funciones gauge y radial, estas u ´ltimas tambi´en van a ser funciones continuas. Teorema 1.56. El funcional volumen (definido como la medida de Hausdorff ) es continuo en Kn .

18

Los conjuntos convexos y sus propiedades

Para finalizar la lecci´on, y con ella el cap´ıtulo, comentar que otra de las grandes utilidades de la m´etrica de Hausdorff es que el hecho de disponer de una m´etrica en la familia Kn de los cuerpos convexos nos permite estudiar la aproximaci´ on de este tipo de conjuntos por otros m´ as particulares (como por ejemplo politopos o cuerpos con frontera diferenciable), lo que resulta ser una herramienta muy u ´til en numerosas demostraciones. Teorema 1.57. Sean K un cuerpo convexo de Rn y ε > 0. Entonces, existe un politopo P ∈ Kn verificando que P ⊂ K ⊂ P + εBn , y por tanto, con δ(P, K) ≤ ε. Teorema 1.58 (Teorema de aproximaci´ on). Sea K un cuerpo convexo de Rn que contiene el origen en su interior. Entonces, para cada λ > 1, existe un politopo P ∈ Kn verificando que P ⊂ K ⊂ λP.