Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

ii-*'-

i li r I

'

"'

21

Estabilidad en Programación Semi-Infinita Lineal

Memoria presentada por Juan Parra López para optar al grado de Doctor en Ciencias Matemáticas, realizada bajo la dirección de los doctores D. Marco Antonio López Cerdá y D. Maxim Ivanov Todorov.

Alicante,1999

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

_ffi

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

D. MARCO AIITONIO LÓPr,Z CERDÁ Catedráticode Estadísticae InvestigaciónOperativade la Universidadde Alicante,y D. MA)ilM M}{OV

TODOROV, Miembro de la AcademiaBúlgara de

lasCiencias,

CERTIFICAN: Que la presentememoriaEstabilidad en Programación Semi-Infinita Lineal, ha sido realizadabajo su dirección,en el Departamentode Estadísticae InvestigaciónOperativade la Universidadde Alicantq por D. Juan Parra Lbpez, y constifuyesu tesis para optar al grado de Doctor en Ciencias Matemáticas.

Y paraque conste,en cumplimientode la legislaciónügente, firman el presente certificado en Alicante, a treinta de noviembrede mil novecientosnoventay ocho.

Fdo.:MarcoA. López

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Fdo.:Ma:

bl , t e T}.

Muchos problemas de PSIL tienen coeficientes cuyos valores, bien son sólo aproximadamente conocidos, o bien tienen que ser redondeados en los procesos computacionales. Por lo tanto, en realidad estamos considerando un problema diferente'r!:

(c',ot), próúmo al original,'Ít :

(",o). Para medir el tamaño de

las perturbaciones, introducimos en el espacio paramétrico de los problemas una di,stanci,aertendi,da ó : II x II --+ [0, **],

-

::-* 6 (n,.,tr)

{ll"t

d o n d el l " l l - : m a x { 1 " ,,1i :

que viene dada por

ll(;)-(fr) ll-)'

sup¿er "ll- ,

I , . . . p } ,s i e n d to:

( * r , . . . , * o )e' l R ep, € N .

- (;:)ll_ definea su vezuna süp¿e? llt;il distanciaextendidad en el espacioparaméticoasociado@ = (lR" x R)" de todos Notemosquela aplicación(ot,o) H

los sistemasde desigualdades linealescuyo conjunto de índiceses ?. (II, ó) y (O, d) sonespaciostopológicosde Hausdorff,cuyastopologíassatisfacen el primer axioma de numerabilidad(esto es, la convergenciapuede caracterizarse ya que cada punto poseeuna basenumerablede entornos).ó mediantesucesiones, y d describenla topologíade Ia convergenciauniforme en II y O, respectivamente. Si 7 es un espaciocompactode Hausdorffy las funcionest v-+a¿ y ú H b¿son continuas,se dice que el probleman (o el sistemaa) es conti,nuo.En este caso, denotandopor flo (resp. O,) al conjunto de los problemasde PSIL (resp. sistemas) continuos,(fI,, ó) (resp. (O", d)) se convierteen un espaciométricocompleto. A Io largo de la memoria trataremos de caracterizar ciertas propiedadesde estabilidad de o y de n'. En concreto,estaremosespecialmenteinteresadosen el estudio de la semicontinuidadinferior y superior de Ia funci,ón conjuntofacti,ble, F,la funci,ónualor ópti,mo,d, y Ia funci,ónconjuntoópti,mo, F". La primera, f : II * 2R", asignaa cada problemazc(resp. a cada sistemao, abusandode la notación) at, conjuntofactible -o conjuntosolución-F; esto es, .F (r) : F (resp. F ("):

F ). r.9: fI ---+[-*,

**],

asociaa cadaproblemar sr ualor ópti,mou (esto

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

0.1. Notacióny defr.niciones

es, t9(n') :u),

T2

conviniendoqueT9(zr): *oo cuando F:0

(en cuyo casodiremos

que r, o o, es 'i,nconsi,stenüe). Si t9(z') : -oo, diremos que r es no acotado. Por rlltimo, F* : II -r 2R" hace corresponder a cada problema a su (posiblemente vacÍo) conjunto ópt'imo,representadopor F* (esto es,F* (*) : F-). En lo que sigue, fI" (resp. O") representará el conjunto de los problemas (resp. sistemas) consi,stentes(er' € ["

€

F *. A 0 } , y eI conopolar posi,ti,uo de X, Xo, dadopor Xo: {ge reolA'r> 0paratodor €X). En ocasiones,utilizaremos también eI espaciode li,neal,idadde X (supuestoX convexo),dadopor lin(X) :: O* (X) n l-O* (X)] . Convendremos que cone(X) siempre contiene al vector nulo y, por tanto, cone(A) : {0p}. Las normas ezclldeay de Chebysheu de r € IRpseránrepresentadas por ll"ll v ll"ll- , respectivamente,y la distanciaeuclídeade un punto z al conjuntoX (l 0) es d(r, X) :: inf {llr - All , A € X} . La bolauni,dadabi,erta,en JRp,para Ia norma euclídeaserá representadapor B, mientrasque JR..denotaráal intervalo [0,+oo). En el aspecto topológico,si X es un subconjuntode cualquierespaciotopológico,i,nt(x), ct(X)

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

0.1. Notacióny defrniciones

13

y bd(X) denotarán al i,nterior, Ia clausuray Ia frontera de X, respectivamente. Finalmente,lim, debeinterpretarsecomolimr--. Si {X,} esuna sucesiónde conjuntosno vacíos,en JRP, Iim inf, X, (resp. Iim sup, X,) es el conjunto de todos los lÍmites (resp. puntos de aglomeraciónl)de todas las posiblessucesiones como {*'} , r' e Xr, r : L,2,..., y puedecaracterizarse el conjunto de los puntos r tales que cada uno de sus entornosintersectaa todos los X, excepto a un número finito de ellos (resp. intersecta a una infinidad de los X"). Se dice que {Xr} convergea X, en eL senti,dode Pai,nleué-Kuratowski, (véase,por ejemplo,[29])si X :liminf, X,:limsup, Xr, encuyocasoescribiremos X :Iir¡,- X,. Seguidamenteconsideramosalgunasnocionesde continuidadpara aplicaciones puntoaconjunto.Siy y Z sondosespaciostopológicos,y M:))

-+22 esunaapli-

cación punto a conjunto, fijaremosnuestra atenciónen las siguientespropiedades d eM : Si ambosespaciossatisfacenel primer axioma de numerabilidad,diremosque M e s ce rva d a e n g€ ) si p a r acualesquier asucesiones { y' } cy

y { 2,} c z

verificandolímry' : gr,lim, z' : z y z' e M(A'), r : I,2,..., setienez e M(ú. La aplicaciónM es sem,icontinua,inferioremente (abreviadopor lsc2)en y e !, en el sentidode Berge,si para cadaconjuntoabierioW c Z tal que W nM(ü * A existe nn entorno abierto U C y, del punto y, tal que W n M(y') I A para todo

at€u. M se dice semi,contí,nua superiormente (abreviado usc3) en A e y si para cada conjunto abierto W c Z tal que M(g) CW U, ta| que M(yl)

extste un entorno abierto de g en)),

CW para todo gr1e U.

En el capítulo 1 de la memoria estudiaremos estas nociones de continuidad para la función conjunto factible F, y en el capÍtulo 2 lo haremos para.F*. lllamaremos punto d,eaglomeración de una sucesión a todo punto que pueda expresarse como lfmite de alguna subsucesión suya. 2Del inglés lower sem,icontinuous. sDel inglés upper sem,icontinuous.

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

0.2. Henamientasbasicas

L4

O.2 f{erramientas básicas Esta brevesecciónrecogealgunasherramientasdel Análisis Convexoque utilizaremos constantementea Io largo de Ia memoria. Dado un sistemaconsistenteo p {alr } il, t € T} , con conjunto factible F, se dice que a'n ) b es rtna consecuenc'ia de a si la satisfacentodos los puntos de F; es decir, a'z ) ó para todo z € F. En relacióncon esteconcepto,er Lema d,e Farkas para sistemasno homogéneos([aa]) caracterizalas desigualdadeslineales a'r ) ó que son consecuencia de un sistemaconsistente6 p {a!rr>br, te T} como aquellasque satisfacen

, t€r' (:i)})) (;) . "t("onu({(fr)

(0.2.1)

Introduciendoel cono, R!), de todas las funciones) : ? --+ IRa que toman valorespositivos sólo en una cantidad finita de puntos de ?, (0.2.1) equivalea la existenciade un par de sucesiones {)'} c Rtt) y {tt,} clR-., tales que

(;)

:rim"{t^r(;) .,,(1)

},

d o n d e) ' : ( ) í ) r . 7 , r : 1 , 2 , . . . Asociaremos al sistema a los conos M y K, denominados respectivamenteprimer cono de momentos y cono característi,code o, definidos por

M::cone({a¿,

t€T¡),

((/"r\ K :: cone

\t \r'/

j tr -t mt. ; / 0 " \ ' l j \ \-r) )

Debido al Lema de Farkas, cl(K) recibe en ocasionesel nombre de cono de las relacionesconsecuentes d,eo. El cono M,,por su parte, resultade gran utilidad a la hora de caracterizarla acotacióntanto del conjunto factible como del conjunto óptimo del problema. Es inmediato comprobarque, si n es consistente,entoncesO* (F) : Mo. La

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

0.3. Ejemplo: El dual lagrangianocomo un problemasemi-infr.nito

15

acotaciónde F puedeestablecerse comosigue. Proposición 0.2.1- [12,Th. 9.3] ^9C r € II", las si,gui,entes cond,ici,ones son equi.ualentes: (i) .F es acotado; (ii) M - rR,;

(iii)o+ (r) : {0"}. De cara al estudiode la acotaciónde F*, resulta en generalde interéscorsiderar Ios conjuntosde ni,uel(inferior) de r, L(a) ,: {, € F I Cr 1a}, o e IR.. Se compruebainmediatamenteque todos los conjuntosde nivel no vacÍosde n-tienen el mismoconode recesión,el cual vienedado por {a¿, t eT;

-"}o . La acotación

de f'* se caracterizacomo sigue. Proposición 0.2.2 [12,Cor. 9.3.1]Sea¡r € fI". Entoncesson equ,iualentes: (i) F- es acotadoy no uacío; ( i i ) {a ¿ , t e T ; -c}':

{0 ,};

(iii) c e int (M) . En otro orden de ideas,en diversassituacionesa lo largo del texto utilizaremos la siguientepropiedad: si X I 0 es un conjunto convexoy cerrado, y i É X, entoncesexiste una única mejor aprorimaci,óndei en X. Ademrís,denotandopor r a estamejoraproúmación,severificala relación(" - i)' n > (r - i)' * paratodo r Q X. En particular, si X es el conjunto factible de un sistemade desigualdades lineales,Ia relaciónanterior es una consecuencia de dicho sistema.

0.3

Ejemplo: El dual lagrangiano como un problema semi-infinito

En esta secciónpretendemosilustrar algunosde los conceptosanterioresen una aplicaciónde la PSIL, inspiradaen [1, Sec.6.4].

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

0.3. Ejemplo: El dual lagrangianocomo un problemasemi-infrüto

16

Consideremosel problema (primal) de ProgramaciónNo Lineal (P) Inf / (¿) s.a g(¿)0-. EI problema (D') puede tranformarse en el siguiente problema de PSIL. Ejemplo

0.3.1- Conservando Ia terminologÍa de los prírrafos anteriores, considere-

mos el problema 7( :

Inf. {c'r I olr, > b¿, t e T} ,

donde hemos realizado el cambio de notaciórr lt :: ()) e R-*1, y cuyos elementos describimos a continuación: T :: C U {tt, s2,..s*}, donde sl, s2,...s* son rn puntos distintos en IR' que no pertenecen a C. Nótese que ?, con la topología inducida por IR', es compacto; [/o(t)\ t-._/0-\. ': \-t/i

a^t t_l :

t'['EL/ ca

\ .t/' ll?), t:si,r1j1m,

1 /''\ \

\U,/

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

(

-f ttl , t€c )bt::l lo, t:si,L"o f', C lim sup rlr¡ Fr se verifica en general, se concluye que f' : Iimr>"' Fr. Supongamos ahora que se tiene (ii) y F no es lsc en d. Existe entonces un conjunto abierto W tal que F nW

+ 0, mientras que para cada r € N puede

elegirseun or de forma qte d(o,,o) < Llr y F, nW r e FñW,

:

A. En consecuencia,si

para cualquier rs que corsideremos,r t' liminf ,¿,sF,. En resumen,

Iimro, - o y F t'Iiminf,.>,' Fr, para cualquier rs, contradiciendo la hipótesis. Seguidamenteprobaremos (i) 0 tal que FL1W + A, siendoo1 i:

{o!rr>bt-lV,

teT).

Como Fl : F("r)

C Fss, obtenemosque

Fssñ W + A. En conclusión, hemosprobadoqueF nW * 0 implicaFssn W + A,

Tesis doctoral de la Universidad de Alicante. Tesi doctoral de la Universitat d'Alacant. 1999

Estabilidad en Programacion Semi-infinita lineal. Juan Parra Lopez.

23

1.2. Semicontinuidadinferior de la función conjunto factible

de dondese deduceque F c ct (Fss) . La inclusión contraria es inmediata,ya que FssCFyF

e s c e r r a d oI .

En [13, Th. 3.1] se añadea la relaciónde condicionesequivalentesdel teorema de F (en el sentidode Robirson, [27])en d, que vienedescrita I.2.L Ia R-estabi,ti,dad comosigue: Para todo ñ e F existeun par de númerospositivos0 y e tales que se verifica d (ñ,Ft) S pV (l,or) d( o1,o) < e, donded( ñ,Ft) {@l )'r>b !, t€T} satisfaciendo representala distancia euclÍdeade ñ a F1 (conviniendoque esta distancia es *m p a r at o d o o t:

si Ft :6¡, t

V(t,o) :: **

(ul- (ol)'t))e ¡0,+*1 {0, :EF

es una medida de la infactibilidad de ñ respectode o1. En Ia definiciónanterior, B dependedel punto ñ elegido. En el siguiente lema se proporciona una condici,ónuni,forme de regulari,dad métrica de un carácter análogoa la R-estabilidad,pero que involucra a dos sistemas cualesquieraen un entorno suficientementepequeñode o, y en Ia que el escalarB dependesólo de a. En contrapartida,hemosde exigir que F : F (o) esté acotado. Este lema será fundamentala la hora de establecercierta propiedadde Iipschitzianidadlocal de Ia función valor óptimo en el capitulo 2. Lema L.2.3 Seao € O". Si,F es Isc en o y F es antado, entoncesexisteun par posi,ti,uos € A P talesquesi d(o¿,o) 1e,'i: de escalares

L,2, se t'iene,para cada

ri e F¡, d ( * i , P n 0 ta l q u e F r c F +B

siem pr eque d( o1,o)