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.