Resúmenes

Optimización

Ordenados alfabéticamente por título.
Por modificaciones, comunicarse al correo del Noticiero UMA (uma.noticiero@gmail.com).

Análisis de sensibilidad de problemas de equilibrio. Aplicación a la estimación de la demanda de tráfico.

Pablo Andrés Lotito (PLADEMA-CONICET, pablo.lotito@gmail.com); Lucas Corrales (PLADEMA-CONICET, corrales.lucas@gmail.com); Lisandro Parente (CIFASIS-CONICET, lisandroparente@gmail.com)

Dado un problema de optimización parametrizado en una restricción, nos interesa calcular la variación de la solución (o soluciones) óptima(s) respecto del parámetro. Esto resulta de utilidad para resolver el problema de estimación de matrices origen-destino en una red de tráfico vehicular [4]. Este último es un problema binivel que presenta minimización cuadrática en el nivel superior y restricciones de equilibrio de Wardrop, expresadas a través de una inecuación variacional, en el nivel inferior. Específicamente, dado un vector de demandas desactualizado $\bar{d}$ y un conjunto $\tilde A$ de arcos donde se puede medir el flujo actual, se presenta el siguiente problema: \[ \min \sum_k\rho_k(d_k-\bar{d}_k)^2+\sum_{a\in \tilde{A}}\beta_a(x_a-\bar{x}_a)^2 ,  \  \  (1)\] sujeto a \[ t(x)^T(x-x')\geq0,\,\, \forall x'\in\omega(d)  \  \  (2)\] donde $t(x)$ es la función de costo por arcos para el vector de flujos $x$ y $\omega(d)$ es el conjunto de flujos por arco que satisfacen el vector de demanda $d$, expresado por restricciones lineales de igualdad y desigualdad. Las condiciones KKT de la IV (2) permiten reformular las restricciones como restricciones de complementariedad. Los métodos que ya hemos considereado podemos dividirlos en enfoques que reemplazan las retricciones de equilibrio por su formulación KKT (método de lifting) y métodos de descenso de la función objetivo definida implícitamente en $d$ (métodos de aproximación del gradiente y de restauración inexacta). En este caso también presentamos un método de descenso donde caracterizamos la derivada direccional de la solución óptima del problema de equilibrio como solución de un problema de optimización asociado, basado en el análisis de sensibilidad mencionado al principio [2]. Presentamos ejemplos numéricos en redes standard de pequeño y mediano porte, contrastando los resultados heurísticos de [1] y [3].

Bibliografía

[1] Codina,E. y Barceló, J., Adjustment of O-D trip matrices from observed volumes: An algorithmic approach based on conjugate directions, \emph {European Journal of Operational Research}, vol. 155 (2004), pp. 535-557.

[2] Josefsson, M. y Patriksson, M., Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design, Transportation Research Part B: Methodological, vol. 41 (2007), Nro. 1, pp. 4-31.

[3] Lundgren, J.T. y Peterson, A., A heuristic for the bilevel origin-destination-matrix estimation problem, Transportation Research Part B, vol. 42 (2008), pp. 339–354.

[4] Patriksson, M.,Sensitivity analysis of traffic equilibria, Transportation Science, vol. 38 (2004), Nro. 3, pp. 258-281.

Resumen en PDF

Descenso estocástico para problemas de control óptimo con incertidumbre

Lisandro Parente (CIFASIS-CONICET. FCEIA-UNR, parente@cifasis-conicet.gov.ar); Laura Aragone (CIFASIS-CONICET. FCEIA-UNR, aragone@cifasis-conicet.gov.ar); Justina Gianatti (CIFASIS-CONICET. FCEIA-UNR, gianatti@cifasis-conicet.gov.ar); Pablo Lotito (CONICET, UNCPBA, plotito@exa.unicen.edu.ar)

En este trabajo se consideran problemas de control óptimo de tipo minimax que involucran parámetros de incertidumbre tanto en la dinámica como en la función objetivo. Se propone su resolución numérica mediante un esquema que en cada iteración presenta tres etapas: generación de un muestreo aleatorio, búsqueda de una dirección de descenso y actualización por un paso de tipo Armijo. Bajo hipótesis de crecimiento del muestro, se obtienen resultados de convergencia sobre una adecuada clase de subsucesiones. Se presentan implementaciones en ejemplos sencillos comparando los resultados con métodos de promedio muestral.

Resumen en PDF

Diseño de componentes fluidodinámicas mediante el Método de Optimización Topológica

Natalia N. Salva (CNEA-CONICET-UNComa, natalia.salva@yahoo.com.ar); L.c. Ruspini (Petricore Norway AS; Norway, leonardo.ruspini@gmail.com); E. Dari (CNEA-CONICET- UNCuyo, darie@cab.cnea.gov.ar); C. Padra (CNEA-CONICET-UNComa, padra@cab.cnea.gov.ar); G. Paissan (CONICET-UNComa, paissan@cab.cnea.gov.ar)

En esta comunicación se presentán aplicaciones del Método de Optimización Topológica a problemas fluidodinámicos en 2 y 3 dimensiones. Se utilizó el método de elementos finitos como forma de discretización de los problemas, desarrollando un código computacional propio. A diferencia de otros trabajos, se consideró el término no lineal de las ecuaciones de Navier- Stokes, resolviéndolo a través de un método iterativo. Además se analizaron diferentes métodos de extracción de elementos, a partir de los cuales se cambia la topología del dominio.

Resumen en PDF

Equilibrios Fuertes de Stackelberg Estacionarios en Juegos Estocásticos con Descuento

Eugenio Della Vecchia ( FCEIA - UNR. Rosario. Argentina. , eugenio@fceia.unr.edu.ar); Víctor Bucarey ( ULB - Computer Science Department, Bruselas, Bélgica. Departamento de Ingenieria de la Universidad de Chile, Santiago, Chile. , vbucarey@ulb.ac.be); Alain Jean-marie (Inria, LIRMM, University of Montpellier, CNRS, Montpellier, Francia. , alain.jean-marie@inria.fr); Fernando Ordóñez (Departamento de Ingeniería Industrial, Universidad de Chile, Santiago, Chile., fordon@dii.uchile.cl)

En este trabajo nos abocamos al estudio de existencia y cálculo de equilbrios fuertes de Stackelberg (SSSE, Strong Stationary Stackelberg Equilibria) en estrategias estacionarias para juegos estocásticos con descuento a suma general.

Exhibimos clases de juegos para los cuales estos equilibrios existen y mostramos mediante contraejemplos que no existen en el caso general.

Definimos operadores de Programación Dinámica apropiados para este concepto de equilibrio y estudiamos los Puntos de Fijos de tales operadores, que llamamos equilibrios de punto fijo (PPE, Fixed Point Equilibria). Mostramos que SSSE y FPE coinciden para ciertas clases de juegos estocásticos. En particular introducimos la clase de juegos con seguidores miopes para la cual ambos conceptos de equilibrios coinciden.

Finalmente analizamos el comportamiento de los algoritmos de Iteración de Valores, Iteración de Políticas y formulaciones de Programación Matemática para el cáclulo y aproximaciones de los equilibrios definidos.

Resumen en PDF

Identification of the anti-diffusion coefficient for the linear Kuramoto-Sivashinsky equation

Diego Gajardo (Universidad Técnica Federico Santa María, diego.gajardomi@gmail.com); Alberto Mercado (Universidad Técnica Federico Santa María, alberto.mercado@usm.cl); Juan Carlos Muñoz (Universidad del Valle, juan.munoz@correounivalle.edu.co)

In this talk, we consider the inverse problem of recovering the second-order coefficient in the linear Kuramoto-Sivashinsky equation from the knowledge of the solution in final time. We formulate the inverse problem as a regularized nonlinear optimization problem, show one local stability result and developed a scheme for the reconstruction of the parameter. We present numerical simulations showing the accuracy of the method.

Resumen en PDF

Un algoritmo determinístico para optimización global para minimización con restricciones y sin derivadas

Johanna Analiz Frau (CIEM-FAMAF, jfrau@famaf.unc.edu.ar); Elvio Ángel Pilotta (CIEM-FAMAF, pilotta@famaf.unc.edu.ar)

En este trabajo se presenta un nuevo algoritmo para minimización global con restricciones generales. El mismo está basado en el algoritmo DIRECT (DIviding RECTangles) propuesto por Jones [1] e inicialmente formulado para un problema con restricciones de cotas en las variables. En cada iteración, el dominio es particionado en subrectángulos y un subconjunto de ellos es elegido (de acuerdo a un criterio conveniente) para realizar una nueva partición en la siguiente iteración. Este trabajo fue extendido al caso general por Jones en el año 2001 [2] utilizando una función auxiliar, que combina información de la función objetivo y de las restricciones lineales y generales, para determinar una mejor aproximación al minimizador global.

Por otro lado, recientemente Paulavičius et. al. [3] presentaron una variante de DIRECT, llamada BIRECT (BIsecting RECTangles), también para problemas de minimización global con cotas en las variables. La misma está basada en una estrategia de partición diagonal con el objeto de reducir la cantidad de subrectángulos considerados.

El algoritmo para minimización global general propuesto en este trabajo combina las ideas de Jones con la técnica de partición de rectángulos del algoritmo BIRECT. La formulación algorítmica involucra diferentes subproblemas de gran complejidad computacional a fin de lograr una implementación eficiente y robusta. Con el objetivo de evaluar la performance de tal implementación, se realizaron diferentes experimentos numéricos en los cuales se consideraron diversos problemas disponibles en la literatura así como también distintas elecciones de parámetros algorítmicos.

Bibliografía

[1] D. R. Jones. Lipschitzian optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, v.79, pp. 157–181, 1993.

[2] D. R. Jones. Direct Global Optimization Algorithm, Floudas C.A., Pardalos P.M. (eds) Encyclopedia of Optimization. Springer, Boston, MA , 2001.

[3] R. Paulavičius, L. Chiter and J. Žilinskas. Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants, Glob Optim. v. 71, pp 5–20, 2018.

Resumen en PDF

Un esquema numérico para inecuaciones variacionales estocásticas.

Emelin Buscaglia ( CIFASIS-CONICET, UNR, emelinbus@gmail.com); Pablo Andrés Lotito (CONICET, UNCPBA, pablo.lotito@gmail.com); Lisandro Parente ( CIFASIS-CONICET, UNR, lparente@fceia.unr.edu.ar)

En este trabajo abordamos la resolución numérica de inecuaciones variacionales estocásticas en la formulación dada por Rockafellar y Wets [Stochastic variational inequalities: single-stage to multistage, Math. Program., Ser. B, Springer, 2016]. Presentamos un algoritmo que extiende el esquema introducido por Rockafellar y Sun [Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging, Math. Program., Ser. B, Springer, 2018], basado en métodos de punto proximal. Nuestro enfoque permite resolver los subproblemas en forma inexacta con una condición de tolerancia computacionalmente implementable. Mostramos resultados de convergencia bajo hipótesis usuales y presentamos algunos ejemplos numéricos preliminares en problemas de complementariedad no lineales.

Resumen en PDF

Una implementación en paralelo de un problema de asignación de tráfico

Nicolas Jares (FAMAF-UNC, nico.jar@gmail.com); Damián Fernandez Ferreyra (FAMAF-UNC CIEM-CONICET, dfernandez@unc.edu.ar); Lisandro Parente (FCEIA-UNR CIFASIS-CONICET, lparente@fceia.unr.edu.ar)

En este trabajo se desarrollaron estrategias de paralelización aplicadas a la implementación computacional del modelo propuesto en [1] para diseñar un ruta de colectivo. Dicho modelo está basado en una variante del equilibrio de Wardrop.

El modelo propuesto requiere conocer la demanda de pasajeros, descripta como un conjunto de pares Origen-Destino (OD) $(p,q)$ que tienen asociadada una cantidad positiva. Luego, se necesita conocer todos los caminos que unen $p$ con $q$ para cada par. Con eso se construye un problema de asignación de tráfico y se resuelve con el método del gradiente proyectado. El minimizador de ese problema indica las aristas del grafo que debería usar la nueva línea de colectivo.

Las etapas de mayor intensidad computacional son el cálculo de todas las rutas posibles para cada par, y las proyecciones que se realizan durante la optimización. Afortunadamente, ambas resultaron ser paralelizables. Se expondrán las ideas usadas para la implmentación en paralelo de la búsqueda de rutas [2] y de las proyecciónes necesarias.

10pt

keywords: OpenMP - Probemas de Asignación de Tráfico - Optimización No Lineal

AMS: 65Y05 - 90B20 - 90C90

10pt

Referencias

[1] {\sc{Nicolás Jares}}, Diseño de Rutas y Paradas óptimas para el Transporte Público de Pasajeros, Trabajo Especial de Grado, FAMAF-UNC, 2015

[2] {\sc{Nicolás Jares}}, Paralelización en búsqueda de rutas en grafos, VII MACI 2019, Actas del VII Congreso de Matemática Aplicada Computacional e Industrial, Rio Cuarto, Mayo 2019, pp. 77-80, ISSN: 2314-3282.

Resumen en PDF

UMA SOMACHI
Ir arriba