Existencia de una matriz semidefinite positiva que satisface un conjunto de restricciones de igualdad

Question

Dado los vectores $a_1, b_2, a_2, b_2 \in \mathcal{R}^{n\times 1}$, estoy interesado en encontrar una positiva semi-definida la matriz de $M \in \mathcal{R}^{n\times n}$, $M \succeq 0$, tal que $M\cdot a_1 = b_1$, $M\cdot a_2 = b_2$. Aquí $n \gg 2$, dicen $n = 1000 $. $a_1, a_2$ no son paralelas y no son cero.

Escribir en ecuaciones, quiero resolver el siguiente semidefinite programa

\begin{equation*} \begin{aligned} & \underset{M}{\text{minimize}} & & 0 \\ & \text{subject to} & & M\cdot a_1 = b_1 \\ && & M\cdot a_2 = b_2 \\ &&& M \succeq 0. \end{aligned} \end{ecuación*}

Dependiendo del valor de $a_1, b_2, a_2, b_2$, a veces un solucionador numérico informará de este programa es inviable ($M$ existe). He experimentado con varios solucionadores con idéntico resultado. Yo aún puede imponer ese $a_1^T\cdot b_1>0, a_2^T\cdot b_2>0$, pero el resultado es el mismo.

Una observación: Si $a_1, a_2$ son ortogonales, parece que el problema es siempre factible.

Mi intuición es que el número de variables libres en $M$$(n(n+1)/2 -n)$, debido a una matriz simétrica ha $n(n+1)/2$ variables libres, y positivo semidefiniteness requiere que todos los principales de los menores a ser positivo, añadiendo $n$ restricciones. Parece que esta afirmación no es correcta.

¿Cuál es el requisito de $a_1, b_2, a_2, b_2$ $M$ a existir?

Answer 1

Una manera de ver esto es para obtener el doble, y determinar las condiciones en las que el dual es no acotada---porque eso significa que el problema original no es factible.

El Lagrangiano es $$L(M,Z,\lambda_1,\lambda_2) = \lambda_1^T(M a_1-b_1)+\lambda_2^T(M a_2-b_2) - \langle M, Z \rangle$$ Donde el escalar multiplicadores de Lagrange $\lambda_1,\lambda_2\in\mathbb{R}^{n+1}$ no tienen restricción y $Z$ es positivo semidefinite. Por lo que la doble condición de optimalidad es $$\mathop{\textrm{sym}}(a_1 \lambda_1^T + a_2 \lambda_2^T) - Z = 0$$ donde $\mathop{\textrm{sym}}(Y)=(Y+Y^T)/2$, y el doble problema es \begin{array}{ll} \text{maximize} & - b_1^T \lambda_1 - b_2^T \lambda_2 \\ \text{subject to} & \mathop{\textrm{sym}}(a_1 \lambda_1^T + a_2 \lambda_2^T) - Z = 0 \\ & Z \succeq 0 \end{array} La eliminación de $Z$ rendimientos \begin{array}{ll} \text{maximize} & - b_1^T \lambda_1 - b_2^T \lambda_2 \\ \text{subject to} & \mathop{\textrm{sym}}(a_1 \lambda_1^T + a_2 \lambda_2^T) \succeq 0 \\ \end{array} Y vemos que este es acotada si existe $\lambda_1, \lambda_2$ tal que $$\mathop{\textrm{sym}}(a_1 \lambda_1^T + a_2 \lambda_2^T) \succeq 0, \quad b_1^T \lambda_1 + b_2^T \lambda_2 < 0$$ Si usted puede encontrar un par que satisface estas desigualdades, a continuación, puede simplemente escala $(\lambda_1,\lambda_2)$ por cualquier valor positivo a la unidad con el doble objetivo hasta el infinito. Y si puede hacer eso, la primera debe ser inviable. Dado que la escala es irrelevante, se puede fijar fácilmente en $b_1^T \lambda_1 + b_2^T \lambda_2 = -1$.

El nombre formal de este ejercicio es la derivación de un teorema de alternativas. Que es, exactamente una de las siguientes alternativas es verdadera [EDITAR: ver los comentarios, ni puede ser verdad]: $$\exists M \succeq 0 \quad \text{s.t.} \quad Ma_1 = b_1, ~ Ma_2 = b_2$$ o $$\exists \lambda_1, \lambda_2 \quad\text{s.t.} \quad \mathop{\textrm{sym}}(a_1 \lambda_1^T + a_2 \lambda_2^T) \succeq 0, \quad b_1^T \lambda_1 + b_2^T \lambda_2 = -1$$