Una introducción a la optimización robusta [... y una pequeña lista de compras que olvidé ...]

¿Cómo determinar cuántas personas necesitan ser contratadas para un nuevo cumplimiento, cómo exactamente completarlo y dónde colocar un producto en particular? Cuanto mayor es el negocio, mayor es la incertidumbre y más caro es el error. Vencer al caos y elegir la mejor solución es una de las tareas del equipo de ciencia de datos. Y dado que las matemáticas son la base del análisis de datos, comenzaremos con él.

En este post consideraremos problemas de optimización con incertidumbre en los datos y su aproximación por problemas convexos deterministas. Este es uno de los principales trucos en la optimización robusta: una técnica que le permite hacer frente a problemas de optimización que son demasiado sensibles para los cambios en los datos de entrada.

El tema de la sensibilidad es muy importante. Para las tareas, cuya calidad de la solución depende débilmente de los cambios en los datos, es más fácil usar la optimización estocástica habitual. Sin embargo, en tareas con alta sensibilidad, este enfoque dará un mal resultado. Hay muchas tareas de este tipo en finanzas, gestión de la cadena de suministro, diseño y muchas otras áreas.

Y sí, este es un ejemplo de una publicación donde la complejidad crece exponencialmente (basura ya) ...

¿Qué significa "resolver" el problema de optimización?

Comencemos con un breve recordatorio.

La tarea de optimización en general se ve así:

$$

$$\ min_ {x \ en R ^ n} f (x) \\ s.t. \\ x \ en X$$

Aqui $$$f (x)$ llamada la función objetivo, y $$$X$ - Un conjunto válido.

Al resolver el problema de optimización nos referimos a tal punto $$$x ^ * \ en X$ para lo cual se ejecuta:

$$

$$f (x) - f (x ^ *) \ geq 0, \ quad \ forall x \ en X$$

Este es el concepto estándar para resolver el problema de optimización sin incertidumbre.

¿Qué es un problema de optimización con incertidumbre?

Es hora de preguntarse sobre el origen de la función. $$$f (x)$ y limitaciones $$$X$ .

Muy útil para compartir.

• lógica estructural del problema (en otras palabras, qué funciones se utilizan),
• limitaciones técnicas (independientes de la lógica o los datos humanos),
• parámetros que se evalúan a partir de los datos.

Por ejemplo, una persona de negocios vino a nosotros y nos mostró el problema de programación lineal:

$$

$$\ min_ {x \ en R ^ 2} 2.16 x_1 + 3.7 x_2 \\ s.t. \\ 0.973 x_1 + 2.619 x_2 \ leq 3.32 \\ x_1 \ geq 0, x_2 \ geq 0$$

Ves esta tarea por primera vez. Un hombre también (tal vez no, ¡pero con chaquetas azules todo es tan abstracto!). No sabes el significado de las variables. Pero incluso ahora, con mucha confianza, podemos decir que:

1. Lo más probable es que la tarea sea lineal, porque alguien lo ha decidido. La linealidad es la estructura que una persona ha elegido.
2. Limitaciones $$$x_1 \ geq 0, x_2 \ geq 0$ Son técnicos. Es decir, provenían de la "física" y no de los datos (por ejemplo, las ventas no pueden ser negativas).
3. Coeficientes específicos $$$\ {0.973, 2.619, 3.32 \}$ en limitar $$$0.973 x_1 + 2.619 x_2 \ leq 3.32$ en nuestro ejemplo fueron evaluados a partir de los datos. Es decir, al principio alguien dijo que la variable $$$x_1$ asociado con variable $$$x_2$ , luego se dijo que la relación es lineal, y finalmente, los coeficientes en la ecuación de acoplamiento se estimaron a partir de los datos. Lo mismo es cierto para las probabilidades. $$$\ {2.16, 3.7 \}$ en la función objetivo.

Cuando hablamos de tareas con incertidumbre, apuntamos precisamente a la incertidumbre en los parámetros estimados a partir de los datos. No tocamos las limitaciones técnicas ni la elección inicial de la estructura del problema.

De vuelta a nuestra historia. Tenemos un problema lineal, alguien calculó los coeficientes de alguna manera. Si teníamos razón sobre la naturaleza de los coeficientes en la función, de hecho, se nos pidió que resolviéramos el problema para un escenario del desarrollo de eventos (una instancia específica del problema).

A veces esto es suficiente para nosotros, y simplemente lo resolvemos.

Sin embargo, a veces resolver un problema para un escenario es una idea estúpida (por ejemplo, si la solución es muy sensible a la variación de datos).

¿Qué hacer en este caso y cómo modelar la incertidumbre en los datos?

Primero, tenga en cuenta que la incertidumbre de los datos siempre se puede transferir de la función objetivo a restricciones o viceversa. Cómo hacer esto, mira debajo del corte.

Optimización estocástica, en línea, robusta y lista de productos

Podemos tener muchos escenarios de incertidumbre, así como opciones sobre qué hacer con él. Ilustramos varios enfoques estándar con un ejemplo simple.

No sé cómo es la situación con un lector respetado, pero aquí estoy casado (con éxito) y periódicamente voy al supermercado. Con una hoja, por supuesto (da invulnerabilidad de compras impulsivas). A veces no solo a la tienda, sino al Auchan condicional, donde es más barato, pero a dónde ir lejos.

Modelaremos esta situación: vinimos a Auchan con una hoja en nuestras manos para comprar.

Atención, la primera pregunta: ¿cómo modelar?

Entrada: información sobre los productos a comprar y la cantidad requerida.

Por conveniencia, podemos pensar en el folleto como un vector entero no negativo $$$y \ en Z _ + ^ n$ .

Como variables, tomamos, respectivamente, un vector entero no negativo $$$x \ en Z _ + ^ n$ - cuántos y qué productos compraremos en última instancia (nuestra solución).

El punto es pequeño: tome algún tipo de función objetivo $$$f (x, y)$ , que dice cuánto cometimos un error con la elección de los productos.

Dependiendo del contexto, el tipo de función puede cambiar, pero hay algunos requisitos básicos para ello:

• Función $$$f (x, y)$ debe tener un mínimo $$$x ^ * = \ arg \ min_ {x \ en R ^ n} f (x, y) = y$ (es decir, en óptimo compraremos exactamente lo que está escrito en el folleto)
• Función $$$f (x, y)$ debe ser convexo en $$$x$ (y preferiblemente suave) - para poder calcular efectivamente $$$min$ .

Así, obtenemos el problema:

$$

$$min_ {x \ en R ^ n} f (x, y)$$

Ahora imagine que la hoja se quedó en casa ...

Entonces, con un comentario, entramos en el mundo de las tareas con incertidumbre.

Entonces, ¿qué hacer si en la tarea $$$min_ {x \ en R ^ n} f (x, y)$ desconocido para nosotros $$$y$ ?

La respuesta, nuevamente, depende del contexto.

Optimización estocástica

La optimización estocástica (generalmente) implica

• La incertidumbre en los datos es de naturaleza estocástica. Conocimiento completo de la distribución probabilística de valores de parámetros no deterministas.
• Las limitaciones, incluida la incertidumbre, son suaves

En nuestro ejemplo, si lo modelamos utilizando la optimización estocástica, diríamos

• De acuerdo, no sé qué estaba escrito en el folleto, pero he estado caminando con folletos durante 8 años y tengo bastante conocimiento sobre la distribución del vector. $$$y$
• Incluso si me equivoco con la elección (es decir, con $$$x$ ), volviendo a casa, descubro lo real $$$y$ y, si estoy completamente seguro, iré a Pyaterochka y compraré allí, aunque sea más caro.
• Ahora elegiré uno $$$x$ , que minimizará algún tipo de agregado de la función objetivo original y posibles "multas" por el error.

Esto nos llevará a esta tarea:

$$

$$\ min_ {x \ en R ^ n} E_y [f (x, y) + \ psi (y, z)] \\ s.t. \\ x + z \ geq y$$

Tenga en cuenta que en esta tarea, de facto tomamos decisiones dos veces: primero, la decisión principal de comprar en Auchan, de la cual somos responsables $$$x$ , luego "corrección de errores" con $$$z$ .

Los principales problemas con este enfoque son:

• A menudo no hay información sobre la distribución de parámetros.
• Las limitaciones pueden ser severas (para tareas con alto riesgo: muerte, ruina, apocalipsis nuclear o zombie, etc.)
• No siempre es posible "corregir errores" (una decisión se toma una vez) o viceversa, a menudo se toman decisiones (en este caso, aparecerán muchas integrales anidadas, y será muy difícil contarlas).

Optimización en línea

La optimización en línea es un marco que explora la toma de decisiones consistentes. Uno de los enfoques estándar para el modelado en este marco son los bandidos multi-armados, que ya se han escrito sobre Habré muchas veces.

En el contexto de nuestro ejemplo de juguete, haríamos lo siguiente:

• no tenía ningún folleto (y nunca lo usó antes)
  
• y en casa seríamos elogiados / regañados por los productos que compramos (al mismo tiempo, solo podíamos adivinar sobre el conjunto deseado)
• la tarea sería aprender lo más rápido posible a comprar comida, así como a su antiguo príncipe imaginario, bueno, o al mejor amigo de los hijos de su madre.

Optimización robusta

La optimización robusta es una extensión lógica de la idea de una solución minimax.

Idealmente, ahora deberíamos tomar una decisión que siempre será aceptable, independientemente de las circunstancias. Las personas que diseñaron ollas, planchas y refrigeradores en la URSS hicieron esto en el contexto de una optimización robusta: el producto debería funcionar incluso si se ha utilizado durante 20 años como la herramienta principal para el exterminio de mutantes que surgieron después de la guerra nuclear (también debe sobrevivir).

Además, quiero que el rompecabezas sea llevado a un solucionador regular, y no entienden las restricciones "para cualquier implementación de una variable aleatoria" (si no hay un número finito de estas implementaciones).

En el problema con un folleto, la decisión debe tomarse aquí y ahora y seguir siendo válida bajo cualquier circunstancia:

$$

$$\ min_ {x \ en R ^ n, t \ en R} t \\ s.t. \\ f (x, y) \ leq t \ quad \ forall y \\ x \ geq y \ quad \ forall y$$

Está claro que incluso en este ejemplo de juguete, si no necesita nada de $$$y$ , entonces ninguna solución significativa funcionará.

Entonces, ¿cómo manejas esas tareas?

Creación de una versión robusta de una tarea utilizando el ejemplo de tarea LP

Considere un problema de optimización lineal con incertidumbre:

$$

$$\ min_ {x \ en R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

Parámetros $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ se derivaron de los datos e incluyen incertidumbre.

Supuesto 1: muchos valores (implementaciones) $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ se puede parametrizar, es decir hay tal $$$\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix}, \ begin {pmatrix} c_1 ^ T, d_1 \\ A_1, b_1 \ end {pmatrix}, \ dots, \ begin {pmatrix } c_k ^ T, d_k \\ A_k, b_k \ end {pmatrix}$ que cualquier implementación de datos $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ se encuentra en el conjunto:

$$

$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix} \ in U = \ left \ {\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \ begin {pmatrix} c_i ^ T, d_i \\ A_i, b_i \ end {pmatrix} | \ quad \ zeta \ en Q \ subconjunto R ^ k \ right \}$$

Aqui $$$\ begin {pmatrix} c ^ T_0, d_0 \\ A_0, b_0 \ end {pmatrix}$ se denominan datos "nominales" y $$$\ begin {pmatrix} c ^ T_i, d_i \\ A_i, b_i \ end {pmatrix} \ quad (1 \ leq i \ leq k)$ - "turnos".



Ya sabemos que toda la incertidumbre en el problema puede eliminarse en las limitaciones. Hagámoslo

Tenemos el problema

$$

$$\ min_ {x \ en R ^ n, t \ en R} t \\ st \\ c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ en U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ en U \\ $$

Versión robusta de la tarea.

Ahora es el momento de uno de los mejores trucos en la optimización robusta: cómo pasar de un número infinito de restricciones a un conjunto finito de buenas restricciones.

Para comenzar, considere un ejemplo simple cuando

$$

$$Q = \ {\ zeta \ en R ^ k | \ | \ zeta \ | _2 \ leq 1 \}$$

Todas las restricciones en el sistema.

$$

$$c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ en U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ en U \\ $$

del mismo tipo: son solo desigualdades lineales. Aprenda a trabajar con uno: aprenda a trabajar con todos.

Por lo tanto, consideramos una restricción del tipo de desigualdad:

$$

$$a ^ Tx \ leq b \ quad \ forall (a, b) \ in U = \ {(a_0, b_0) + \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i, b_i) | \ quad \ zeta \ en Q \} \\ (a_0 + \ sum_ {i = 1} ^ k \ zeta_i a_i) ^ Tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ in Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx \ quad \ forall \ zeta \ in Q \\ \ max _ {\ zeta \ en Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx$$

Déjame explicarte lo que pasó.

Primero, transferimos todas las partes con incertidumbre al lado izquierdo de la desigualdad; $$$\ zeta$ .
Después de eso, vimos el peor de los casos (para cada $$$x$ Él es suyo).
Como resultado, obtuvimos el siguiente registro:

$$

$$g (x) = max _ {\ zeta \ in Q} f (x, \ zeta) \ leq b_0 - a_0 ^ Tx$$

.

El siguiente paso es escribir una función explícita $$$g (x)$ . Para hacer esto, es suficiente resolver el problema de optimización $$$\ zeta$ y sustituir el óptimo $$$\ zeta *$ :

$$

$$\ max _ {\ | \ zeta \ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) = \ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx - b_i) ^ 2}$$

lo que lleva a la desigualdad:

$$

$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$$

Tenga en cuenta que la desigualdad resultante es convexa y cualquier $$$x$ satisfacerlo satisface el original $$$a ^ Tx \ leq b$ para cualquier implementación $$$(a, b) \ en U$ ...

Limitación $$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$ llamada la versión robusta de la restricción $$$a ^ Tx \ leq b \ quad \ forall (a, b) \ en U$ .

Este es uno de los principales caballos de batalla en la optimización robusta: la aproximación de las restricciones de probabilidad por un conjunto finito de restricciones convexas.

¿Qué hacer con restricciones más complejas (no lineales)?

Construyendo versiones robustas de restricciones usando dualidad cónica

Se pueden representar muchas restricciones no lineales estándar en forma cónica (es decir, en la forma $$$Ax + b \ en K$ donde $$$K$ es un cono convexo cerrado):

• No negatividad $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ en R ^ n _ +$
• Restricciones de norma $$$\ | x \ | _p \ leq p \ quad \ leftrightarrow \ quad \ begin {pmatrix} x \\ p \ end {pmatrix} \ in K_p ^ n = \ left \ {(x, t) \ in R ^ n \ veces R_ + | \ quad \ | x \ | _p \ leq t \ right \}$
• Restricciones sobre la definición positiva de la matriz. $$$x_1F_1 + \ puntos x_nF_n + G \ succeq 0$

Volver a las restricciones robustas.

Suponga que el problema de optimización con respecto a $$$\ zeta$ logró reducirse a una forma cónica

$$

$$\ max _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx - b_i) \\ s.t \\ C \ zeta + d \ en K$$

Construimos un dual para este problema.

Hace algún tiempo publiqué una publicación sobre la dualidad cónica exactamente para dedicar un poco menos de atención a la técnica misma en esta publicación.

$$

$$\ min _ {\ lambda} \ lambda ^ Td \\ st \\ C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k \\ \ lambda \ en K ^ *$$

Ahora depende de lo pequeño: el teorema de la dualidad débil:

$$

$$\ max _ {[\ zeta: \ quad C \ zeta + d \ in K]} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) \ leq \ min _ {\ lambda \ en G} \ lambda ^ Td \\ where \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ en K ^ * \ right \}$$

Por lo tanto, como una aproximación robusta de la restricción inicial $$$a ^ Tx \ leq b, \ quad (a, b) \ en U$ restricción puede ser utilizada

$$

$$\ lambda ^ Td \ leq b_0 - a_0 ^ Tx \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ en K ^ * \ right \}$$

donde $$$\ lambda$ misma variable que $$$x$ .

Entonces construimos una restricción robusta para la desigualdad original.

Conclusión

Examinamos la técnica de aproximación de restricciones malas (estocásticas) mediante un conjunto de buenas restricciones convexas. Esto puede ser útil, por ejemplo, si:

• No desea escribir algoritmos usted mismo, pero el solucionador que está utilizando no sabe cómo trabajar con restricciones de probabilidad.
• Hay un problema con los parámetros estocásticos, mientras que el óptimo es muy sensible a las fluctuaciones en los datos.
• Y, por supuesto, tareas con incertidumbre, donde todas las restricciones son estrictas (el precio del error es demasiado alto)