Mínimo cuadrado dada la restricción sobre los subcomponentes

Question

Hola a todos,

Tengo que encontrar un conjunto de parámetros que se ajusten a un conjunto de datos con restricción a un subconjunto de los parámetros. En resumen, quiero resolver $\min ||A[x_1 \, x_2]^T -b ||$ dado $||x_2|| = g$ .

Pensaba que el problema era trivial, pero resulta que no lo es en absoluto. El método del multiplicador de Lagrange da una ecuación matricial muy complicada (que yo todavía no puedo resolver). Cualquier idea, o solución numérica / analítica, es muy apreciada.

Gracias.

Answer 1

Escribir $A = [A_1 A_2]$ y tomando sin pérdida de generalidad $g=1$ (escala $A_2$ adecuadamente), su problema equivale a $$\min_{x_1,x_2}\ ||A_1 x_1 + A_2 x_2 - b||^2 \text{ s.t. } ||x_2||=1.$$ Obsérvese que la solución de $\min_{x_1} ||A_1 x_1 - c||^2$ puede obtenerse de forma cerrada (suponiendo independencia de columnas en $A_1$ ): es igual a $c^T P_1 c$ con $P_1 = I - A_1 (A_1^T A_1)^{-1}A_1^T$ (nota $P_1$ es semidefinida positiva). Ahora basta con resolver $$\min_{x_2}\ (b-A_2 x_2)^T P_1 (b-A_2 x_2) \text{ s.t. } ||x_2||=1$$ que puede hacerse con técnicas estándar. No estoy seguro de que se pueda obtener una solución de forma cerrada, pero se puede, por ejemplo, obtener una ecuación escalar en el multiplicador de Lagrange, que se resuelve numéricamente, y luego obtener $x_2$ . Véase también enlace donde el problema se reduce a un problema cuadrático de valores propios.

Answer 2

Puede expresar este problema como programa cuadrático con restricciones cuadráticas (QCQP). Lamentablemente, debido a la restricción de igualdad, el QCQP no será convexo. Sin embargo, en la página de Wikipedia se explica cómo tratar los QCQP no convexos, y si se busca en Google se encontrará más información. Este artículo " Relajaciones y métodos aleatorios para QCQP no convexos "El ejemplo 1.2.1 del documento es muy similar a su problema.

Answer 3

¿Has probado un algoritmo newton simple (con la restricción añadida al algo)?

Sea $(\alpha_{k})$ definirse como: $\alpha_k=1/k^2$

Inicialización :

$x^0=[0,...,0]$

Compute $H=(A^* A)^{-1}$

Bucle para $k$ en $1:m$

$x^k=x^{k-1}-\alpha_k H A^*(Ax^{k-1}-b)$

$x^{k}=g*x^{k}/\|x_2^k\|$

fin del bucle for

Evidentemente, hay formas más adaptables de elegir $\alpha_k$ ... pero quizá no necesites tanta sofisticación para resolver un problema de minimización de normas. Si $A^* A$ tiene valores propios muy pequeños, puede utilizar $H_k=(A^* A+\epsilon_k)^{-1}$ en lugar de $H$ ( $\epsilon_k$ decreciente hasta cero)...

Nótese que este tipo de código es relativamente general cuando se quiere encontrar el punto de silla de un lagrangiano y se sabe cómo encontrar los máximos con respecto a los multiplicadores de Lagrange (en el espacio dual) (segundo paso del bucle) pero se necesita un descenso de gradiente (o aquí algo de Newton) para encontrar los mínimos en el espacio principal.

Aquí está el código R correspondiente:

A=t(array(1:1000,c(10,100)))
m=100; b=1:10; g=3; l=5; p=10;
alpha=1:m
alpha=1/alpha^2
x=array(0,c(m,p))
H=t(A)%*%A
svdH=svd(H)
H=svdH$v%*%diag(1/svdH$d)%*%t(svdH$u) 
for (k in 2:m)
{
    x[k,]=x[k-1,]-alpha[k]*H%*%(t(A)%*%(A%*%x[k-1,]-b))
    x[k,]=g*x[k,]/sqrt(sum(x[k,(l+1):p]^2))
    print(sum((A%*%x[k,]-b)^2))
}

Answer 4

Primero eliminar $x_1$ resolviendo un mínimo cuadrático ordinario, y luego hay que esencialmente resolver un problema de la forma $\min x_2^TMx_2$ s.t. $\|x_2\|=g$ para que sea apropiado $M$ . Este problema es el famoso subproblema de la región de confianza , alias, TRS.

Por favor, eche un vistazo a las siguientes referencias (y sus referencias), que proporcionan algoritmos y discusiones sobre cómo resolver este tipo de problemas; quizás pueda simplificar o adaptar alguno de sus métodos:

1. LSTRS: http://ta.twi.tudelft.nl/wagm/users/rojas/lstrs-paper.pdf
2. Algoritmo Moré-Sorensen TRS (en el libro sobre subproblemas Trust-region)
3. http://www.optimization-online.org/DB_HTML/2002/09/530.html

Dependiendo del tamaño $A$ o qué tipo de estructura tiene, es posible que se prefieran distintos métodos de SRT. Por ejemplo, para matrices pequeñas, en las que puedes permitirte hacer Cholesky, el método More-Sorensen suele ser muy difícil de superar. Sin embargo, si la matriz es grande y dispersa, es posible que prefiera el método LSTRS.