encontrar un elemento de un subespacio vectorial contenido en el primer ortante

Question

Dada una matriz $M$ Quiero encontrar un vector no trivial en el núcleo de $M$ que también está en el primer ortante, si es que existe tal vector. Es decir, quiero resolver simultáneamente

$$Mx = 0$$ $$x \geq 0$$ $$x \neq 0$$

Tengo problemas para plantear este problema de forma que se pueda resolver numéricamente de forma eficiente. Un enfoque que he intentado es resolver

$$\min_x \|Mx\|^2\quad s.t. \quad x\geq 0, x_i = 1$$

utilizando mínimos cuadrados no negativos para cada $i$ y buscando soluciones cuyo mínimo sea 0. Si el mínimo es positivo para cada $i$ El problema original no tenía solución. Por desgracia, además de ser ineficiente (tengo que hacer $\dim x$ resuelve), los paquetes estándar de mínimos cuadrados tienen grandes dificultades para converger para este enfoque.

¿Hay una forma mejor de resolver este problema?

Answer 1

Sí, se llama programación lineal . Como señala Anthony más arriba, tendrás que reformular un poco tu pregunta para que entre en este marco. Si realmente sólo quieres cualquier elemento de ese ortante, puedes minimizar $\sum x_i$ con respecto a las restricciones $x_i\geq 1$ y $Mx=0$ .

Answer 2

La respuesta de @Ben está dentro $\epsilon$ de correcto. El problema es que (dependiendo de cómo se interpreten las restricciones $x_i \geq 1$ ) es posible que no haya solución con un $x_{i_0} > 0,$ o todo $x_i>0,$ y como en la pregunta original, recorrer todos los índices es ineficienteEn su lugar se utiliza el teorema de Gordan (ver http://en.wikipedia.org/wiki/Farkas_lemma , "otras implicaciones"), que dice que la OP es equivalente a la existencia de una solución a $M^t y < 0,$ lo que equivale a $M^t y \leq -\mathbf{1}.$