Cono convexo

Conjunto matemático cerrado bajo combinaciones lineales positivas

Un cono convexo (azul claro). En su interior, el cono convexo rojo claro está formado por todos los puntos αx + βy con α, β > 0 para los valores x e y representados . Las curvas de la parte superior derecha simbolizan que las regiones son infinitas en extensión.

En álgebra lineal , un cono —a veces llamado cono lineal para distinguirlo de otros tipos de conos— es un subconjunto de un espacio vectorial que está cerrado bajo la multiplicación escalar positiva; es decir, C es un cono si implica para cada escalar positivo s . Un cono no necesita ser convexo, o incluso parecerse a un cono en el espacio euclidiano . ${\displaystyle x\in C}$ ${\displaystyle sx\in C}$

Cuando los escalares son números reales, o pertenecen a un cuerpo ordenado , generalmente se denomina cono a un subconjunto de un espacio vectorial que está cerrado bajo la multiplicación por un escalar positivo . En este contexto, un cono convexo es un cono que está cerrado bajo la adición o, equivalentemente, un subconjunto de un espacio vectorial que está cerrado bajo combinaciones lineales con coeficientes positivos. De ello se deduce que los conos convexos son conjuntos convexos . ^[1]

En este artículo solo se considera el caso de escalares en un campo ordenado.

Definición

Un subconjunto C de un espacio vectorial V sobre un campo ordenado F es un cono (o a veces llamado cono lineal ) si para cada x en C y escalar positivo α en F , el producto αx está en C. ^[2] Nótese que algunos autores definen el cono con el escalar α abarcando todos los escalares no negativos (en lugar de todos los escalares positivos, que no incluyen 0). ^[3]

Un cono C es un cono convexo si αx + βy pertenece a C , para cualquier escalar positivo α , β y cualquier x , y en C . ^{[4] [5]} Un cono C es convexo si y solo si C + C ⊆ C .

Este concepto es significativo para cualquier espacio vectorial que permita el concepto de escalar "positivo", como espacios sobre los números racionales , algebraicos o (más comúnmente) reales. Observe también que los escalares en la definición son positivos, lo que significa que el origen no tiene que pertenecer a C. Algunos autores utilizan una definición que asegura que el origen pertenece a C. ^[6] Debido a los parámetros de escala α y β , los conos son infinitos en extensión y no están acotados.

Si C es un cono convexo, entonces para cualquier escalar positivo α y cualquier x en C el vector Se deduce que un cono convexo C es un caso especial de un cono lineal . ${\displaystyle \alpha x={\tfrac {\alpha }{2}}x+{\tfrac {\alpha }{2}}x\in C.}$

De la propiedad anterior se desprende que un cono convexo también puede definirse como un cono lineal que está cerrado bajo combinaciones convexas o simplemente bajo adiciones . Más sucintamente, un conjunto C es un cono convexo si y solo si αC = C y C + C = C , para cualquier escalar positivo α .

Ejemplos

Cono convexo que no es una envoltura cónica de un número finito de generadores.

Cono convexo generado por la combinación cónica de los tres vectores negros.

Un cono (la unión de dos rayos) que no es un cono convexo.

• Para un espacio vectorial V , el conjunto vacío, el espacio V y cualquier subespacio lineal de V son conos convexos.
• La envoltura cónica de un conjunto finito o infinito de vectores es un cono convexo. ${\displaystyle \mathbb {R} ^{n}}$
• Los conos tangentes de un conjunto convexo son conos convexos.
• El conjunto es un cono pero no un cono convexo. $${\displaystyle \left\{x\in \mathbb {R} ^{2}\mid x_{2}\geq 0,x_{1}=0\right\}\cup \left\{x\in \mathbb {R} ^{2}\mid x_{1}\geq 0,x_{2}=0\right\}}$$
• El cono norma es un cono convexo. $${\displaystyle \left\{(x,r)\in \mathbb {R} ^{d+1}\mid \|x\|\leq r\right\}}$$
• La intersección de dos conos convexos en el mismo espacio vectorial es nuevamente un cono convexo, pero su unión puede no serlo.
• La clase de conos convexos también está cerrada bajo aplicaciones lineales arbitrarias . En particular, si C es un cono convexo, también lo es su opuesto y es el subespacio lineal más grande contenido en C. ${\displaystyle -C}$ ${\displaystyle C\cap -C}$
• El conjunto de matrices semidefinidas positivas .
• El conjunto de funciones continuas no negativas es un cono convexo.

Ejemplos especiales

Conos convexos afines

Un cono convexo afín es el conjunto resultante de aplicar una transformación afín a un cono convexo. ^[7] Un ejemplo común es trasladar un cono convexo por un punto p : p + C . Técnicamente, tales transformaciones pueden producir no conos. Por ejemplo, a menos que p = 0 , p + C no es un cono lineal. Sin embargo, todavía se le llama cono convexo afín.

Medios espacios

Un hiperplano (lineal) es un conjunto en la forma donde f es una función lineal en el espacio vectorial V. Un semiespacio cerrado es un conjunto en la forma o y, asimismo, un semiespacio abierto utiliza una desigualdad estricta. ^{[8] [9]} ${\displaystyle \{x\in V\mid f(x)=c\}}$ ${\displaystyle \{x\in V\mid f(x)\leq c\}}$ ${\displaystyle \{x\in V\mid f(x)\geq c\},}$

Los semiespacios (abiertos o cerrados) son conos convexos afines. Además (en dimensiones finitas), cualquier cono convexo C que no sea todo el espacio V debe estar contenido en algún semiespacio cerrado H de V ; este es un caso especial del lema de Farkas .

Conos poliédricos y finitamente generados

Los conos poliédricos son tipos especiales de conos que pueden definirse de varias maneras: ^{[10] : 256–257}

• Un cono C es poliédrico si es la envoltura cónica de un número finito de vectores (esta propiedad también se denomina finitamente generada ). ^{[11] [12]} Es decir, existe un conjunto de vectores tal que . ${\displaystyle \{v_{1},\ldots ,v_{k}\}}$ ${\displaystyle C=\{a_{1}v_{1}+\cdots +a_{k}v_{k}\mid a_{i}\in \mathbb {R} _{\geq 0},v_{i}\in \mathbb {R} ^{n}\}}$
• Un cono es poliédrico si es la intersección de un número finito de semiespacios que tienen 0 en su borde (la equivalencia entre estas dos primeras definiciones fue demostrada por Weyl en 1935). ^{[13] [14]}
• Un cono C es poliédrico si existe alguna matriz tal que . ${\displaystyle A}$ ${\displaystyle C=\{x\in \mathbb {R} ^{n}\mid Ax\geq 0\}}$
• Un cono es poliédrico si es el conjunto solución de un sistema de inecuaciones lineales homogéneas. Algebraicamente, cada inecuación está definida por una fila de la matriz A . Geométricamente, cada inecuación define un semiespacio que pasa por el origen.

Todo cono finitamente generado es un cono poliédrico, y todo cono poliédrico es un cono finitamente generado. ^[11] Todo cono poliédrico tiene una representación única como una envoltura cónica de sus generadores extremales, y una representación única de las intersecciones de los semiespacios, dado que cada forma lineal asociada con los semiespacios también define un hiperplano de soporte de una faceta. ^[15]

Los conos poliédricos desempeñan un papel central en la teoría de la representación de los poliedros . Por ejemplo, el teorema de descomposición de los poliedros establece que cada poliedro puede escribirse como la suma de Minkowski de un politopo convexo y un cono poliédrico. ^{[16] [17]} Los conos poliédricos también desempeñan un papel importante en la demostración del Teorema de base finita relacionado para politopos, que muestra que cada politopo es un poliedro y cada poliedro acotado es un politopo. ^{[16] [18] [19]}

Las dos representaciones de un cono poliédrico (mediante inecuaciones y mediante vectores) pueden tener tamaños muy diferentes. Por ejemplo, considere el cono de todas las matrices n por n no negativas con sumas de filas y columnas iguales. La representación de inecuaciones requiere n ² inecuaciones y 2( n − 1) ecuaciones, pero la representación vectorial requiere n ! vectores (ver el Teorema de Birkhoff-von Neumann ). También puede ocurrir lo opuesto: el número de vectores puede ser polinómico mientras que el número de inecuaciones es exponencial. ^{[10] : 256}

Las dos representaciones juntas proporcionan una manera eficiente de decidir si un vector dado está en el cono: para demostrar que está en el cono, es suficiente presentarlo como una combinación cónica de los vectores que lo definen; para demostrar que no está en el cono, es suficiente presentar una única desigualdad definitoria que viola. Este hecho se conoce como lema de Farkas .

Un punto sutil en la representación por vectores es que el número de vectores puede ser exponencial en la dimensión, por lo que la prueba de que un vector está en el cono puede ser exponencialmente larga. Afortunadamente, el teorema de Carathéodory garantiza que cada vector en el cono puede ser representado por un máximo de d vectores definitorios, donde d es la dimensión del espacio.

Conos romos, puntiagudos, planos, salientes y propios.

Según la definición anterior, si C es un cono convexo, entonces C ∪ { 0 } también es un cono convexo. Se dice que un cono convexo esapuntado si0está enC, yromo si0noestá enC.^[2][20]Los conos romos se pueden excluir de la definición de cono convexo sustituyendo "no negativo" por "positivo" en la condición de α, β.

Un cono se llama plano si contiene algún vector distinto de cero x y su opuesto − x, lo que significa que C contiene un subespacio lineal de dimensión al menos uno, y saliente en caso contrario. ^{[21] [22]} Un cono romo convexo es necesariamente saliente, pero lo inverso no es necesariamente cierto. Un cono convexo C es saliente si y solo si C ∩ − C ⊆ { 0 }. Se dice que un cono C es generador si es igual a todo el espacio vectorial. ^[23] ${\displaystyle C-C=\{x-y\mid x\in C,y\in C\}}$

Algunos autores requieren que los conos salientes sean puntiagudos. ^[24] El término "puntiagudo" también se usa a menudo para referirse a un cono cerrado que no contiene ninguna línea completa (es decir, ningún subespacio no trivial del espacio vectorial ambiental V , o lo que se llama un cono saliente). ^{[25] [26] [27]} El término cono propio ( convexo ) se define de diversas formas, según el contexto y el autor. A menudo significa un cono que satisface otras propiedades como ser convexo, cerrado, puntiagudo, saliente y de dimensión completa. ^{[28] [29] [30]} Debido a estas definiciones variables, se debe consultar el contexto o la fuente para obtener la definición de estos términos.

Conos racionales

Un tipo de cono de particular interés para los matemáticos puros es el conjunto parcialmente ordenado de conos racionales. "Los conos racionales son objetos importantes en geometría algebraica tórica, álgebra conmutativa combinatoria, combinatoria geométrica, programación entera". ^[31] Este objeto surge cuando estudiamos los conos en junto con la red . Un cono se llama racional (aquí asumimos "puntiagudo", como se definió anteriormente) siempre que sus generadores tengan todos coordenadas enteras , es decir, si es un cono racional, entonces para algún . ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle C}$ ${\displaystyle C=\{a_{1}v_{1}+\cdots +a_{k}v_{k}\mid a_{i}\in \mathbb {R} _{+}\}}$ ${\displaystyle v_{i}\in \mathbb {Z} ^{d}}$

Cono doble

Sea C ⊂ V un conjunto, no necesariamente un conjunto convexo, en un espacio vectorial real V dotado de un producto interior . El cono dual (continuo o topológico) de C es el conjunto

${\displaystyle C^{*}=\{v\in V\mid \forall w\in C,\langle w,v\rangle \geq 0\},}$

que siempre es un cono convexo. Aquí, está el emparejamiento de dualidad entre C y V , es decir . ${\displaystyle \langle w,v\rangle }$ ${\displaystyle \langle w,v\rangle =v(w)}$

De manera más general, el cono dual (algebraico) de C ⊂ V en un espacio lineal V es un subconjunto del espacio dual V* definido por:

${\displaystyle C^{*}:=\left\{v\in V^{*}\mid \forall w\in C,v(w)\geq 0\right\}.}$

En otras palabras, si V* es el espacio dual algebraico de V , C* es el conjunto de funcionales lineales que son no negativos en el cono primario C . Si tomamos V* como el espacio dual continuo , entonces es el conjunto de funcionales lineales continuos no negativos en C . ^[32] Esta noción no requiere la especificación de un producto interno en V .

En dimensiones finitas, las dos nociones de cono dual son esencialmente las mismas porque cada funcional lineal de dimensión finita es continuo, ^[33] y cada funcional lineal continuo en un espacio de producto interno induce un isomorfismo lineal (mapa lineal no singular) de V* a V , y este isomorfismo llevará el cono dual dado por la segunda definición, en V* , al dado por la primera definición; véase el teorema de representación de Riesz . ^[32]

Si C es igual a su cono dual, entonces C se llama autodual . Se puede decir que un cono es autodual sin referencia a ningún producto interno dado, si existe un producto interno con respecto al cual es igual a su dual según la primera definición.

Construcciones

• Dado un subconjunto cerrado y convexo K del espacio de Hilbert V , el cono normal exterior al conjunto K en el punto x en K está dado por

  ${\displaystyle N_{K}(x)=\left\{p\in V\colon \forall x^{*}\in K,\left\langle p,x^{*}-x\right\rangle \leq 0\right\}.}$

• Dado un subconjunto cerrado y convexo K de V , el cono tangente (o cono contingente ) al conjunto K en el punto x está dado por

  ${\displaystyle T_{K}(x)={\overline {\bigcup _{h>0}{\frac {K-x}{h}}}}.}$

• Dado un subconjunto cerrado y convexo K del espacio de Hilbert V , el cono tangente al conjunto K en el punto x en K se puede definir como cono polar a cono normal hacia afuera : ${\displaystyle N_{K}(x)}$

  ${\displaystyle T_{K}(x)=N_{K}^{o}(x)\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \{y\in V\mid \forall \xi \in N_{K}(x):\langle y,\xi \rangle \leqslant 0\}}$

Tanto el cono normal como el tangente tienen la propiedad de ser cerrados y convexos.

Son conceptos importantes en los campos de optimización convexa , desigualdades variacionales y sistemas dinámicos proyectados .

Propiedades

Si C es un cono convexo no vacío en X , entonces el espacio lineal de C es igual a C - C y el subespacio vectorial más grande de X contenido en C es igual a C ∩ (− C ). ^[34]

Orden parcial definida por un cono convexo

Un cono convexo puntiagudo y saliente C induce un ordenamiento parcial "≥" en V , definido de modo que si y solo si (Si el cono es plano, la misma definición da simplemente un preorden .) Las sumas y los múltiplos escalares positivos de desigualdades válidas con respecto a este orden siguen siendo desigualdades válidas. Un espacio vectorial con dicho orden se denomina espacio vectorial ordenado . Los ejemplos incluyen el orden del producto en vectores de valores reales y el orden de Loewner en matrices semidefinidas positivas. Este tipo de ordenamiento se encuentra comúnmente en la programación semidefinida . ${\displaystyle x\geq y}$ ${\displaystyle x-y\in C.}$ ${\displaystyle \mathbb {R} ^{n},}$

Véase también

• Cono (desambiguación)
  • Cono (geometría)
  • Cono (topología)
• El lema de Farkas
• Teorema bipolar
• Espacio vectorial ordenado

Notas

1. Boyd, Stephen; Vandenberghe, Lieven (8 de marzo de 2004). Optimización convexa. Cambridge University Press. ISBN 978-0-521-83378-3.
2. Bernstein, Dennis S. (26 de julio de 2009). Matrix Mathematics: Theory, Facts, and Formulas (Segunda edición). Princeton University Press. pág. 97. ISBN 978-0691140391.
3. C. Zalinescu (1 de enero de 2002). Análisis convexo en espacios vectoriales generales. World Scientific. pág. 1. ISBN 978-981-238-067-8.
4. Nef, Walter (1 de enero de 1988). Álgebra lineal. Courier Corporation. pág. 35. ISBN 9780486657721.
5. Itô, Kiyosi (1 de enero de 1993). Diccionario enciclopédico de matemáticas. Prensa del MIT. ISBN 9780262590204.
6. Rockafellar, Ralph Tyrell (29 de abril de 2015). Análisis convexo. Princeton University Press. pág. 13. ISBN 9781400873173.
7. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (6 de diciembre de 2012). Fundamentos del análisis convexo. Springer Science & Business Media. ISBN 9783642564680.
8. Aliprantis, Charalambos D.; Border, Kim C. (2 de mayo de 2007). Análisis de dimensión infinita: una guía para el autoestopista. Springer Science & Business Media. pág. 197. ISBN 9783540326960.
9. Rockafellar, Ralph Tyrell (29 de abril de 2015). Análisis convexo. Princeton University Press. pág. 10. ISBN 9781400873173.
10. Lovász, László ; Plummer, Doctor en Medicina (1986). Teoría del emparejamiento . Anales de matemáticas discretas. vol. 29. Holanda Septentrional. ISBN 0-444-87916-1.Sr. 0859549  .
11. Loera, Jesús A. De; Hemmecke, Raymond; Köppe, Matthias (1 de enero de 2012). Ideas algebraicas y geométricas en la teoría de la optimización discreta. SIAM. ISBN 9781611972443.
12. Schrijver, Alejandro (7 de julio de 1998). Teoría de la Programación Lineal y Entera. John Wiley e hijos. ISBN 9780471982326.
13. Weyl, H. (1935). "Elementare Theorie der konvexen Polyeder". Comentarios Mathematici Helvetici . 7 : 290–306. doi :10.1007/BF01292722.
14. Mirkil, H. (1957). "Nuevas caracterizaciones de conos poliédricos". Revista Canadiense de Matemáticas . 9 : 1–4. doi :10.4153/CJM-1957-001-5. MR  0083761.
15. Bruns, Winfried; Gubeladze, Joseph (2009). Politopos, anillos y teoría K (1.ª ed.). Springer Monographs in Mathematics. pág. 3. ISBN 9780387763552.
16. Schrijver, Alejandro (7 de julio de 1998). Teoría de la Programación Lineal y Entera. John Wiley e hijos. págs. 88–89. ISBN 9780471982326.
17. Conforti, Michele; Cornuejols, Gerard; Zambelli, Giacomo (15 de noviembre de 2014). Programación entera. Saltador. pag. 111.ISBN​ 9783319110080.
18. Korte, Bernhard; Vygen, Jens (11 de noviembre de 2013). Optimización combinatoria: teoría y algoritmos. Springer Science & Business Media. pág. 61. ISBN 9783662217115.
19. Villarreal, Rafael (26 de marzo de 2015). Álgebras monomiales, segunda edición. CRC Press. pág. 9. ISBN 9781482234701.
20. Dhara, Anulekha; Dutta, Joydeep (17 de octubre de 2011). Condiciones de optimalidad en optimización convexa: una perspectiva de dimensión finita. CRC Press. pág. 243. ISBN 9781439868225.
21. Neustadt, Lucien W. (8 de marzo de 2015). Optimización: una teoría de las condiciones necesarias. Princeton University Press. pág. 6. ISBN 9781400870530.
22. Edwards, RE (25 de octubre de 2012). Análisis funcional: teoría y aplicaciones. Courier Corporation. pág. 135. ISBN 9780486145105.
23. Schaefer y Wolff 1999, págs. 205-209.
24. Hadjisavvas, Nicolas; Martinez-Legaz, Juan E.; Penot, Jean-Paul (10 de abril de 2001). Convexidad generalizada y monotonía generalizada: Actas del 6.º Simposio internacional sobre convexidad/monotonía generalizadas, Samos, septiembre de 1999. Springer Science & Business Media. pág. 238. ISBN 9783540418061.
25. Bauschke, Heinz H.; Combettes, Patrick L. (19 de abril de 2011). Análisis convexo y teoría de operadores monótonos en espacios de Hilbert. Springer Science & Business Media. pág. 88. ISBN 9781441994677.
26. Cameron, Neil (5 de septiembre de 1985). Introducción a la programación lineal y convexa. Archivo CUP. p. 32. ISBN 9780521312073.
27. Panik, MJ (1 de diciembre de 2013). Programación lineal: matemáticas, teoría y algoritmos. Springer Science & Business Media. pág. 40. ISBN 9781461334347.
28. Dattorro, Jon (1 de enero de 2005). Optimización convexa y geometría de distancias euclidianas. Meboo Publishing USA. pág. 96. ISBN 9780976401308.
29. Nicola, PierCarlo (14 de marzo de 2013). Economía matemática dominante en el siglo XX. Springer Science & Business Media. pág. 125. ISBN 9783662042380.
30. Fujiwara, Hidenori; Ludwig, Jean (5 de diciembre de 2014). Análisis armónico en grupos de Lie con solución exponencial. Springer. pág. 246. ISBN 9784431552888.
31. Gubeladze, José; Michałek, Mateusz (1 de enero de 2018). "El poset de los conos racionales". Revista Pacífico de Matemáticas . 292 (1): 103-115. arXiv : 1606.02083 . doi :10.2140/pjm.2018.292.103. S2CID  119639952.
32. Hunter, John K.; Nachtergaele, Bruno (1 de enero de 2001). Análisis aplicado. World Scientific. pág. 116. ISBN 9789810241919.
33. Carothers, NL (1 de enero de 2005). Un curso breve sobre la teoría del espacio de Banach. Cambridge University Press. ISBN 9780521603720.
34. Narici y Beckenstein 2011, págs. 149-153.

Referencias

• Bourbaki, Nicolas (1987). Espacios vectoriales topológicos. Elementos de matemáticas. Berlín, Nueva York: Springer-Verlag . ISBN 978-3-540-13627-9.
• Narici, Lawrence; Beckenstein, Edward (2011). Espacios vectoriales topológicos . Matemáticas puras y aplicadas (segunda edición). Boca Raton, FL: CRC Press. ISBN 978-1584888666.OCLC 144216834  .
• Rockafellar, RT (1997) [1970]. Análisis convexo. Princeton, NJ: Princeton University Press. ISBN 1-4008-7317-7.
• Schaefer, Helmut H. ; Wolff, Manfred P. (1999). Espacios vectoriales topológicos . GTM . Vol. 8 (Segunda ed.). Nueva York, NY: Springer New York Imprenta Springer. ISBN 978-1-4612-7155-0.OCLC 840278135  .
• Trèves, François (2006) [1967]. Espacios vectoriales topológicos, distribuciones y núcleos . Mineola, Nueva York: Publicaciones de Dover. ISBN 978-0-486-45352-1.OCLC 853623322  .
• Zălinescu, C. (2002). Análisis convexo en espacios vectoriales generales. River Edge, NJ: World Scientific. ISBN 981-238-067-1.Señor 1921556  .