4 votos

Cómo proyectar un vector sobre un conjunto definido por desigualdad lineal restricciones a través de condiciones KKT?

Necesito encontrar la proyección de $x \in \mathbb{R}^{k}$ de un vector $z \in \mathbb{R}^{k}$ en el conjunto definido por $Y \cdot x \geq 0$ donde $Y$ es un (dado pero no específicos de la propiedad) de la matriz de tamaño $m \cdot k$.

Yo primero construir el Lagrangiano de la siguiente manera :

$$L=\frac{1}{2} ||x-z||^2 -\sum_{i=1}^m \lambda_i Y(i,:)x$$ and set its gradient w.r.t. $x$ to $0$ which leads to $$x=z+\sum_{i=1}^m \lambda_i Y(i,:)^T$$

Las restricciones de la desigualdad agrega un adicional de KKT condición :

$$\lambda_i \cdot Y(i,:)x=0 \; \forall i=1,...,m ; \lambda_i \geq 0$$

La sustitución de $x$ dentro de da $$\lambda_i \cdot Y(i,:)[z+\sum_{i=1}^m \lambda_i Y(i,:)^T]=0 \; \forall i=1,...,m$$

Es donde se hace más difícil para mí. Supongo que cualquiera de las $\lambda_i$ o $Y(i,:)[z+\sum_{i=1}^m \lambda_i Y(i,:)^T]$ debe ser igual a $0$ pero luego me he atascado. De hecho, la segunda condición es un escalar producto de la vinculación de todos los $\lambda_i$ y no sé cómo lidiar con él de forma adecuada. Cualquier ayuda apreciada

1voto

P. Quinton Puntos 172

Está a la derecha (hasta los índices de re-etiquetado), $Y(i,:)[z+\sum_{j=1}^m \lambda_j Y(j,:)^T]=0$ o $\lambda_i=0$ cualquier $i$, Vamos a $\mathcal S=\left\lbrace i : Y(i,:)[z+\sum_{j=1}^m \lambda_j Y(j,:)^T]=0 \right\rbrace$, luego \begin{align*} x = z + \sum_{i\in\mathcal S} \lambda_i Y(i,:)^T \end{align*} Esto satisface las condiciones KKT y es tu solución. Usted no puede obtener una mejor forma, excepto si $Y$ se compone de columnas ortogonales o similares condiciones.

Problemas para el $\lambda$ parámetros requiere que usted para resolver el sistema de $|\mathcal S|$ ecuaciones lineales \begin{align*} Y(i,:)[z+\sum_{j=1}^m \lambda_j Y(j,:)^T]=0&&\text{for } i\in\mathcal S \end{align*} Así que es un poco de auto loop argumento. Pero la solución de estas ecuaciones es numéricamente fácil y se puede hacer de manera eficiente si la matriz $Y$ tiene algún tipo de estructura.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X