MINOS (software de optimización)

MINOS es un paquete de software Fortran para resolver problemas de optimización matemática lineales y no lineales . MINOS (Modular In-core Nonlinear Optimization System) puede utilizarse para programación lineal, programación cuadrática y funciones objetivo y restricciones más generales, así como para encontrar un punto factible para un conjunto de igualdades y desigualdades lineales o no lineales. ^{[ 1 ]}

MINOS fue desarrollado inicialmente por Bruce Murtagh y Michael Saunders , principalmente en el Laboratorio de Optimización de Sistemas del Departamento de Investigación Operativa de la Universidad de Stanford. ^{[ 2 ]} En 1985, Saunders recibió el primer premio Orchard-Hays ^{[ 3 ]} de la Sociedad de Programación Matemática (ahora Sociedad de Optimización Matemática ) por su trabajo en MINOS. A pesar de ser uno de los primeros solucionadores de optimización con restricciones de propósito general, el paquete sigue siendo muy utilizado. MINOS es compatible con los sistemas de modelado AIMMS , AMPL , APMonitor , GAMS y TOMLAB . Además, sigue siendo uno de los solucionadores más utilizados en el servidor NEOS ^{[ 4 ] [ 5 ]} y en GAMS . ^{[ 6 ]}

Idealmente, el usuario debería proporcionar los gradientes de las funciones no lineales. (Esto es automático en la mayoría de los sistemas de modelado mencionados anteriormente). Si faltan algunos o todos los gradientes, MINOS los aproximará mediante diferencias finitas, pero esto podría ser lento y menos fiable. Si la función objetivo es convexa y las restricciones son lineales, la solución obtenida será un minimizador global. De lo contrario, la solución obtenida podría ser un minimizador local.

Para la programación lineal, se utiliza un método simplex primal de dos fases . La primera fase minimiza la suma de las infactibilidades. Para problemas con restricciones lineales y una función objetivo no lineal, se emplea un método de gradiente reducido. Se mantiene una aproximación cuasi-Newton a la matriz hessiana reducida para obtener las direcciones de búsqueda. Este método resulta más eficiente cuando existen numerosas restricciones o límites activos en la solución.

Para problemas con restricciones no lineales, se utiliza un método lagrangiano con restricciones lineales. ^{[ 7 ]} Este método implica una secuencia de iteraciones principales, cada una de las cuales resuelve (quizás de forma aproximada) un subproblema con restricciones lineales. El objetivo del subproblema es un lagrangiano aumentado , y las restricciones del subproblema son linealizaciones de las restricciones no lineales en el punto actual.

MINOS está diseñado para problemas dispersos de gran tamaño. No existe un límite fijo para el tamaño del problema. La mayor parte del almacenamiento de trabajo se encuentra en un único array de doble precisión (que debe ser suficientemente grande). El código fuente es compatible con todos los equipos científicos que dispongan de un compilador Fortran.

• BA Murtagh, MA Saunders (1982). "Un algoritmo lagrangiano proyectado y su implementación para restricciones no lineales dispersas" (PDF) . Programación matemática . 16 : 84–117 .

• Laboratorio de Optimización de Sistemas, Universidad de Stanford (SOL).
• MINOS 5.5 - Descripción - Distribuidores del software.