Paquete de software para optimización restringida?

21

Estoy buscando resolver un problema de optimización restringida donde conozco los límites de algunas de las variables (específicamente una restricción en recuadro).

\arg min_{u} f (u, x)

$\arg \min_u f(u,x)$

sujeto a

c (u, x) = 0

$c(u,x) = 0$

a \leq d (u, x) \leq b

$a \le d(u,x) \le b$

donde $u$ es un vector de variables de diseño, $x$ es un vector de variables de estado, y $c(u,x)$ es una restricción de igualdad (generalmente un PDE). Las limitaciones inferior y superior $a$ y $b$ pueden ser espacialmente variable.

¿Qué paquetes pueden manejar sistemas de esta forma?

pde optimization nonlinear-programming Sean Farley
fuente

1

La versión editada no se parece a un problema de optimización con restricción de cuadro. Un problema de optimización con restricción de cuadro tendría

a \leq u \leq b

$a \leq u \leq b$ como restricción. Se

u

$u$ supone que es una función de

x

$x$ ? ¿Es

c

$c$ lineal en

u

$u$ ? Si no es así, ¿es dos veces diferenciable? ¿Es

f

$f$ convexo en

u

$u$ ? ¿Es dos veces diferenciable en

u

$u$ ? Finalmente,

\arg min_{u}

$\arg \min_{u}$ denota el conjunto de puntos en

u

$u$ en el que se alcanza el valor mínimo de

f

$f$ . ¿Quieres decir

min_{u}

$\min_{u}$ lugar?

Geoff Oxberry

d (u, x) = u

$d(u,x) = u$ es un caso especial, pero esta forma más general es realmente común en la práctica. Siempre puede introducir variables adicionales si su método solo puede lidiar con restricciones directamente en

u

$u$ . Por lo general, estamos más interesados en el valor

u

$u$ al que se alcanza un mínimo que en el valor mínimo de

f

$f$ . Sean agregó la etiqueta [pde], por lo que puede obtener cierta regularidad de eso. No dijo si el sistema era hiperbólico o no, así que no asumamos. No supongamos que

f

$f$ es convexo, ya que a menudo no lo es.

Jed Brown el

Es bastante común que implique una regularización o , por lo que no debemos suponer dos derivadas.

f

$f$

L^{1}

$L^1$

W^{1, 1}

$W^{1,1}$

Jed Brown el

@JedBrown: Eso tiene sentido; fue confuso ver "restricción de caja" mencionada sin, bueno, una restricción de caja explícita. Para los tipos de problemas de los que está hablando (problemas de diseño, problemas de control), es definitivamente más interesante, pero los problemas de optimización generalmente se plantean utilizando la notación , y sus conjuntos de soluciones se describen utilizando la notación .

u

$u$

m i n

$min$

\arg min

$\arg \min$

Geoff Oxberry

Puede ser útil especificar en qué idioma / entorno modela las PDE. Puede restringir la elección de optimizadores.

Dominique

18

Decidí editar radicalmente mi respuesta en función de algunos de los comentarios.

No he usado TAO. Al examinar detenidamente la documentación, parece que la única forma en que TAO puede manejar problemas de optimización restringidos (excluyendo el caso especial de las restricciones de solo recuadros) es convertir el problema en una desigualdad variacional utilizando las condiciones de Karush-Kuhn-Tucker (KKT) , que son necesarios bajo la calificación de restricción (el tipo que generalmente veo es la condición del punto Slater ), y suficiente bajo la convexidad del objetivo y las restricciones (más generalmente, la invexidad de Tipo 1). Si $f$ no es convexo, la formulación de desigualdad variacional que utiliza las condiciones KKT NO es equivalente al problema de optimización original, por lo que, estrictamente hablando, si desea un óptimo global para el problema de optimización, no debe expresarlo como una desigualdad variacional. De todos modos, sería difícil encontrar un óptimo global para la optimización restringida por PDE (ver más abajo), por lo que tal vez ignorar este detalle está bien. Dado lo que Wolfgang ha dicho, sería escéptico de usar TAO; Ya soy escéptico porque no implementa métodos para resolver programas no lineales (PNL) como PNL, en lugar de desigualdades variacionales.

No soy un experto en optimización con restricciones PDE; compañeros de trabajo y asociados de minas trabajan en problemas de optimización restringidos por ODE. Sé que para formulaciones intrusivas, Larry Biegler (y otros) usarán métodos de colocación para discretizar el PDE y convertirlo en un PNL muy grande y escaso, y luego lo resolverá usando métodos de punto interior. Para resolver realmente el problema de la optimización global, también necesitaría generar relajaciones convexas, pero que yo sepa, este enfoque no se toma porque los problemas de optimización con restricción de PDE conducen a PNL tan grandes que sería difícil resolverlos. Optimidad global. Menciono estos detalles solo porque la formulación del problema influye mucho en la elección del paquete de solución. Para formulaciones no intrusivas, la PDE repetida resuelve información de gradiente de rendimiento para algoritmos de optimización.

Algunas personas que estudian problemas de optimización restringidos por ODE utilizan un enfoque similar de discretizar el problema utilizando la colocación y un método numérico, y luego relajar la PNL resultante para producir una formulación convexa utilizada en un algoritmo de optimización global. Un enfoque alternativo para la optimización limitada por ODE es relajar el problema y luego discretizar el ODE, que es el enfoque adoptado en mi laboratorio. Podría ser posible relajar ciertas clases de problemas de optimización restringidos por PDE, pero no sé de ningún trabajo existente realizado sobre ese problema. (Fue un proyecto potencial en mi laboratorio en un momento).

En última instancia, lo que importa no es la diferenciabilidad del PDE original, sino la diferenciabilidad de la discretización con respecto a las variables de decisión.

Si el problema discretizado es dos veces diferenciable con respecto a las variables de decisión, los siguientes paquetes calcularán una solución local:

IPOPT es un solucionador de puntos interiores de código abierto desarrollado por Andreas Wächter en IBM. Es un código de muy alta calidad. Como solucionador de puntos interiores, es mejor para funciones objetivas con matrices jacobianas grandes y dispersas, y sería útil para la optimización restringida por PDE
SNOPT es un solucionador de programación cuadrática secuencial comercial que es otro código de alta calidad. Es mejor para funciones objetivas con matrices jacobianas pequeñas y densas, por lo que no esperaría que fuera útil para la optimización restringida por PDE, pero podría intentarlo.
NLopt es un pequeño código de código abierto escrito por Steven Johnson en el MIT que contiene implementaciones básicas de una serie de algoritmos de optimización no lineal. Todos los algoritmos deben ser adecuados para resolver problemas con restricciones limitadas.
fmincon en Matlab implementa una serie de algoritmos (incluyendo punto interior y programación cuadrática secuencial) para la optimización no lineal
GAMS y AMPL son lenguajes comerciales de modelado utilizados para formular problemas de optimización y contienen interfaces para una gran cantidad de solucionadores de programación no lineales. Sé que GAMS tiene una versión de prueba que se puede usar para problemas más pequeños, y las instancias de problemas también se pueden enviar al servidor NEOS para su solución.

Sin embargo, es posible que la discretización sea solo una vez diferenciable con respecto a las variables de decisión, en cuyo caso, debe usar el descenso más pronunciado proyectado o algún otro método de optimización de primer orden al calcular una solución local. Dado que muchos estudios se centran en problemas en los que se pueden usar métodos de segundo orden (y cuando puede usarlos, sus propiedades de convergencia superiores los convierten en una mejor opción), no pude encontrar muchas implementaciones de descenso más pronunciado que no fueran soluciones a problemas de tarea. La Biblioteca Científica GNU tiene una implementación, pero es solo para fines de demostración. Probablemente necesite codificar su propia implementación.

Si el problema solo es continuo con respecto a las variables de decisión, entonces podría usar métodos directos para resolverlo localmente. Hay una excelente encuesta sobre métodos directos realizada por Kolda, Lewis y Torczon . El más conocido de estos métodos es el algoritmo simplex Nelder-Mead . No se garantiza que converja a un mínimo local en múltiples dimensiones, pero ha encontrado un uso práctico considerable de todos modos.

La elección del paquete realmente depende del idioma que desee usar para resolver el problema, si la solución del problema limitado es solo parte de un algoritmo que desea implementar (o si es el único paso en su algoritmo, en cuyo caso los lenguajes de modelado volverse más viable para el código de producción), el tipo y el tamaño del problema, y si necesita algún paralelismo.

Geoff Oxberry
fuente

4

Hemos intentado TAO pero encontramos que no es muy útil para problemas con restricciones de desigualdad. También está esencialmente solo en modo de mantenimiento desde al menos 2003, sin nuevas características reales aparte de las actualizaciones para rastrear los cambios en PETSc sobre los que se basa.

Wolfgang Bangerth
fuente

3

Otra alternativa es OPT ++ . Admite restricciones lineales y no lineales con un solucionador de puntos interior no lineal eficiente, proporciona control para la precisión de la función (si se requiere diferenciación numérica), control para tamaños de pasos, etc. Normalmente estoy optimizando grandes funciones implícitas (por ejemplo, FEM) donde estos tipos de Los controles pueden ser útiles.

Barron
fuente

¿Podría explicar por qué OPT ++ es un buen paquete para usar? ¿Tiene usted (o sus colegas) alguna experiencia con esto?

Geoff Oxberry

Para ser claros, no tengo ninguna razón para decir que OPT ++ es superior a cualquiera de los que mencionó anteriormente porque no tengo ninguna experiencia con ellos (aunque marqué algunos de ellos para verificar). Pero sí tengo experiencia con OPT ++ y lo he encontrado adecuado para mis necesidades. Admite restricciones lineales y no lineales con un solucionador de puntos interior no lineal eficiente, proporciona control para la precisión de la función (si se requiere diferenciación numérica), control para tamaños de pasos, etc. Normalmente estoy optimizando grandes funciones implícitas (por ejemplo, FEM) donde estos tipos de Los controles pueden ser útiles.

Barron

2

@Barron: deberías haber puesto eso en tu respuesta para empezar. :)

JM

2

Si el problema se formula como un problema de complementariedad, puede usar TAO (Toolkit for Advanced Optimization). Algunos de los métodos en TAO, como el método de espacio reducido (una variante del método de conjunto activo), están actualmente disponibles como parte de SNES en PETSc ( SNESVI ).

Jungho Lee
fuente

1

$[-\infty,+\infty]$

No creo que MINUTE funcione bien para sus necesidades, pero la transformación puede hacerlo si se ve obligado a escribir parte o la totalidad del código usted mismo.

dmckee
fuente

Esa transformación parece desagradable; no es de extrañar que vaya acompañado de un par de párrafos.

Geoff Oxberry

1

Como señaló @Geoff Oxberry, varios paquetes le permiten encontrar una solución local. Si desea poder comparar estos diferentes solucionadores de PNL para un mismo problema, puede usar RobOptim .

Aunque RobOptim se desarrolló inicialmente teniendo en cuenta los problemas de optimización robótica, es adecuado para cualquier problema de optimización no lineal. Proporciona una interfaz C ++ simple con complementos para múltiples solucionadores de NLP (por ejemplo, Ipopt, NAG). Si no puede proporcionar gradientes, el cálculo de diferencias finitas se puede hacer automáticamente.

Es de código abierto, por lo que puede consultar el código fuente en GitHub: https://github.com/roboptim/

Nota: Soy uno de los desarrolladores de este proyecto.

BenC
fuente

1

Debería señalar que otras respuestas describen solucionadores , no marcos. Es más fácil encontrar un marco aceptable ( controlador ) que un buen solucionador,

Deer Hunter

@DeerHunter Cuando busca un solucionador para resolver un problema dado, a menudo es difícil saber a priori qué solucionador calculará la mejor solución y / o será el más rápido. Estás hablando de un "buen solucionador", pero esto realmente depende de lo que estés resolviendo: no hay un "mejor solucionador general". Además, las API de solucionador suelen ser bastante diferentes, por lo que puede ser realmente útil utilizar un buen marco que le permita cambiar fácilmente de un solucionador a otro. La pregunta era sobre "paquetes de software para optimización restringida", y los marcos también entran en esta categoría.

BenC

1

Aquí hay una lista parcial de paquetes de optimización con restricciones PDE.

Dolfin Adjoint es parte de FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance son partes de Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

Ejemplo de PYOMO para la optimización restringida por PDE:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

El manual TAO proporciona ejemplos de resolución de problemas de optimización con restricciones PDE:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

denfromufa
fuente

1

Bienvenido a SciComp.SE! Simplemente proporcionar un enlace (por útil que sea) no es realmente una buena respuesta; ver meta.stackexchange.com/questions/8231 . ¿Podría ampliar esto un poco (lenguaje informático, qué tipo de restricciones se pueden tratar, qué métodos se implementan, etc.)?

Christian Clason

Estoy de acuerdo con @ChristianClason. Ha habido un desarrollo sustancial en solucionadores para el software de optimización con restricciones PDE; sin embargo, esta respuesta no proporciona esencialmente antecedentes sobre qué algoritmos implementan realmente esos paquetes.

Geoff Oxberry

0

Los paquetes APM MATLAB y APM Python pueden resolver a gran escala (más de 100,000 variables) de sistemas de ecuaciones algebraicas diferenciales de enteros mixtos. El software está disponible como un servicio web para uso comercial o académico. Si está resolviendo un sistema PDE, puede discretizar una vez para ponerlo en forma DAE u ODE para ponerlo en el lenguaje de modelado APMonitor. El lenguaje de modelado utiliza solucionadores APOPT , BPOPT, IPOPT, SNOPT y MINOS.

John Hedengren
fuente

1

Revele su afiliación como desarrollador de APMonitor en esta y futuras respuestas que mencionan su software. Consulte las preguntas frecuentes para obtener detalles sobre nuestra política de divulgación.

Geoff Oxberry

Geoff, gracias por el dato. Comencé a trabajar en la plataforma APMonitor en 2004 como estudiante graduado en la Universidad de Texas en Austin. Ahora lo usamos en nuestro grupo de investigación en la Universidad Brigham Young para el control de procesos y la optimización ( apm.byu.edu/prism ) de aplicaciones biológicas, químicas, aeroespaciales y de otro tipo. Lo hago disponible gratuitamente para usuarios comerciales o académicos.

John Hedengren

Paquete de software para optimización restringida?

Respuestas: