Un programa cuadrático no convexo con restricciones cuadráticas (QCQP)

Question

¿Cómo puedo resolver el siguiente problema de optimización cuadrática con restricciones?

$$\max_{x} \qquad x'Ax$$ tal que $$x'P_ix - k \leq 0 \qquad i=1,2$$

$A, P_i$ son matrices semidefinidas positivas. Sé que podemos minimizar $x' \hat{A} x$ donde $\hat{A} = -A$ pero esto cambia el problema a uno cóncavo con restricciones convexas. $x \in \mathbb{R^2}$ . Si ayuda, encontrar el mínimo de la inversa de $x' A x$ también es una opción.

La función objetivo en ese caso sería $$\min_x \qquad \frac{1}{x'Ax}$$

Answer 1

Por lo tanto, dado que sus funciones son semidefinidas positivas, hay una serie de algoritmos que puede utilizar (ver: https://en.wikipedia.org/wiki/Quadratic_programming#cite_note-6 , cita 6). Pero para este problema es lo suficientemente simple como para no necesitar tales técnicas:

Dado $x \in \mathbb{R}^2$ deseamos resolver

$$ \max x^T A x \\ x^T P_1 x \le k, x^T P_2 x \le k$$

En realidad, esto se puede concretar por completo dejando que $A = \begin{pmatrix} A_{00} & A_{01} \\ A_{10} & A_{11} \end{pmatrix}$ y

$$P_1 = \begin{pmatrix} P_{001} & P_{011} \\ P_{101} & P_{111} \end{pmatrix}$$

$$P_2 = \begin{pmatrix} P_{002} & P_{012} \\ P_{102} & P_{112} \end{pmatrix}$$

Entonces se deduce que queremos resolver

$$ \max x_0 (A_{00} x_0 + A_{01} x_1) + x_1(A_{10} x_0 + A_{11} x_1) \\ x_0 (P_{001} x_0 + P_{011} x_1) + x_1(P_{101} x_0 + P_{111} x_1) -k \le 0 \\ x_0 (P_{002} x_0 + P_{012} x_1) + x_1(P_{102} x_0 + P_{112} x_1) -k \le 0 $$

Aquí reordenamos los términos para obtener:

$$ \max A_{00} x_0^2 + (A_{01}+ A_{10} )x_1x_0 + A_{11} x_1^2 \\ P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k \le 0 \\ P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k \le 0 $$

Ahora podemos sacar directamente el $KKT$ condiciones (una generalización de los multiplicadores de lagrange) https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

que nos dicen que la solución óptima $x^*$ a este problema satisfará las condiciones (suponiendo que $f = A_{00} x_0^2 + (A_{01}+ A_{10} )x_1x_0 + A_{11} x_1^2$ , $p_1 = P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k$ , $p_2 = P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k $ ) :

Condiciones:

$$\nabla f(x^*) = \mu_1 \nabla p_1(x^*) + \mu_2 \nabla p_2 (x^*)$$ $$ p_1(x^*) \le 0 $$ $$ p_2(x^*) \le 0 $$ $$ \mu_1 \ge 0, \mu_2 \ge 0$$ $$ \mu_1 p_1(x^*) = 0, \mu_2 p_2(x^*) = 0$$

Abordemos la primera línea con el $\nabla$ 's desempacando para nuestro caso:

$$ \begin{bmatrix} 2A_{00}x_0 + (A_{01} + A_{01})x_1 = \mu_1 (2P_{001}x_0 + (P_{011} + P_{011})x_1) + \mu_2 (2P_{002}x_0 + (P_{012} + P_{012})x_1) \\ 2A_{11}x_1 + (A_{01} + A_{01})x_0 = \mu_1 (2P_{112}x_1 + (P_{011} + P_{012})x_0) + \mu_2 (2P_{112}x_1 + (P_{012} + P_{012})x_0)\end{bmatrix}$$

Ahora mira las 2 últimas ecuaciones de la forma $[\mu_1 p_1(x^*) = 0, \mu_2 p_2(x^*) = 0]$

También podemos descomprimirlos para obtener

$$ \mu_1 (P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k) = 0 \\ \mu_2 (P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k)= 0 $$

combinando estos cuatro, juntos:

$$ \begin{bmatrix} 2A_{00}x_0 + (A_{01} + A_{01})x_1 = \mu_1 (2P_{001}x_0 + (P_{011} + P_{011})x_1) + \mu_2 (2P_{002}x_0 + (P_{012} + P_{012})x_1) \\ 2A_{11}x_1 + (A_{01} + A_{01})x_0 = \mu_1 (2P_{112}x_1 + (P_{011} + P_{012})x_0) + \mu_2 (2P_{112}x_1 + (P_{012} + P_{012})x_0)\\ \mu_1 (P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k) = 0 \\ \mu_2 (P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k)= 0 \end{bmatrix} $$

Tenemos 4 ecuaciones, y 4 incógnitas $\mu_0, \mu_1, x_0, x_1$ . Ahora se puede resolver algebraicamente para 36 posibles combinaciones de $\mu_0, \mu_1, x_0, x_1$ seleccione el que maximice su función.

Answer 2

Tenemos el siguiente QCQP

$$\begin{array}{ll} \text{maximize} & \mathrm x^{\top} \mathrm A \, \mathrm x\\ \text{subject to} & \mathrm x^{\top} \mathrm P_1 \mathrm x \leq q_1\\ & \mathrm x^{\top} \mathrm P_2 \mathrm x \leq q_2\end{array}$$

donde $\mathrm A, \mathrm P_1, \mathrm P_2 \in \mathbb R^{n \times n}$ son simétricos y semidefinidos positivos, y $q_1, q_2 > 0$ . Tenga en cuenta que tenemos un convexo función objetivo y dos convexo restricciones de desigualdad. Sin embargo, como queremos maximizar el objetivo, el QCQP dado es no -convexo.

Si $\mathrm P_1, \mathrm P_2$ fueron positivo definida (por tanto, invertible), entonces, utilizando la Complemento de Schur podríamos escribir la restricción de desigualdad $\mathrm x^{\top} \mathrm P_i \mathrm x \leq q_i$ como la siguiente desigualdad matricial lineal (LMI)

$$\begin{bmatrix} \mathrm P_i^{-1} & \mathrm x\\ \mathrm x^{\top} & q_i\end{bmatrix} \succeq \mathrm O_{n+1}$$

Tendríamos entonces el problema de optimización cuadrática con restricciones LMI

$$\begin{array}{ll} \text{maximize} & \mathrm x^{\top} \mathrm A \, \mathrm x\\ \text{subject to} & \begin{bmatrix} \mathrm P_1^{-1} & \mathrm x & & \\ \mathrm x^{\top} & q_1 & & \\ & & \mathrm P_2^{-1} & \mathrm x \\ & & \mathrm x^{\top} & q_2\end{bmatrix} \succeq \mathrm O_{2n+2}\end{array}$$

¿Alguien conoce algún trabajo de optimización cuadrática sobre (convexo) espectros ?

Echa un vistazo a la obra de Didier Henrion notas de clase y sus referencias.