Nuevos resultados sobre sistemas lineales y conjuntos convexos Margarita Rodríguez Álvarez

Tesis de Doctorado Facultad:

Ciencias

Directores: Dr. Miguel Ángel Goberna Torrent Dr. Valentín Jornet Pla

2001

Universidad de Alicante Depto. de Estadística e Investigación Operativa

1XHYRV UHVXOWDGRV VREUH VLVWHPDV OLQHDOHV \ FRQMXQWRV FRQYH[RV

Memoria presentada por Margarita Rodríguez Álvarez para optar al grado de Doctor en Ciencias Matemáticas, realizada bajo la dirección de los doctores D. Miguel Ángel Goberna Torrent y D. Valentín Jornet Pla.

Alicante, Mayo de 2001

D. MIGUEL ÁNGEL GOBERNA TORRENT, Catedrático de Estadística e Investigación Operativa de la Universidad de Alicante, y D. VALENTÍN JORNET PLA, Catedrático E.U. de Estadística e Investigación Operativa de la Universidad de Alicante, CERTIFICAN: Que la presente memoria 1XHYRV UHVXOWDGRV VREUH VLVWHPDV OLQHDOHV \ FRQMXQWRV FRQYH[RV ha sido realizada bajo su dirección en el Departamento de Estadística e Investigación Operativa de la Universidad de Alicante por Dña. Margarita Rodríguez Álvarez, y constituye su tesis para optar al grado de Doctor en Ciencias Matemáticas.

Y para que conste, en cumplimiento de la legislación vigente, ¿rman el presente certi¿cado en Alicante, a 10 de Mayo de dos mil uno.

Fdo: Miguel A. Goberna

Fdo: Valentín Jornet

ËQGLFH ,QWURGXFFLyQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  &DStWXOR  3UHOLPLQDUHV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  0.1. Conjuntos convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 0.2. Sistemas semi-in¿nitos lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 &DStWXOR  6LVWHPDV OLQHDOHV JHQHUDOHV HQ U? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.2. Existencia de soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3. Conjuntos linealizables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4. Geometría . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.5. Optimización lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 &DStWXOR  &RQItQ GH XQ FRQMXQWR FRQYH[R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  2.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2. Confín: Propiedades básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.3. Conexión del confín . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.4. El confín y la iluminación de los conjuntos convexos cerrados . . . . . . . . . . . 71 2.5. Algunas aplicaciones a los sistemas de desigualdades lineales . . . . . . . . . . . . 77 &DStWXOR  &DUDFWHUL]DFLyQ GH IDPLOLDV GH FRQMXQWRV FHUUDGRV FRQYH[RV . . . . . .  3.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.2. Caracterización de las sumas de conjuntos convexos compactos con subespacios vectoriales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.3. Caracterización de los símplices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.4. Caracterización de los sandwiches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.5. Caracterización topológica de los &-sandwiches . . . . . . . . . . . . . . . . . . . . . . . 103 3.6. Caracterización de los paralelotopos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.7. Caracterización de conjuntos continuos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.8. Caracterización de cuerpos convexos suaves . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3.9. Caracterización de familias de cuerpos convexos mediante conceptos de iluminación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 %LEOLRJUDItD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

,QWURGXFFLyQ El conjunto de soluciones de cualquier sistema de desigualdades lineales de la forma i@| %  K| c | 5 A j, siendo A un conjunto arbitrario de índices (posiblemente in¿nito), 

@| 5 U? y K| 5 U para todo | 5 A , es un conjunto convexo cerrado y, recíprocamente, cualquier conjunto convexo cerrado se puede representar por medio de una in¿nidad de sistemas lineales de este tipo. Existe, pues, una correspondencia entre sistemas semi-in¿nitos lineales (SSIL) y conjuntos convexos cerrados. Sin embargo, los sistemas anteriormente mencionados no son los sistemas lineales más generales que podemos considerar. Un sistema en U? de la forma j ' i@| %  K| c | 5 (( @| % : K| c | 5 .j c 



donde los conjuntos de índices, ( y ., son disjuntos y no simultáneamente vacíos, @| 5 U? y K| 5 U para todo | 5 A G' ( ^ ., contiene un número arbitrario (posiblemente in¿nito) de restricciones de desigualdad débil (dos de las cuales reemplazan a una ecuación) y/o estricta. Se trata, pues, de un sistema semi-in¿nito lineal general (SSILG) y su conjunto de soluciones es un conjunto convexo, por tratarse de una intersección de semiespacios abiertos o cerrados. En este punto, cabe preguntarse si, al igual que ocurre con los conjuntos convexos cerrados (caso particular de los conjuntos convexos) y los SSIL (caso particular de los SSILG), todo conjunto convexo se puede representar por medio de un SSILG. Al ser negativa la respuesta, llamaremos conjuntos linealizables a la clase de conjuntos convexos que sí cumplen esta propiedad. Estos conjuntos fueron introducidos por Fenchel [14] (con la denominación de “evenly convex”) para extender la teoría de la polaridad, pero sin analizar a fondo sus posibles caracterizaciones ni estudiar 1

2

Introducción

exhaustivamente sus propiedades. De la existencia de este trabajo tuvimos noticia a través de una comunicación privada del Prof. Martínez Legaz, quien ha utilizado estos conjuntos para de¿nir un tipo de funciones cuasiconvexas importante para la generalización de la teoría de la conjugación (véanse [24], [30], [ 25] y [26]). Aunque los SSIL han sido muy bien estudiados por su conexión con la Programación Semi-In¿nita Lineal, no ocurre lo mismo con los SSILG, por lo que dedicaremos el Capítulo 1 de la presente memoria al estudio de esta clase de sistemas y de los conjuntos que admiten este tipo de representaciones lineales. En él analizaremos la existencia de soluciones, caracterizaremos geométricamente los conjuntos linealizables y probaremos que se pueden extender, a esta gran familia de conjuntos convexos, la mayoría de las propiedades conocidas para la subfamilia de los conjuntos convexos cerrados. También mostraremos que es posible obtener información geométrica sobre estos conjuntos a partir de una representación lineal dada y, ¿nalmente, discutiremos la teoría y los métodos para aquellos problemas de optimización lineal que contienen restricciones de desigualdad estrictas. Dentro de la correspondencia que existe entre SSIL y conjuntos convexos cerrados, hay ciertos tipos de SSIL que se corresponden con determinadas familias de conjuntos convexos cerrados. Así, por ejemplo, los llamados sistemas localmente poliédricos (LOP), sistemas en los que la condición de Weyl (siempre su¿ciente para que un punto sea extremo) es también necesaria, tienen conjuntos de soluciones cuasipoliédricos (conjuntos convexos cerrados cuyas intersecciones con polítopos son polítopos) y, viceversa, cualquier conjunto cuasipoliédrico admite una representación LOP. Por lo tanto, podemos caracterizar los conjuntos cuasipoliédricos como aquellos conjuntos convexos cerrados que admiten representaciones LOP. La caracterización de familias de conjuntos convexos cerrados puede resultar útil en diferentes campos de las matemáticas aplicadas.

Así, por ejemplo, una

condición necesaria para la convergencia de algoritmos de programación matemática que progresan sobre la frontera del conjunto factible (como el método simplex en programación lineal ordinaria y semi-in¿nita) es la conexión por arcos de la frontera, por lo que sería útil caracterizar aquellos conjuntos convexos cerrados que poseen esta

Introducción

3

deseada propiedad. En el Capítulo 3 abordaremos la caracterización de determinadas familias de conjuntos convexos cerrados (algunas de ellas con propiedades muy interesantes de cara a las aplicaciones) desde diferentes puntos de vista, entre ellos sus representaciones lineales. En particular, para caracterizar la clase de los conjuntos convexos cerrados que tienen la frontera relativa conexa por arcos será necesario el uso de un nuevo concepto, el de confín de un conjunto convexo no vacío, que introduciremos en el Capítulo 2. En este capítulo, además, analizaremos las propiedades del confín de los conjuntos convexos en general y de los convexos cerrados en particular, así como sus relaciones con ciertos conceptos de iluminación ya conocidos y sus aplicaciones a la teoría de los sistemas lineales. Por último, decir que los tres capítulos que constituyen el cuerpo de esta memoria están precedidos por un capítulo de preliminares, el Capítulo 0, en el que se recoge la notación, las de¿niciones y los enunciados de los resultados ya conocidos que se van a utilizar en los demás capítulos. Buena parte de dichos resultados aparecen expuestos en la reciente monografía de Goberna y López [19] de una manera ordenada y con una notación uni¿cada que se ha mantenido en esta memoria. Hemos optado por referirnos a [19], siempre que ha sido posible, en lugar de hacerlo a las fuentes originales (que el lector puede encontrar en las notas ¿nales del correspondiente capítulo de [19]).

&DStWXOR  3UHOLPLQDUHV  &RQMXQWRV FRQYH[RV En el espacio euclídeo, U? , denotaremos por nn, f? , ? ' i% 5 U? m n%n j y 7? ' i% 5 U? m n%n ' j c la norma euclídea, el vector cero, la EROD XQLGDG DELHUWD y la HVIHUD XQLGDG, respectivamente. La base canónica de U? la representaremos por e c    c e? . Un conjunto 



U? se dice que es FRQYH[R cuando, para todo par

%c + 5 , el segmento d%c +o G' iE  b % n b+ m f  b  j está contenido en . Consideraremos que el vacío es un conjunto convexo por convenio. Un conjunto no vacío   U? se dice que es un FRQR si contiene a todos los rayos ib% m b : fj, con % 5 q if? j. Dado > 9'   U? , denotaremos por tT@? , @g , UL? , UL?i  y 

z

al

VXEHVSDFLR YHFWRULDO GH U? JHQHUDGR por , la HQYROWXUD DItQ de , la HQYROWXUD FRQYH[D de , el FRQR FRQYH[R JHQHUDGR por  (de¿nido como la intersección de todos los conos convexos que contienen al origen y al conjunto ) y el subespacio 5

6

0. Preliminares

de los vectores que son ortogonales a todos los elementos de , respectivamente. Si  ' >, adoptaremos el convenio tT@? > ' @g > ' UL?i > ' if? j. Si  es convexo no vacío, denotaremos por _4  su GLPHQVLyQ (de¿nida como la dimensión de @g ). Todas estas envolturas se pueden describir a través del espacio de VXFHVLRQHV ¿QLWDV JHQHUDOL]DGDV, UEA  , cuyos elementos son las funciones b G A $ U tales que b| 9' f sólo en un subconjunto ¿nito de A . El cono convexo, en UEA  , de las sucesiones ¿nitas EA 

no negativas es Un . Supuesto que  es convexo, diremos que un conjunto convexo f   es una FDUD de  si, para todo par   9'  2 de  tal que f _ o  c  2 d 9' >, se tiene que d  c 2 o  f. El conjunto vacío también se considera una cara de  por convenio. Los SXQWRV H[WUHPRV, las DULVWDV y las IDFHWDV de  son las caras de  de dimensión f,  y ?  , respectivamente. Denotaremos por i |h  el conjunto de todos los puntos extremos de . Diremos que una cara es H[SXHVWD si se puede obtener como conjunto de mínimos de una función afín sobre . Para  convexo no vacío de¿niremos el FRQR GH UHFHVLyQ de , n , que viene dado por  n  G' i 5 U? m % n > 5  para todo % 5  y para todo >  fj y el FRQR GH GLUHFFLRQHV IDFWLEOHV de  en % 5 , (Ec %, dado por (Ec % G' i 5 U? m % n > 5  para algún > : fj  Si  9' > es un cono convexo, de¿niremos el FRQR SRODU SRVLWLYR de ,  J , dado por  J G' i 5 U? m  %  f para todo % 5 j  

Obsérvese que para todo % 5 , ( Ec % ' UL?i E  %. Al conjunto n  _ En  le llamaremos HVSDFLR GH OLQHDOLGDG de  y se denotará por *? . Un cono convexo es DSXQWDGR cuando no contiene rectas, es decir, si su espacio de linealidad se reduce al vector cero. Un vector no nulo  5 n  es una GLUHFFLyQ H[WUHPD del conjunto convexo no vacío  si, para todo par de vectores   , 2 5  n  tales que  ' >   n >2 2

0.1 Conjuntos convexos

7

(> y >2 números reales positivos), se tiene que  tT@?   ' tT@? ij c

 ' c 2

Desde el punto de vista topológico, denotamos por ?| , U*  y M_  los conjuntos LQWHULRU, FODXVXUD y IURQWHUD de un subconjunto  cualquiera de U? . Si el conjunto  es convexo, de¿nimos los conjuntos LQWHULRU UHODWLYR y IURQWHUD UHODWLYD de , denotados por h?|  y hM_ , como el interior y la frontera de  cuando consideramos  como subconjunto de @g  con la topología inducida. Dado un conjunto convexo  y un punto % 5 M_ , existe un vector @ 5 U? q if? j tal que @ %  @ % para todo % 5  a la frontera de este semiespacio le llamaremos 



KLSHUSODQR GH VRSRUWH de  en %. Se utilizarán a menudo las siguientes familias de conjuntos convexos cerrados: los SROLHGURV FRQYH[RV (de¿nidos como intersecciones ¿nitas de semiespacios cerrados), los SROtWRSRV (poliedros convexos acotados) y los FRQMXQWRV FXDVLSROLpGULFRV (de¿nidos por Klee como aquellos subconjuntos de U? cuyas intersecciones con polítopos son polítopos). Ciertas pruebas por inducción utilizan implícitamente la adaptación de los conceptos anteriores a variedades: Las variedades a¿nes en  (variedad afín de U? ) son las variedades a¿nes de U? contenidas en , y son hiperplanos en  cuando su dimensión es E_4   . Si u es un hiperplano en , cada una de las dos componentes conexas de  qu es un semiespacio abierto en  determinado por u su unión con u proporciona los dos semiespacios cerrados en  correspondientes a u. La intersección de ¿nitos semiespacios cerrados de  es un poliedro convexo en , pudiéndose probar que son exactamente los poliedros convexos de U? contenidos en . Del mismo modo, los polítopos (cuasipoliedros) de  son los polítopos (cuasipoliedros) de U? contenidos en . Las propiedades de los poliedros convexos, polítopos y cuasipoliedros en una variedad afín de dimensión 6 ? son las mismas que las de los objetos correspondientes en U6 (sustituyendo los operadores topológicos, M_ e ?|, por los relativos correspondientes, hM_ y h?|). Dado que será frecuente el uso de resultados de Análisis Convexo a lo largo de la

8

0. Preliminares

memoria, hacemos, a continuación, una recopilación de los mismos, dando, para cada uno de ellos, la adecuada referencia bibliográ¿ca. En algunos casos aislados, daremos el enunciado y su demostración, por tratarse de nuevas aportaciones. 352326,&,Ï1  >32 7K @ 6L g \ g2 VRQ FRQRV FRQYH[RV TXH FRQWLHQHQ DO

RULJHQ HQWRQFHV g n g2 ' UL? Eg ^ g2 

352326,&,Ï1  6HD  XQ FRQMXQWR FRQYH[R QR YDFtR HQ U?  (QWRQFHV VH YHUL¿FDQ

ODV VLJXLHQWHV SURSRVLFLRQHV

(i) h?|  HV XQ FRQMXQWR FRQYH[R QR YDFtR >32 7K @ (ii) h?| U*  ' h?|  \ U* h?|  ' U*  >32 7K @ (iii) VL % 5 h?|  H + 5 U*  HQWRQFHV d%c +d  h?|  /HPD GH $FFHVLELOLGDG >32 7K @ \ (iv) 5 5 h?|  VL \ VyOR VL SDUD WRGR % 5  H[LVWH > :  WDO TXH E  > % n >5 5  >32 7K @ 352326,&,Ï1  >32 7K @ 6HD   U? XQ FRQMXQWR FRQYH[R \ VHD  XQD WUDQVIRUPDFLyQ OLQHDO GH U? HQ U6  (QWRQFHV

h?| E '  Eh?|   352326,&,Ï1  >32 &RU @ 3DUD FXDOTXLHU SDU GH FRQMXQWRV FRQYH[RV GH U? 

 \ 2  VH FXPSOH

h?| E n 2  ' h?|  n h?| 2  Como se ha señalado, el interior relativo de un conjunto convexo no vacío es no vacío. Algo parecido ocurre con hM_ . 352326,&,Ï1  6HD  XQ FRQMXQWR FRQYH[R QR YDFtR HQ U?  (QWRQFHV VH YHUL¿FDQ

ODV VLJXLHQWHV SURSRVLFLRQHV

(i) hM_  HV QR YDFtR VL \ VyOR VL  QR HV XQD YDULHGDG DItQ \ (ii) VL  HV XQ VXEFRQMXQWR SURSLR GH U?  HQWRQFHV  WLHQH DO PHQRV XQ SXQWR IURQWHUD 'HPRVWUDFLyQ (i) Para demostrar la implicación no trivial, construiremos un par de sucesiones i%? j   e i+? j  E@g  q convergentes al mismo punto de @g . Dicho punto estará en la frontera relativa de . Por ser  no vacío y no ser una variedad afín (E@g  q 9' >), existe un % n +  punto % 5  y un punto +  5 E@g  q. Si (que pertenece a @g  por 2

0.1 Conjuntos convexos

9

ser combinación convexa de elementos de dicho conjunto) pertenece a , entonces tomamos %2 '

% n +  e +2 ' +  2

En caso contrario, tomamos % n +   2

%2 ' % e + 2 '

En general, para construir los términos %?n e +?n , se toman %?n '

%? n + ? %? n +? e +?n ' + ? c si 5 c 2 2

y %?n ' %? e +?n '

%? n + ? %? n + ? c si 5 E@g  q 2 2

De esta manera hemos construido una sucesión i%? j contenida en el conjunto  y una sucesión i+ ? j contenida en el conjunto E@g  q cuyos términos ?-ésimos veri¿can que n%?  + ? n '

n%?



3

 +?  n  2 3

La sucesión i%? j es de Cauchy en U? ya que, para todo ? 5 Q y R  f, se tiene que  ?nR  n%  +  n %  %?   n%?  + ? n '  2?  3

Del mismo modo, i+ ? j también es una sucesión de Cauchy en U? . Además, ambas sucesiones son convergentes en U? a un mismo punto, el cual pertenece a @g  por ser éste un conjunto cerrado. (ii) El argumento de la demostración es el mismo que en el caso anterior sustituyendo @g  por U? 



La siguiente proposición caracteriza los puntos del interior relativo de la envoltura convexa (envoltura convexa cónica) de un conjunto no vacío de U? . 352326,&,Ï1  >19 7K $@ 6HD  XQ FRQMXQWR QR YDFtR HQ U? \ 5 5 @g 

5 5 tT@?   (QWRQFHV ODV VLJXLHQWHV SURSRVLFLRQHV VRQ HTXLYDOHQWHV

10

0. Preliminares

(i) 5 5 h?| UL?  5 5 h?| UL?i  UHVSHFWLYDPHQWH  (ii) H[LVWHQ SXQWRV % 5   ' c 2c    c R FRQ @g i% c %2 c    c %R j ' @g  UHVSHFWL YDPHQWH tT@? i% c %2 c    c %R j ' tT@?  , \ HVFDODUHV SRVLWLYRV k   ' c 2c    c R R R R S S S WDOHV TXH 5 ' k % \ k '  UHVSHFWLYDPHQWH k DUELWUDULD  \ '

'

'

(iii) 5 n UL?i E  5 ' @g  (Un dEUL?i   5o ' UL?i di5j ^ UL?i o ' tT@? ). En la siguiente proposición demostramos algunas de las propiedades, claramente intuitivas, que tienen los puntos del interior relativo de un convexo no vacío. 352326,&,Ï1  6HD  XQ FRQMXQWR FRQYH[R QR YDFtR \ % 5 h?|  (QWRQFHV VH

YHUL¿FDQ ODV VLJXLHQWHV SURSRVLFLRQHV

(i) tT@? E  % ' UL?i E  % ' E@g    y (ii) f? 5 h?|E  % 'HPRVWUDFLyQ

(i) Para demostrar la primera igualdad es su¿ciente probar

que dada una base en tT@? E  %, sus elementos y los opuestos pertenecen a UL?i E  %. Sea i+   %c  ' c    c 6j c con +  5  para todo  ' c    c 6c una base de tT@? E  %  Puesto que % 5 h?| , existe 0 : fc tal que E% n 0?  _ E@g    Para cada  ' c    c 6, el punto %

0 E+   % 5 E% n 0?  _ E@g   c 2 n+   %n

de modo que 0 E%  +   5 % 2 n+   %n y, por lo tanto, %  +  5 UL?i E  %  Dado que también se veri¿ca que +   % 5 UL?i E  % para todo  ' c c 6, se

0.1 Conjuntos convexos

11

obtiene que UL?i E  % ' tT@? E  %  Por otra parte, si % 5 h?| , E@g    ' E@g   %

(0.1)

En efecto, si +  % 5 E@g   , entonces +  % ' + n %  %  % ' E+ n %  %  % 5 E@g   % La segunda igualdad en (i) se obtiene como consecuencia de (0.1) y de la Proposición 0.6(iii). (ii) Si % 5 h?| c entonces, por la Proposición 0.6, existen puntos % 5 ,  ' c    c R, con  @g  ' @g % c %2 c c %R c y escalares positivos k ,  ' c    c R, tales que R [

%'

'

k % y

R [ '

k ' 

Entonces R [

f? '

'

R [

k %  % '

con k : fc  ' c    c R,

R [ '

'

k  % 

R [ '

R [ k % ' k E%  % '

k '  y

 @gE  % ' @g %  %c %2  %c c %R  % c y, por la Proposición 0.6, f? 5 h?| UL?E  % ' h?|E  %



El siguiente resultado caracteriza la acotación de un conjunto convexo cerrado no vacío a través de su cono de recesión. 352326,&,Ï1  >32 7K @ 8Q FRQMXQWR FRQYH[R FHUUDGR QR YDFtR   U? HV

DFRWDGR VL \ VyOR VL n  ' if? j

12

0. Preliminares

352326,&,Ï1  >32 &RU @ 6HDQ  c    c 6 FRQMXQWRV FRQYH[RV QR YDFtRV HQ U? TXH VDWLVIDFHQ OD VLJXLHQWH FRQGLFLyQ VL 5 c    c 56 VRQ YHFWRUHV WDOHV TXH 5 5 n EU*   \ 5 n    n 56 ' f?  HQWRQFHV 5 5 *? EU*   SDUD  ' c    c 6

(QWRQFHV

U* E n    n 6  ' U*  n    n U* 6 c  n dU* E n    n 6 o ' n EU*   n    n n EU* 6   En las dos siguientes proposiciones se dan propiedades acerca de las caras de un conjunto convexo. 352326,&,Ï1  >32 7K @ 6HD  XQ FRQMXQWR FRQYH[R \ VHD   XQD FDUD GH

 6L ( HV XQ FRQMXQWR FRQYH[R HQ  WDO TXH Eh?| ( _  9' > HQWRQFHV (    



352326,&,Ï1  >32 &RU @ 6HD  XQ FRQMXQWR FRQYH[R \ VHD   XQD FDUD

SURSLD GH  (QWRQFHV   hM_  \ _4  _4  



Se dice que un par de conjuntos no vacíos,  y 2 , son VHSDUDEOHV si existe un hiperplano M G' i% 5 U? m @ % ' Kj tal que @ %  K  f  @ +  K para todo % 5  y 





para todo + 5 2 . Si, además, E ^ 2  qM 9' >, entonces  y 2 están SURSLDPHQWH VHSDUDGRV. En el caso de que las desigualdades sean estrictas, se dice que M separa a  y 2 HVWULFWDPHQWH Por otra parte, si se cumple la desigualdad ?u i@ % m % 5  j  tT i@ + m + 5 2 j c 



se dice que  y 2 están GpELOPHQWH VHSDUDGRV y si esta desigualdad es estricta, se dice que M separa a  y 2 IXHUWHPHQWH. 352326,&,Ï1  >32 7K @ 6HD  XQ FRQMXQWR FRQYH[R QR YDFtR UHODWLYDPHQWH DELHUWR HQ U?  \ VHD  XQD YDULHGDG DItQ QR YDFtD HQ U? TXH QR FRUWD D  (QWRQFHV

H[LVWH XQ KLSHUSODQR M FRQWHQLHQGR D  WDO TXH XQR GH ORV VHPLHVSDFLRV DELHUWRV DVRFLDGRV FRQ M FRQWLHQH D  352326,&,Ï1  >32 &RU @ 6HDQ  \ 2 FRQMXQWRV FHUUDGRV FRQYH[RV QR YDFtRV GLVMXQWRV HQ U? TXH QR WLHQHQ GLUHFFLRQHV GH UHFHVLyQ HQ FRP~Q (QWRQFHV

H[LVWH XQ KLSHUSODQR VHSDUDQGR IXHUWHPHQWH D  \ 2 

Dada una función s G U? $ U ^ i 4j, se de¿nen el HSLJUDIR de s , iT s, y el

0.2 Sistemas semi-in¿nitos lineales

13

KLSRJUDIR de s , )TL s , como los conjuntos    % ? n iT s G' 5U m s E%  k k y

   % ? n m s E%  k  )TL s G' 5U k

Diremos que s es FRQYH[D o FyQFDYD según sea convexo el conjunto iT s o bien )TL s . Llamaremos GRPLQLR HIHFWLYR de s , _L4 s, al conjunto _L4 s G' i% 5 U? m s E% n4j  Una función convexa s se dice que es SURSLD si _L4 s 9' > y s E% : 4 para todo % 5 U? . Dada una función convexa propia, s , y un punto % 5 _L4 s , se dice que el vector  es un VXEJUDGLHQWH de s en % si, para todo + 5 U? , s E+  s E% n  E+  % . 

Se dice que s es VXEGLIHUHQFLDEOH en un punto % 5 _L4 s si existe algún subgradiente de s en % y, en el caso de que éste sea único, se dice que s es GLIHUHQFLDEOH en %. La subdiferenciabilidad de s en un punto % 5 _L4 ses equivalente a la existencia  % de un hiperplano no vertical que soporta a iT s en y cada subgradiente s E% de s en %, , está asociado con exactamente uno de estos hiperplanos de soporte    (el que tiene como vector normal a ). La existencia de tales hiperplanos de  soporte no verticales es una propiedad de los puntos de h?| E_L4 s , es decir, s es subdiferenciable en todos los puntos de h?| E_L4 s  [32, Th. 23.4].

 6LVWHPDV VHPLLQ¿QLWRV OLQHDOHV A lo largo de la memoria irán apareciendo repetidamente sistemas lineales de la

14

0. Preliminares

forma j ' i@| %  K| c | 5 A j c 

(0.2)

donde A es un conjunto arbitrario de índices (posiblemente in¿nito), @| 5 U? y K| 5 U para todo | 5 A . En esta sección haremos una recopilación de los principales conceptos y resultados que se van a utilizar en relación con los sistemas semi-in¿nitos lineales (SSIL). Denotaremos por 8 el FRQMXQWR GH VROXFLRQHV de j y diremos que j es FRQVLVWHQWH si 8 9' >. Cuando todos los coe¿cientes de una desigualdad lineal son cero, se dice que esta GHVLJXDOGDG es WULYLDO. El VLVWHPD será WULYLDO cuando todas sus desigualdades sean triviales. Las caras de 8 son los conjuntos 8| ' i% 5 8 m @| % ' K| j, | 5 A , que, de hecho, son caras expuestas de 8 . Si @| 9' f? entonces diremos que | 5 A es un tQGLFH 

SURSLR. Se dice que | 5 A (@| %  K| ) es un tQGLFH SRUWDGRU (GHVLJXDOGDG SRUWDGRUD) de j cuando 8| ' 8 . El FRQMXQWR GH tQGLFHV SRUWDGRUHV lo denotaremos por AS . 

Obviamente, si existe un cierto % 5 U? tal que @| % : K| para todo | 5 A entonces AS ' >. Tales puntos reciben el nombre de SXQWRV GH 6ODWHU. 

Asociados al sistema j se de¿nen los llamados SULPHU \ VHJXQGR FRQR GH PRPHQWRV  G' UL?i i@| c | 5 A j y el FRQR FDUDFWHUtVWLFR

   @| y  G' UL?i c|5A , K|

    f? @|  c | 5 A( g G' UL?i K| 

Cualquier conjunto convexo cerrado no vacío   U? es la intersección de todos los semiespacios de soporte de , de manera que  es el conjunto solución de un cierto sistema lineal j de la forma (0.2). Tal sistema j se llama UHSUHVHQWDFLyQ H[WHUQD de . Llamaremos FRQR GH UHIHUHQFLD de , y lo denotaremos por g E, a la clausura del cono característico de cualquier representación externa de . Esta de¿nición es independiente de la representación considerada, ya que dos representaciones lineales distintas del conjunto  son sistemas lineales equivalentes, y por lo tanto, las clausuras

0.2 Sistemas semi-in¿nitos lineales

15

de sus correspondientes conos característicos son iguales [19, Th. 5.10]. En ocasiones, asociados al sistema j, de¿niremos un par de problemas parametrizados, cuyo parámetro, S, recorre U? . El primero de ellos es de Programación Semi-in¿nita Lineal (PSIL para abreviar), siendo el parámetro el gradiente del funcional objetivo:  ES  W?u S % r@ % 5 8 

Denotaremos por 8 ES el FRQMXQWR ySWLPR de  ES y por  ES su YDORU ySWLPR, con W

 ES ' n4 si 8 ' >. Diremos que un punto % 5 8 es una VROXFLyQ IXHUWHPHQWH W

~QLFD para  ES si existe k : f tal que, para todo % 5 8 , S %  S % n k n%  % n. 



W

W

Obviamente, en este caso, 8 ES ' i% j. W

W

El segundo problema es el dual de  ES (en el sentido de Haar), de modo que el parámetro es el vector de la derecha en el sistema de restricciones, [ [ EA  ( ES  5T b| K| r@ b| @| ' Sc b 5 Un  |MA

|MA

EA 

Denotaremos por [ la función objetivo de ( ES, es decir, [ G Un $ U tal que S [ Eb G' b| K| , por \ES su conjunto factible, por \ ES su conjunto óptimo y por W

|M A

( ES su valor óptimo, acordando que ( ES ' 4 si \ES ' >. Llamaremos VDOWR GH GXDOLGDG, B ES, a la diferencia entre el valor del problema primal y el del dual, B ES G'  ES  ( ES c que siempre es no negativo por el Teorema de Dualidad Débil. Dado un sistema consistente j, se dice que @ %  K es una FRQVHFXHQFLD de j si la 

satisfacen todos los puntos de 8 , es decir, @ 5  K para todo 5 5 8 . En relación con 

este concepto, el /HPD GH )DUNDV H[WHQGLGR [40] caracteriza las desigualdades lineales @ %  K que son consecuencia de un sistema consistente j como aquellas para las que 

se satisface

  @ 5 U* g K

Un caso particular es el /HPD GH )DUNDV H[WHQGLGR SDUD VLVWHPDV KRPRJpQHRV [19, Cor. 3.1.3] que dice que la desigualdad @ %  f es consecuencia del sistema 

16

0. Preliminares

i@| %  fc | 5 A j si, y sólo si, @ 5 U*  

En un sistema consistente, para cada % 5 8 , de¿nimos el FRQMXQWR GH tQGLFHV DFWLYRV A E% G' i| 5 A m @| % ' K| j 

y el FRQR GH UHVWULFFLRQHV DFWLYDV  E% G' UL?i i@| c | 5 A E%j en el punto %. Los resultados más importantes sobre los sistemas ¿nitos de desigualdades lineales sólo son válidos para ciertas clases de sistemas in¿nitos. Consideremos, por ejemplo, el Teorema de Weyl [38] que caracteriza los puntos extremos de 8 cuando mA m 4: % 5 8 es un punto extremo de 8 si, y sólo si, _4  E% ' ?. En [1] se prueba que este resultado se cumple cuando  E%J ' ( E8c % para todo % 5 8 . Un sistema que satisface esta propiedad se dice que es ORFDOPHQWH SROLpGULFR (LOP). Para aquellos problemas PSIL E 

W?u S % 

r@

@| %  K| c | 5 Ac 

cuyo sistema de restricciones es LOP, se han propuesto extensiones del método simplex y del método del gradiente reducido [2]. El Teorema de Karush-Kuhn-Tucker para problemas PL establece que % 5 8 es una solución óptima de (P) si, y sólo si, S 5  E%. En [31] se demuestra que esta a¿rmación también es cierta cuando cualquier desigualdad que de¿na un semiespacio soporte de 8 es también consecuencia de un subsistema ¿nito de j. Los sistemas que satisfacen esta propiedad se llaman ORFDOPHQWH )DUNDV0LQNRZVNL (LFM). Para los sistemas LOP se veri¿ca que 8 es cuasipoliédrico [19, Cor. 5.6.1] y, recíprocamente, todo cuasipoliedro admite una representación LOP [19, Th. 5.11]. Cualquier sistema ¿nito es LOP y cualquier sistema LOP es LFM [19, Th. 5.7]. Un VLVWHPD j es FRQWLQXR cuando A es un espacio topológico compacto y Hausdorff y todos los coe¿cientes, @ E c    c @? E c K E, son continuos en A .

0.2 Sistemas semi-in¿nitos lineales

17

352326,&,Ï1  >19 /HP L @ 'DGR XQ VLVWHPD j VH YHUL¿FD OD VLJXLHQWH

UHODFLyQ HQWUH ODV FODXVXUDV GH \g   f? f? 5 U*  VL \ VyOR VL 5 U* g  

352326,&,Ï1  6L 8 9' > HV HO FRQMXQWR VROXFLyQ GH j ' i@| %  K| c | 5 A j

HQWRQFHV VH FXPSOHQ ODV VLJXLHQWHV SURSRVLFLRQHV

(i) h?| 8  i% 5 U? m @| % : K| c | 5 A qAS ( @| % ' K| c | 5 AS j [19, Th. 5.1(i)] \ 



(ii) _4 8 ' ?  _4 *? U* g [19, Th. 5.8]. 352326,&,Ï1  >19 &RU @ 8Q VLVWHPD FRQVLVWHQWH j WLHQH DO PHQRV XQ

SXQWR GH 6ODWHU VL \ VyOR VL AS ' >

352326,&,Ï1  >19 7K @ &XDOTXLHU VLVWHPD /)0 QR WULYLDO j VDWLVIDFH ODV

VLJXLHQWHV SURSLHGDGHV

(i) _4 8 ' ? VL \ VyOR VL QLQJXQD FRPELQDFLyQ FRQYH[D GH GHVLJXDOGDGHV QR WULYLDOHV GH j GD OXJDU D OD GHVLJXDOGDG WULYLDO (ii) _4 8 ' ?  _4 tT@? i@| c | 5 AS j  $GHPiV VL AS 9' > VH WLHQH @g 8 ' i% 5 U? m @| % ' K| c | 5 AS j  

(iii) h?| 8 ' i% 5 U? m @| % : K| c | 5 A qAS ( @| % ' K| c | 5 AS j  



352326,&,Ï1  >19 7K L @ 'DGR % 5 8  VL _4  E% ' ? HQWRQFHV % HV

SXQWR H[WUHPR GH 8  (VWD FRQGLFLyQ WDPELpQ HV QHFHVDULD FXDQGR j HV /23 352326,&,Ï1  >19 7K

@ 6L 8 9' > ODV VLJXLHQWHV D¿UPDFLRQHV VRQ

HTXLYDOHQWHV

(i) 8 HV DFRWDGR   f? (ii) 5 ?| g     @ ? n m @ % : K SDUD WRGR % 5 8  (iii) ?| g ' 5U K 

(iv)  ' U?  \ (v) H[LVWH XQ VXEVLVWHPD ¿QLWR GH j FX\R FRQMXQWR VROXFLyQ HV DFRWDGR. 352326,&,Ï1  >19 7K $@ 6HD  XQ FRQMXQWR SROLpGULFR GH Pi[LPD GLPHQVLyQ HQ U?  \ FRQVLGHUHPRV XQD UHSUHVHQWDFLyQ OLQHDO GH 

i@ %  K c  ' c    c Rj  

(0.3)

18

0. Preliminares

(QWRQFHV VH YHUL¿FDQ ODV VLJXLHQWHV SURSRVLFLRQHV R

(i) M_  ' ^ M _ , donde M G' i% 5 U? m @ % ' K j ( 

'

(ii) si f es una faceta de , existe  5 ic    c Rj tal que f ' M _ ( y (iii) cada conjunto M _  es una faceta de  si, y sólo si, (0.3) es una representación minimal de  (es decir un sistema sin restricciones redundantes).