Saltar al contenido

Maximizar la norma euclidiana de una matriz multiplicada por un vector en subesferas unitarias

Puede que se de el caso de que halles algún error con tu código o trabajo, recuerda probar siempre en un entorno de testing antes añadir el código al proyecto final.

Solución:

No puede esperar nada como una solución de forma cerrada, o incluso un algoritmo eficiente exacto para este problema, porque es NP-difícil. La reducción es del problema de corte máximo. Veamos el caso especial $m=1$. Sea $G = (V, E)$ un gráfico y oriente los bordes de alguna forma arbitraria. Sea $A$ la matriz de incidencia arista por vértice de $G$, es decir, las filas de $A$ están indexadas por aristas y las columnas por vértices, y $a_e, v$ es $1$ si $v $ es la cola de $e$, $-1$ si $v$ es la cabeza de $e$ y $0$ en caso contrario. Entonces es fácil verificar que para cualquier $x in mathbbR^V$, $|Ax|^2 = sum_(u,v) in E{(x_u – x_v)^2 ps Si $x in -1, 1^V$ como en el caso $m=1$ de su problema, entonces $|Ax|^2 = 4e(S, barS)$ , donde $e(S, barS)$ es el número de aristas cortadas por el conjunto $S = v: x_v = 1$.

Puede encontrar un algoritmo de aproximación de factor constante (debido a Nesterov) en el Capítulo 6.3. del libro de Williamson y Shmoys.

Puedes escribir $AX=sum_i=1^N A_i x_i$ con $A_iin mathbbR^rtimes m$. Entonces tenemos $$ |AX|^2=(AX)^TAX=sum_i,j x^T_i A_i^TA_jx_j. $$ La condición para un punto crítico es $$ A_i^TAX=alpha_ix_i $$ para algunos $alpha_1,dots,alpha_N in mathbbR$. Una posibilidad de encontrar el maximizador es hacer la iteración de punto fijo $$ x_i=fracA_i^TAX. $$

$$mathrm A mathrm x = beginbmatrix mathrm A_1 & mathrm A_2 & cdots & mathrm A_nendbmatrix beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_nendbmatriz$$

donde $mathrm x_1, mathrm x_2, dots, mathrm x_n in mathbb R^m$ son las variables de optimización. Por lo tanto,

$$| mathrm A mathrm x |_2^2 = beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_nendbmatrix^top beginbmatrix mathrm A_1 ^top mathrm A_1 & mathrm A_1^top mathrm A_2 & cdots & mathrm A_1^top mathrm A_n\ mathrm A_2^top mathrm A_1 & mathrm A_2^top mathrm A_2 & cdots & mathrm A_2^top mathrm A_n\ vdots & vdots & ddots & vdots\mathrm A_n^top mathrm A_1 & mathrm A_n^top mathrm A_2 & cdots & mathrm A_n^top mathrm A_n\ endbmatrix beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_nendbmatrix$$

Por lo tanto, tenemos el siguiente programa cuadrático con restricciones cuadráticas (no convexo) (QCQP)

$$begin{arrayll textmaximizar & beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_nendbmatrix^top beginbmatrix mathrm A_1^ arriba mathrm A_1 & mathrm A_1^top mathrm A_2 & cdots & mathrm A_1^top mathrm A_n\ mathrm A_2^top mathrm A_1 & mathrm A_2^top mathrm A_2 & cdots & mathrm A_2^top mathrm A_n\ vdots & vdots & ddots & vdots\mathrm A_n^top mathrm A_1 & mathrm A_n^top mathrm A_2 & cdots & mathrm A_n^top mathrm A_n\ endbmatrix beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_nendbmatrix\ textsujeto a & | mathrm x_1 |_2^2 = 1\ & | mathrm x_2 |_2^2 = 1\ & qquadvdots \ & | mathrm x_n |_2^2 = 1 endarray$$

Sea el lagrangiano

$$mathcal L (mathrm x_1, dots, mathrm x_n, mu_1, dots, mu_n) := beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_n endbmatrix^top beginbmatrix mathrm A_1^top mathrm A_1 & mathrm A_1^top mathrm A_2 & cdots & mathrm A_1^top mathrm A_n\ mathrm A_2 ^top mathrm A_1 & mathrm A_2^top mathrm A_2 & cdots & mathrm A_2^top mathrm A_n\ vdots & vdots & ddots & vdots\mathrm A_n^top mathrm A_1 & mathrm A_n^top mathrm A_2 & cdots & mathrm A_n^top mathrm A_n\ endbmatrix beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_nendbmatriz -\- sum_k=1^n mu_k left( | mathrm x_k |_2^2 – 1 right)$$

Tomando todas las derivadas parciales del Lagrangiano y encontrando dónde se anulan, obtenemos el siguiente sistema lineal homogéneo

$$beginbmatrix mathrm A_1^top mathrm A_1 – mu_1 mathrm I_m & mathrm A_1^top mathrm A_2 & cdots & mathrm A_1^top mathrm A_n\ mathrm A_2 ^top mathrm A_1 & mathrm A_2^top mathrm A_2 – mu_2 mathrm I_m & cdots & mathrm A_2^top mathrm A_n\ vdots & vdots & ddots & vdots\ mathrm A_n^top mathrm A_1 & mathrm A_n^top mathrm A_2 & cdots & mathrm A_n^top mathrm A_n – mu_n mathrm I_m endbmatrix beginbmatrix mathrm x_1\ mathrm x_2\ vdots \ mathrm x_nendbmatrix = beginbmatrix 0_m\ 0_m\ vdots \ 0_mendbmatrix$$

y las restricciones de igualdad $| mathrm x_1 |_2^2 = | mathrm x_2 |_2^2 = cdots = | mathrm x_n |_2^2 = 1$. Para satisfacer estas restricciones de igualdad $n$, no podemos tener solo la solución $mathrm x = 0_mn$. Por lo tanto, la matriz debe ser singulares decir,

$$det beginbmatrix mathrm A_1^top mathrm A_1 – mu_1 mathrm I_m & mathrm A_1^top mathrm A_2 & cdots & mathrm A_1^top mathrm A_n\ mathrm A_2^top mathrm A_1 & mathrm A_2^top mathrm A_2 – mu_2 mathrm I_m & cdots & mathrm A_2^top mathrm A_n\ vdots & vdots & ddots & vdots \mathrm A_n^top mathrm A_1 & mathrm A_n^top mathrm A_2 & cdots & mathrm A_n^top mathrm A_n – mu_n mathrm I_m endbmatrix = 0$$

que produce un ecuación polinomial de grado $mn$ en los $n$ multiplicadores de Lagrange $mu_1, mu_2, dots, mu_n$.

Si te gustó nuestro trabajo, tienes la habilidad dejar una crónica acerca de qué le añadirías a este escrito.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *