Reducción de programas semiinfinitos a programas finitos

Pub . Mat . UAB N° 22 Nov . 1980 Actes VII JMHL REDUCCION DE PROGRAMAS SEMIINFINITOS A PROGRAMAS FINITOS M .A . Goberna, M .A . López Cerdá, J . Pastor Dpto . d e Estadística e Investigación Operativa Universidad de Valencia ABSTRAC .- Given a semi-infinite Programming a finite representation of the feasible duced to a finite one, with allthe subsequent advantagés . We study more in detail the linear thods which allow us to obtain a finitelinear when it is possible . INTRODUCCION Dado el problema de Programación Matemática : cuando S el al Min T (x) ,  xe S CRn recibe frente lineal) que corresponde a T finito . El conjunto C, sobre el que estándefinidas restricciones, se llamaconjuntosoporte . Parael ciones lineales, se tomará C =R n , representándose En lo que sigue excluiremos el caso trivial Problem, if we can find set, the problem is recomptutational case, giving merepresentation, viene definidoa través de infinitas restricciones, S = {x e C/f t (x) < 0, t ET},  T infinito, nombre de Problema de ProgramaciónSemiinfinita problema típico de Programación Finita (lineal o no todas las caso de restricft (x) --_ atx - gt . (PSI) , RELACIONES CONSECUENTES DE UN SISTEMALINEAL Una relación lineal a'x< S es consecuente del sistema {a x< o t , te T, cuando toda solución de este último satisface aquella desigualdad . La caracterización de las relaciones consecuentespermite la eliminación de restricciones redundantes . En el caso finito, tal caracterizaciónconstituye el conocidoTeorema de Farkas . En el casoinfinito hemos logrado dicha caracterización a través de una condición geométrica referida al cono convexoK c generado por Por construcción, es evidente que K c depende de la representación de S . Sin embargo, cualquier otra representación de S tiene asociado el mismo K c . Se prueba así mismo ((3) y (6)) que la consistencia del sistema viene determinada por K c . En efecto : También el cono Kc nos ha permitidocaracterizar los sistemas de Farkas-Minkowski de singular relevancia en la Ti de la Dualidad en PSI((4)) . REPRESENTACION FINITALINEAL EQUIVALENTE Mientras que R 2 todo sistema lineal homogéneo admite una representación finita equivalente, se puede demostrar, por contraejemplo, la imposibilidad de efectuar tal reducción en gene ral si el sistema es no homogéneo o, aún siéndolo, si se considera un espacio de dimensión superior . Es más, incluso en el caso mencionado en primer lugar, la obtención de un método que permita encontrar la representación finita equivalente no es nada fácil ((5) y (6)) . A través del conode relaciones consecuentes podemos así 266 { (a t ,Y t ) , Yt ' S t , t E T} C Rn+l Con mayor precisión, hemos demostrado ((3) y (6)) que : a'x < S es consecuente de {atx <S t , tET, sí y sólo sí (a,s) pertenece a la clausura K c de K c . S, ;, ¿ (D si y sólo sí (~,-1) j í Kc . mismo caracterizaraquellossistemas lineales que admiten una representación finita : El sistema {atx <B t , t e T admite una representación finita sí y sólo sí K c es un cono poliédrico ((5) y (6)) . El resultado anterior es existencial y procedebuscar métodos operativos para la determinación de la representación finita, cuando existe . Una condición suficiente que aportamos, en estadirección, es la siguiente : Si el conjunto {(a t ,B t ), t F T},o su envoltura cerradoconvexa, P, es un polítopo, entonces S admite representaciónfinita . La condición anterior es fácilmente verificable en muchos casos, como por ejemplo cuandoT es un polítopode R my a t , B t son lineales (en muchos problemas reales de PSI, T es un intervalo cerrado) . Proponemos el siguientemétodo de reducción : Se determinan (d i ,di), i=  vértices y direcciones de las artistas infinitasde P . Entonces, el sistema finito dix <d i , i =i, . . . .r, es equivalente al dado . En el caso particular de que T, o su envoltura cerradoconvexa, venga dado a través de un sistemafinito de desigualdades lineales, puede efectuarse la reducción en las siguientes dos etapas : 1.- Aplicando un método de descripción completa se obtendran los vértices y direcciones extremas de T (o de su envoltura cerrado-convexa), que denotaremos t i , i= 1 .. .p . 2 .- El sistema original será equivalente al : at .x<< Bt .' 11 El método de reducción último, no supone la consistencia del sistema original, por lo que puede emplearse comotest de consistencia paraestetipo de sistemainfinitos (métodos para decidir la consistencia de un sistema linealfinitopueden encontrarse en (1)) . APORTACIONES AL CASO NO-LINEAL Si la familiasde funciones ft , t FT, es acotadasuperiormente en todos los puntos de C, se puede escribir, en teoría : des : S = {x e C/sup . ft (x) < 0 } teT Si además, el supremo es accesible en todos los puntos, se puede expresar . S = {x c C/m (x) <O},donde m (x) representa la funciónmáximo de la familia sobre C . Este sugestivo tratamiento conlleva diferentesdificulta1 .- Si bien es cierto que m(x) conserva, bajo ciertascondiciones, la cuasiconvexidad, la convexidad yla continuidad, no lo es . menos que no se preserverá la cuasiconvexidad explícita ni la diferenciabilidad, siendoesta última propiedadespecialmenterelevante en Programación Matemática . En (2) y (5) se precisan todas estas .cuestiones, aportándose ejemplos en losque se calibra el alcance de .este tratamiento . - En cual nniar caco,  la nhtan~iñn de rn(x) es comDutacionalmen - te muy compleja (equivale a resolverinfinitos problemas de optimización, sobre T) . Otra aproximación posible al problema nos permite afirmar, bajo condiciones muy generales, la existencia de una representación finitade S mediante una función convexa en Rn (y por lo tanto continua) y un número finitode lineales . Con exactitud : sólo se requiere de las funciones f t que sean cuasiconvexasy semicontínuas inferiormente . Finalmente, parael caso particular de que T sea un poliedro de R m , y las funciones ft sean cuasiconvexas en T, S admite también una representación finita que involucraexclusivamente a las restriccionescorrespondientes a los vértices de T . Los dos últimos resultados se encuentran también demostrados en (2) y (5) . BIBLIOGRAFIA 1 . Fan, K . ; On Systems of LinearInequalities, Annals of Mathe - matics Studies, 38-1956 2 . Goberna,M .A . ; Nuevos resultados en la T9 de la Programación Semiinfinita No-lineal . Tesis doctoral . Universidad de Valencia, 1979 . 3 . Goberna,M .A ., López,M . y Pastor,J . ; Infinite linear Inequality Systems : Consequence Relations ans Consistency, Sometido a Mathematics foz Operations Research . 4 . Goberna,M .A ., López,M . y Pastor,J . ; Farkas-Minkoaski Systems in Semiinfinite Programming, sometidoa Mathematics forOpe - rationsResearch . 1980 . 5 . Goberna,M .A ., López,M . y Pastor,J . ; Representación finitade Sistemas de infinitas inecuaciones,sometido a Trabajos de Estadística e 1 .0 . 1980 6 . Pastor,J . ; i Aportacionesa la Ti de la Programación Semiinfinita'Lineal, Tesis doctoral . Universidad de Valencia .1979 .