Un método de punto interior no arquimediano y su aplicación a la programación cuadrática multiobjetivo lexicográfica
Autores: Fiaschi, Lorenzo; Cococcioni, Marco
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Un método de punto interior no arquimediano y su aplicación a la programación cuadrática multiobjetivo lexicográfica
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Primal-dual
Método de puntos interiores
No arquimediano
Convergencia
Problemas de optimización
Multi-objetivo lexicográfico
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 20
Citaciones: Sin citaciones
Este trabajo presenta una implementación generalizada del método de punto interior primal-dual (IPM) inviable lograda mediante el uso de valores no arquimedianos, es decir, números infinitos e infinitesimales. La versión extendida, llamada aquí IPM no arquimediano (NA-IPM), se demuestra que converge en tiempo polinómico a un óptimo global y es capaz de manejar la inviabilidad y la no acotación de manera transparente, es decir, sin considerarlas como casos límite: mediante una incrustación suave (adición de dos variables y una restricción), el NA-IPM gestiona implícita y transparentemente su posible presencia. Además, el nuevo algoritmo es capaz de resolver una mayor variedad de problemas de optimización lineal y cuadrática que su contraparte estándar. Entre ellos, el problema multiobjetivo lexicográfico merece especial atención, ya que el NA-IPM supera los problemas que tienen las técnicas estándar (como la escalarización o el enfoque preventivo). Para respaldar las propiedades teóricas del NA-IPM, el manuscrito también muestra cuatro casos de prueba de programación no arquimediana lineal y cuadrática donde se verifica la efectividad del algoritmo. Esto también destaca que el NA-IPM no es solo un algoritmo simbólico o teórico, sino realmente una herramienta numérica concreta, allanando el camino para su uso en problemas del mundo real en un futuro cercano.
Descripción
Este trabajo presenta una implementación generalizada del método de punto interior primal-dual (IPM) inviable lograda mediante el uso de valores no arquimedianos, es decir, números infinitos e infinitesimales. La versión extendida, llamada aquí IPM no arquimediano (NA-IPM), se demuestra que converge en tiempo polinómico a un óptimo global y es capaz de manejar la inviabilidad y la no acotación de manera transparente, es decir, sin considerarlas como casos límite: mediante una incrustación suave (adición de dos variables y una restricción), el NA-IPM gestiona implícita y transparentemente su posible presencia. Además, el nuevo algoritmo es capaz de resolver una mayor variedad de problemas de optimización lineal y cuadrática que su contraparte estándar. Entre ellos, el problema multiobjetivo lexicográfico merece especial atención, ya que el NA-IPM supera los problemas que tienen las técnicas estándar (como la escalarización o el enfoque preventivo). Para respaldar las propiedades teóricas del NA-IPM, el manuscrito también muestra cuatro casos de prueba de programación no arquimediana lineal y cuadrática donde se verifica la efectividad del algoritmo. Esto también destaca que el NA-IPM no es solo un algoritmo simbólico o teórico, sino realmente una herramienta numérica concreta, allanando el camino para su uso en problemas del mundo real en un futuro cercano.