Optimización multilineal

Question

¿Hay cualquier algoritmos eficientes para resolver, objetivo multi-linear y problemas de optimización multi-linear restricción? Las funciones multilineal son sumas de términos bilineal, trilineales (y así sucesivamente)

\begin{align*} \min\quad & f_1(x_1,x_2,x_3,...,x_n)\\ \text{s.t.}\quad &f_2(x_1,x_2,x_3,...,x_n)\leq b\\ &f_3(x_1,x_2,x_3,...,x_n)\leq c\\ &f_i(x_1,x_2,x_3,...,x_n)=a_{i1}x_1x_2...x_n+a_{i2}x_1x_2...x_{n-1}+...+a_{i(n-1)}x_1+a_{in} \end{align*}

Answer 1

Un problema de optimización donde la función objetivo y las restricciones son multilineal (es decir, las sumas de los productos, $f(x_1,\ldots,x_n)=\sum_{I\subseteq\{1,\ldots,n\}} a_I \prod_{i\in I} x_j, a_I \in \mathbb{R}$) con respecto a las variables de decisión son difíciles de resolver, ya que estos problemas no convexos en general y no se conocen maneras para convexify. Por lo tanto el problema general que no puede ser (en mi conocimiento) se transforma en un problema de programación lineal, por ejemplo. Sin embargo, como se demuestra por el post anterior por el usuario p.s., en algunos casos especiales es posible.

Existe algoritmos para resolver el problema general. Uno en particular es el Reformulatio-técnica de Linealización por Hanif Sherali y Cihan Tuncbilek (1992) , que resuelve el problema como una secuencia de programación lineal. Este método se basa en la relajación de las variables de producto. Por ejemplo, si hay un producto plazo $x_1 x_2$, entonces este es reemplazado por una variable $X_{1,2}$. Esta nueva variable está restringido el uso explícito de los límites inferior y superior en las variables.

Si el problema original tendría límites $0 \leq x_1\leq 1$$1 \leq x_2\leq 2$, entonces uno podría generar una restricción en la variable del producto $X_{1,2}$ señalando que $(x_1-0)(x_2-1)\geq0$, que en forma expandida rendimientos $x_1 x_2 -x_1\geq0$, donde sustituyendo $x_1 x_2\rightarrow X_{1,2}$ rendimiento $X_{1,2}-x_1\geq 0$. Mediante el uso de todos los límites de las variables, se puede derivar más de las restricciones en la variable producto, lo que da una mayor relajación del problema original.

La reformulada problema es lineal con respecto a las variables originales $x_i$ y el producto de las variables de $X_.$ y puede ser resuelto con una programación lineal algoritmo. Si la solución obtenida a partir de la relajación no producir una solución viable para el problema original, entonces esta solución puede ser utilizada para dividir el espacio de búsqueda en dos por la ramificación en una variable. Así que continuando con el ejemplo anterior, si en óptima de la relajación $x_1=0.5$, luego de una ramificación puede ser realizado teniendo en cuenta dos problemas que son los mismos que el original, pero en la primera $0\leq x_1\leq0.5$ y en el segundo $0.5\leq x_2\leq 1$. Claramente, la solución óptima para el problema original se encuentra en cualquiera de estas ramas. Ahora, debido a los límites de la variable $x_1$ ha cambiado, también de las restricciones sobre las variables de producto que ha cambiado también, y se puede demostrar que el producto de las variables que convergen hacia el producto de los términos al continuar la iteración en la que esta de moda.

Aunque conceptualmente simple, la RLT método no es sencillo de implementar. Por lo tanto, para el pequeño problema de los casos, puede ser útil para tratar algunas comercial numérico no lineal solver (por ejemplo, BARON) o incluso el comando Maximizar en Mathematica que resuelve el problema de forma simbólica.

Referencias

Sherali, Hanif D., y Cihan H. Tuncbilek. "Un algoritmo de optimización global para el polinomio de problemas de programación mediante una reformulación-linealización de la técnica". Diario de Optimización Global 2.1 (1992): 101 a 112.

Answer 2

Optimización de general multilineal funciones es difícil, pero por la forma específica dada en el enunciado del problema, sólo hay $n$ monomio términos, por lo que podemos volver a parametrizar: $$ \begin{align} z_1 &= x_1 \\ z_k &= z_{k - 1} x_k, \quad k = 2 \ldots n \end{align} $$ Entonces el problema es lineal en la $z_k$ y puede ser resuelto con cualquier LP solver.

Un general de la función multilineal ha $2^n$ monomio términos, pero esto es no lo que la pregunta está pidiendo.

A partir de la óptima $\mathbf{z}^*$, entonces podemos recuperar el óptimo $\mathbf{x}^*$, a menos que hayamos $z^*_k=0$ $z^*_{k+1}\ne 0$ algunos $k$. Sin embargo, si esto sucede cuando $\mathbf{z}^*$ es la única mínimo de la transformada problema, entonces esto implica que el problema original no tiene finita mínimo. De lo contrario, si la transformada problema tiene múltiples mínimos, podemos resolver una modificación de la LP para encontrar un óptimo $\mathbf{z}^*$ que corresponde a un número finito $\mathbf{x}^*$.