¿Transformar un problema de optimización en un programa cuadrático con restricciones lineales?

Question

Me gustaría que me ayudaran con un problema de minimización. El problema de minimización sería un programa cuadrático con restricciones lineales si no se incluyera una restricción específica. Me gustaría saber si hay algún truco que me permita seguir utilizando algoritmos para programas cuadráticos con restricciones lineales para resolver mi problema.

---

Introducción: Dejemos que $\theta\equiv (a,b,q)$ donde $a,b$ son escalares y $q$ es un vector de filas de dimensión $d_q$ con cada elemento en $[0,1]$ . Interpreto $\theta$ como un triplete ordenado.

Dejemos que $\Theta\equiv \Big\{\theta\equiv (a,b,q) \text{: } (a,b)\in \mathbb{R}^2\text{, } q\in [0,1]^{d_q} \Big\}$

---

Anotación adicional: Permítanme ahora añadir restricciones a algunos componentes de $q$ . Para ello necesito indexar los componentes de $q$ de una manera determinada, como se explica a continuación.

Dejemos que $$ \mathcal{Q}_{1}(a,b)\equiv \{+\infty, -\infty, -a, -b\} $$ $$ \mathcal{Q}_{2}(a,b)\equiv \{+\infty, -\infty, b-a, -b\} $$

$$ \mathcal{Q}(a,b)\equiv \mathcal{Q}_{1}(a,b)\times \mathcal{Q}_{2}(a,b)=\{(\infty, \infty), (-\infty,\infty), (-a,\infty), (-b, \infty)\text{, ...}\} $$ Observe que $\mathcal{Q}(a,b)$ tiene cardinalidad $4^2$ .

Dejemos que $d_q\equiv 4^2$ .

Cada elemento de $q$ corresponde a un elemento de $\mathcal{Q}(a,b)$ . Esta relación puede utilizarse para "remodelar" $q$ como una matriz $4\times 4$ $$ q\equiv \begin{array}{|c|c|c|c|c|} & \color{blue}{b-a} & \color{blue}{-b} & \color{blue}{\infty} & \color{blue}{-\infty} \\ \hline \color{blue}{-a} & q(1,1) &q(1,2) & q(1,3) & q(1,4) \\ \hline \color{blue}{-b } & q(2,1) &q(2,2) & q(2,3) & q(2,4) \\ \hline \color{blue}{ \infty } & q(3,1) &q(3,2) & q(3,3) & q(3,4) \\ \hline \color{blue}{-\infty } & q(4,1) &q(4,2) & q(4,3) & q(4,4) \\ \hline \end{array}$$ donde $q(i,j)$ denota el $ij$ -el elemento de la matriz anterior.

---

Restricciones: Ahora estoy listo para introducir las restricciones deseadas en algunos componentes de $q$ .

1) Restricción (1): $$q(4,1)=q(4,2)=q(4,3)=q(4,4)=q(1,4)=q(2,4)=q(3,4)=0$$

2) Restricción (2): $$q(3,3)=1$$

3) Restricción (3): para cada dos elementos $u', u''$ de $\mathcal{Q}(a,b)$ tal que $u'\leq u''$ tenemos que $$ q(i,j)-q(i,l)-q(k,j)+q(k,l)\geq 0 $$ donde

• $u'\leq u''$ está destinado a los componentes

• $(i,j)$ et $(k,l)$ son las coordenadas de, respectivamente $u', u''$ en la matriz anterior.

---

Función objetivo: La función objetivo es $$ T(q)\equiv (b(q))^2 $$ donde $b: [0,1]^{d_q}\rightarrow \mathbb{R}$ es una función lineal de $q$ .

---

Problema de minimización: $$ (\star) \hspace{1cm}\min_{\theta \in \Theta} T(q)\\ \text{ s.t. the constraints (1), (2), (3) are satisfied} $$

---

Por qué $(\star)$ no es un programa cuadrático con restricciones lineales: Creo que $(\star)$ no es un programa cuadrático con restricciones lineales debido a la restricción (3) que hace que el conjunto de viabilidad no sea convexo (véase ce respuesta para las explicaciones). En cambio, para un determinado $(a,b)\in \mathbb{R}^2$ , $$ (\star) (\star) \hspace{1cm}\min_{q\in [0,1]^{d_q}} T(q)\\ \text{ s.t. the constraints (1), (2), (3) are satisfied} $$ es un programa cuadrático con restricciones lineales.

---

Pregunta: No soy un experto en optimización, pero tengo entendido que los programas cuadráticos con restricciones lineales son buenos porque son relativamente fáciles de resolver. Por lo tanto, ¿hay alguna manera de que pueda resolver $(\star)$ ¿todavía se aprovechan algunas ventajas de los programas cuadráticos con restricciones lineales?

Answer 1

Mi interpretación es que la pregunta es: ¿Cómo puedo asegurar que la desigualdad lineal $q_{ij}-q_{il}-q_{kj}+q_{kl} \geq 0$ se mantiene cuando $q_{ij} \geq q_{kl}$ .

Esta es una implicación entre las desigualdades lineales

$$q_{ij} \geq q_{kl} \Rightarrow q_{ij}-q_{il}-q_{kj}+q_{kl} \geq 0 $$

Desgraciadamente no es representable en LP. Sin embargo, se puede modelar utilizando variables binarias auxiliares (lo que conduce a un programa cuadrático de enteros mixtos)

Para simplificar la notación, consideremos el caso genérico de algunas restricciones (no necesariamente lineales) $p(x)\geq 0$ et $w(x)\geq 0$ y la variable de decisión $x$

$$p(x) \geq 0 \Rightarrow w(x) \geq 0 $$

Introducir una variable binaria $\delta$ y un gran número $M$ (más adelante). La implicación está garantizada si se cumplen las dos restricciones siguientes

$$p(x) \leq M \delta, w(x)\geq -M(1-\delta)$$

Si $p(x)$ es positivo, $\delta$ se verá obligado a ser $1$ que obliga a $w(x)$ para ser no negativo.

Esto se denomina modelización de la gran M. Cuando se implementa, $M$ no debe hacerse innecesariamente grande, sino lo suficiente para que no afecte al espacio factible en $x$ cuando la variable binaria está inactiva. En su caso, suponiendo que las expresiones se construyen a partir de $q$ la diferencia y las sumas entre sus hasta 4 $q$ las variables nunca pueden exceder trivialmente de 4, por lo que $M=4$ o algo así debería ser posible. Si las variables $a$ et $b$ hay que conocer los límites de los mismos para poder acotar las expresiones en consecuencia.

Si $p(x)$ es un vector de longitud $n$ y se desea que la condición se active cuando todos los elementos sean no negativos, se introduciría una variable binaria vectorial $\Delta$ además de su anterior $\delta$ y utilizar $p(x) \leq M\Delta, \delta \geq 1 + \sum\Delta - n$ . Si todos los elementos son positivos, todos $\Delta$ los binarios serán forzados a ser $1$ , obligando a $\delta$ para ser $1$ .

Answer 2

La idea es la siguiente (ver más abajo para aclaraciones). ¿Sería posible hacer aquí una optimización convexa a trozos? El mayor problema viene de la restricción (3) que depende de la relación $u'\le u''$ . Si pensamos en $q$ como $16\times 1$ entonces la condición (3) es $$ A(a,b)q\,\ge 0 $$ donde $A(a,b)$ es un $16\times 16$ matriz de $0$ et $\pm 1$ dependiendo de cuántas relaciones $u'\le u''$ y de qué tipo para que $(a,b)$ que tenemos.

Sin embargo, la relación es bastante robusta, y puede valer la pena dividir el espacio $\Bbb{R}^2\ni (a,b)$ de tal manera que la matriz $A(u',u'')$ es el mismo dentro de una unidad de partición. La partición dependerá de las comparaciones (mayor que, menor que o igual que) entre los números $a$ , $b$ , $a-b$ de la $q$ -tabla (valores para $u'$ et $u''$ que afecta a $u'\le u''$ ), debería ser bastante sencillo de formular. Dentro de cada elemento de partición el conjunto es convexo, por lo que podemos resolver una serie de problemas convexos y luego elegir la mejor solución entre ellos.

---

EDITAR: Aclaración de la idea.

La restricción crítica (3) sólo depende del conjunto $$ U(a,b)=\{(u',u'')\colon u'\le u''\}. $$ El mismo conjunto $U$ resulta en la misma matriz $A(a,b)$ y el mismo conjunto de desigualdades para $q$ en (3).

Veamos el $u'\le u''$ más cerca:

1. la primera desigualdad de coordenadas depende de los casos $$ -a<-b,\quad -a=-b,\quad -a>-b. $$
2. la segunda desigualdad de coordenadas depende de $$ b-a<-b,\quad b-a=-b,\quad b-a>-b. $$

Te da 9 posibles combinaciones diferentes en las que $U$ es el mismo. Si ignoramos los casos de igualdad (dan un conjunto más restrictivo para $q$ lo cual no es bueno para la optimización - ¡compruébelo!) entonces nos quedamos con 4 casos de particiones diferentes para $(a,b)$ que dan el mismo conjunto de $q$ que satisface (3). Por ejemplo, el primer caso es $$ b<a,\quad b<\frac12 a. $$ En este caso obtenemos para $$ q=\begin{bmatrix} x_1 & y_1 & z_1 & 0\\ x_2 & y_2 & z_2 & 0\\ x_3 & y_3 & z_3=1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} $$ las siguientes desigualdades en (3) $$ 0\le x_i\le y_i\le z_i,\quad i=1,2,3, $$ $$ 0\le x_{j+1}-x_j\le y_{j+1}-y_j\le z_{j+1}-z_j,\quad j=1,2. $$ Los otros 3 casos se pueden obtener fácilmente a partir de éste mediante permutaciones de las dos primeras columnas y filas en $q$ (¡verificar!).

Por lo tanto, basta con resolver 4 problemas de optimización, uno para cada caso, y elegir la mejor solución de las cuatro. Cada subproblema es convexo.