"Dividir" los dos lados de una desigualdad por un vector

Question

Tan ridículo como la pregunta suena, me estoy refiriendo a un caso específico. Supongamos que estoy dado de dos $n \times 1$ vectores $x$$c$, $m \times n$ matriz $A$ $m \times 1$ vector de $y$, y la siguiente desigualdad:

$$c^Tx \geq y^TAx$$

Si $x \geq 0$ (todos sus componentes se $\geq 0$), intuitivamente parece deducirse que las $c^T \geq y^TA$ y que, por ende,$c \geq A^Ty$. Es incorrecto decir que "se multiplican ambos lados por $x^{-1}$" porque no hay ninguna noción de la inversa de un vector de columna como tal. Es allí cualquier rigurosa justificación para:

$$c^Tx \geq y^TAx \implies c^T \geq y^TA$$

siempre que $x$ es no negativo (o para revertir la desigualdad anterior si $x$ es negativo)?

(Aclaración: Por $a \geq b$ donde $a, b \in \mathbb{R}^n$, me refiero a que $a_i \geq b_i$ todos los $i = 1, 2, \ldots, n$.)

Answer 1

Si todos los términos de la (columna) de los vectores $\mathbf x,\mathbf y$ son no-negativos, $\mathbf y^T\mathbf x$ es no negativo.

No es cierto, sin embargo, que si todos los términos de $\mathbf x$ son no negativos, y $\mathbf y^T\mathbf x\geq 0$ que todos los términos de $y$ son no-negativos.

Por ejemplo, $$\begin{align}\mathbf x&=\begin{pmatrix}1\\1\end{pmatrix},\\\mathbf y&=\begin{pmatrix}2\\-1\end{pmatrix}.\end{align}$$ o] Así que usted no puede cancelar $x$ $y^Tx\geq \mathbf 0^T x,$ por ejemplo.

Básicamente, usted está diciendo que el si $x\geq 0$ (para algunos definición de $\geq$) y $(c^T-y^TA)x\geq 0$ $c^T-y^TA\geq 0,$ lo cual no es cierto.

---

Una Visualización

El signo de $\mathbf y^T\mathbf x$ es el mismo que el signo del coseno del ángulo entre los dos. Por lo $\mathbf y^T \mathbf x\geq 0$ significa que el ángulo es menor que $\frac{\pi}{2}.$

También, $\mathbf x\geq 0$ sólo significa que $x$ está en la no-negativo cuadrante, octante, etc., dependiendo de la dimensión.

Pero cualquiera de las $\mathbf x$ en el cuadrante tiene un $\mathbf y$ tal que $\mathbf y^T\mathbf x>0$ $\mathbf y$ no está en el mismo cuadrante (octante, etc.)

Answer 2

$c^T x \geq y^T A x \Leftrightarrow vx =(c^T-y^TA)x \geq 0$.

Por lo tanto, debemos investigar al $vx = 0$ e al $vx > 0$.

El primer caso es bastante simple, como $x = 0$ (que no es siempre el caso) o debemos exigir $v = 0$, de modo que $c^T = y^T A$.

Para el segundo caso, podemos utilizar la definición geométrica que $vx = |v|\cdot|x|\cdot cos(\theta) > 0$ siempre $-\pi/2 <\theta < \pi/2$. Visualizar, si $x$ es un vector, podemos imaginar algunos $n-1$-dimensional de "avión" que $x$ es perpendicular a. A continuación, $vx$ es positivo cuando se $v$ puntos para el mismo lado de la "plano" como $x$. Si cada componente de $x$ es no-negativo, pero no todos los $0$, $x$ se encuentra en el primer orthant (generalizada cuadrante). Por lo tanto, si $v$ también está en el primer orthant y $v\neq0$, $vx$ será positivo. Sin embargo, es claro que hay otros $v$ que no se encuentran en la primera orthant pero aún están en el mismo lado de la "plano" como $x$ es.

Para ver esto, dibuje un $xy$-plane, y dibuje una flecha desde el origen en el primer cuadrante, llamado $x$. Entonces, el "avión" es la línea que pasa por el origen, que es perpendicular a $x$. Finalmente, cualquier vector $v$ que comienza en el origen y se mantiene en el mismo lado de la línea como $x$ tienen $vx > 0$.

Disculpa la crudeza del dibujo:

Answer 3

Un poco más cuantitativa de la respuesta:

Al $x$ está normalizado, podemos aplicar la desigualdad de triángulo para encontrar que $$|(a-b)^{T}e_{i}-(a-b)^{T}x|=|(a-b)^{T}(e_{i}-x)|\leq \|a-b\|\sqrt{2(1-x^{T}e_{i})},$$ so $$(a-b)^{T}e_{i}\in (a-b)^{T}x\pm\|a-b\|\sqrt{2(1-x^{T}e_{i})},$$ which means that we have tighter control over the components $(a-b)^{T}e_{i}$ where $x$ and $e_{i}$ are close, as we would expect from intuition. In this sense, the worst case would be the constant vector $x=[1/\sqrt{n}]_{i=1}^{n},$ since this is equally far from all of the $e_{i}$s'.

Esto también nos permite ver de forma explícita el compromiso de la información: desde $\sum_{i=1}^{n}|x^{T}e_{i}|^{2}=1,$ al $1-x^{T}e_{i}$ disminuye, todos de la $x^{T}e_{j},\,j\neq i$ debe disminuir, por lo $1-x^{T}e_{j}$ de aumento para todos los $j\neq i$.