Considere la posibilidad de la simulación de la matriz $Y\in{\mathbb R}^{2\times n}$ y con una magnitud $\mu=\sqrt{\operatorname{tr}(Y^TY)}$.
El uso de un signo de dos puntos para indicar el producto de seguimiento, es decir, $\,A:B=\operatorname{tr}(A^TB),\,$ podemos diferenciar la magnitud como
$$\mu^2=Y:Y \implies\mu\,d\mu=Y:dY$$
Let the columns of the matrix $X\in{\mathbb R}^{2\times n}$ be the $x_i$ vectors. Then the entries of the Grammian matrix $\,G=X^TX\,$ son los productos de puntos de las columnas, y los de la diagonal principal contiene los cuadrados de las longitudes de las columnas.
Por lo que el problema de la restricción puede ser expresado mediante la traza.
$$1 = \operatorname{tr}(G) = X:X$$
Y $X$ se puede construir a partir de $Y$ tal que esta restricción es siempre satisfecho.
$$\eqalign{
X &= \mu^{-1}Y \quad\implica X:X = \mu^{-2}(X:Y) = 1 \\
dX &= \mu^{-1}dY - \mu^{-3}Y(Y:dY) \\
}$$
Columnar distances can be calculated using the $G$ matrix and the all-ones vector ${\tt1}$
$$\eqalign{
g &= \operatorname{diag}(G) \\
A_{ij} &= \|x_i-x_j\| \quad\implica A= g{\tt1}^T + {\tt1}g^T - 2G \\
B &= A+I,\quad C= B^{\odot-3/2},\quad L= C-\operatorname{Diag} C{\tt1}) \\
}$$
La adición de la matriz identidad se deshace de la cero los elementos de la diagonal principal, y permite el cálculo de todos los Hadamard $(\odot)$ competencias que necesita el objetivo de la función y su derivada.
$$\eqalign{
f &= {\tt11}^T:B^{\odot-1/2} \;-\; {\tt11}^T:I \\
df &= -\tfrac{1}{2}C:dB \\
&= \tfrac{1}{2}C:(2\,la dirección general de la dg\,{\tt1}^T {\tt1}\,dg^T) \\
&= C:dG - \tfrac{1}{2} C{\tt1}:dg+{\tt1}^TC:dg^T) \\
&= C:dG - C{\tt1}:dg \\
&= \Big(C - \operatorname{Diag} C{\tt1})\Big):dG \\
&= -L:dG \\
}$$
Una pausa para aclarar que $L$ es el Laplaciano de $C$ y las matrices $(A,B,C,G,L)$ son todos simétrica.
$$\eqalign{
df &= -L:(dX^TX+X^TdX) \\
&= -2L:X^TdX \\
&= -2XL:dX \\
&= -2\mu^{-1}IL:(\mu^{-1}dY - \mu^{-3}Y(Y:dY)) \\
&= 2\mu^{-2}\Big(\mu^{-2}(YL:Y)Y - YL\Big):dY \\
&= 2\mu^{-2}\Big((G:L)Y - YL\Big):dY \\
\frac{\partial f}{\partial Y}
&= 2\mu^{-2}\Big((G:L)Y - YL\Big) \\
}$$
Desde $Y$ libre, estableciendo que el gradiente de cero se obtiene un primer orden de la condición de optimalidad.
$$\eqalign{
YL &= (G:L)Y \;=\; \lambda Y \\
LY^T &= \lambda Y^T \\
}$$
Este tiene la forma de un autovalor problema, excepto que $L$ es una función no lineal de $Y$.
Sin embargo, la relación pone de manifiesto que ambas filas de $Y$ debe ser vectores propios de $L$ se asocia con algún autovalor de multiplicidad $>1$.
Desde $L$ es un Laplaciano, ${\tt1}$ está garantizado para ser un autovector de $L$ asociado con $\lambda=0.$
Si $\operatorname{rank}(L)\le(n-2)$ luego hay otros vectores en el nullspace de $L$ que puede ser utilizado en la segunda fila. Cuando se representa una solución de este tipo podría aparecer como una línea vertical, ya que la primera componente de cada una de las $x_i$ vector será idéntica.
Resumen
- El original restringido problema se puede convertir en un sin restricciones
problema.
- Todas las soluciones deben satisfacer los pabellones de conveniencia en la forma de
una no lineal EV problema.
- A pesar de su naturaleza no lineal, uno eigenpair
$\big(\{\lambda,v\}=\{0,{\tt1}\}\big)$ ya es conocido.
- Iff un segundo eigenpair $\{0,v\}$ existe, entonces los puntos de la solución
$Y=\big[{\tt1}\;\;v\big]^T$ se encuentran en una recta.
- En cualquier caso, dos $v_k$ con el mismo $\lambda$ son necesarios para
una solución de $Y=\big[v_1\;\;v_2\big]^T$
- Soc deberá ser calculado y se evalúa para determinar si un
en particular FOC solución representa un (local) mínimo o máximo.
Otra manera de enfocar el problema es tratar a cada una de las $x_i$ , como un complejo de escalar en lugar de un verdadero vector. Entonces, en lugar de la matriz $X\in{\mathbb R}^{2\times n}$ el análisis se centrará en los complejos de vectores $z\in{\mathbb C}^{n}$.
Es un sencillo ejercicio para numéricamente verificar que los vértices de un polígono regular $(Y_{poly})$ satisfacer las no lineales EV ecuación.
También es fácil de perturbar $Y_{poly}$ y cheque por cerca de $Y$'s con un pequeño objetivo. De esta forma se comprueba que $Y_{poly}$ es un mínimo, sin necesidad de encontrar la Soc.
#!/usr/bin/env julia
using LinearAlgebra;
n = 5 # a pentagon
u,v = ones(n,1), 2*pi*collect(1:n)/n
c,s = cos.(v+u/n), sin.(v+u/n) # add u/n to avoid 0-elements
Y = [c s]'; X = Y/norm(Y); G = X'X; g = diag(G);
A = g*u' + u*g' - 2*G
B = A+I; C = B.^(-3/2); L = C - Diagonal(vec(C*u));
# verify that Y solves the EV equation (via element-wise quotient)
Q = (L*Y') ./ Y'
-15.3884 -15.3884
-15.3884 -15.3884
-15.3884 -15.3884
-15.3884 -15.3884
-15.3884 -15.3884
# the eigenvalue is -15.3884
# now verify that the constraint is satisfied
tr(G)
0.9999999999999998
# objective function
function f(Y)
m,n = size(Y)
X = Y/norm(Y); G = X'X; g,u = diag(G), ones(n,1)
A = g*u' + u*g' - 2*G; B = A + I
return sum(B.^(-0.5)) - n
end
# evaluate at *lots* of nearby points
fY,h = f(Y), 1e-3 # "nearby" is defined by h
extrema( [f(Y+randn(size(Y))*h)-fY for k=1:9999] )
(2.056884355283728e-6, 0.00014463419313415216)
# no negative values ==> f(Y) is a minimum
#
