teorema de dualidad débil

Question

Estudiando la teoría de la dualidad no he encontrado claro este punto

considerando el problema primario de minimización, si $x$ y $p$ son soluciones factibles para el primario y para el dual, entonces $p^tb \leq c^tx$

para cualquier vector $x$ y $p$ definimos

$u_i=p_i(a^t_ix-b_i)$

$v_j=x_j(c_j-p^tA_j)$

para la definición del problema dual el signo de $p_i $ debe ser el mismo del signo de $(a^t_ix-b_i)$ y el signo de $ x_j$ debe ser el mismo del signo de $(c_j-p^tA_j)$ así que $u_i$ y $v_j$ son ambos $\ge 0$ ...etc.

No entiendo por qué el signo debe ser el mismo y qué significan estas cantidades.

Answer 1

Para que lo entiendas, primero escribiré el problema primario y el dual en forma vectorial, luego demostraré el teorema de dualidad débil, y finalmente explicaré qué $u_i$ y $v_j$ para aclarar sus dudas.

\begin {array}{ll} \text {min} & c^t x \\ \text {s.t.} & Ax \ge b \\ & x \ge 0 \tag {P} \end {array}

\begin {array}{ll} \text {max} & b^t p \\ \text {s.t.} & A^t p \le c \\ & p \ge 0 \tag {D} \end {array}

Si piensas en $u_i$ y $v_j$ como componentes de vectores, a partir del lado derecho de estas dos ecuaciones, no es difícil ver que el escalar $x^t A^t p$ es el "hombre del medio".

$$b^t p \le x^t A^t p \le c^t x \tag{1}\label{pf}$$

La primera mitad de la desigualdad anterior proviene de la restricción primaria $Ax \ge b$ y la segunda mitad es de $A^t p \le c$ . Hemos terminado la demostración del teorema de dualidad débil. De la desigualdad anterior, tenemos

\begin {array}{r@{}c@{}l} 0 &{} \le (x^t A^t - b^t) p &{}= p^t (Ax - b) \\ 0 &{} \le c^t x - x^t A^t p &{}= x^t (c - A^t p) \tag {2} \label {eq2} \end {array}

Por lo tanto, comparando estas dos desigualdades con $u_i=p_i(\color{red}{A^t_i} x-b_i)$ y $v_j=x_j(c_j-p^tA_j)$ sabemos que

1. Para calcular $Ax - b$ necesitamos multiplicar el $i$ -en la fila de $A$ por $x$ . (es decir, el $i$ -en la columna de $A^t$ que se denota por $A_i^t$ . $p_i$ es simplemente el $i$ -a componente de $p$ y $u_i$ es el $i$ -término de la suma $p^t (Ax - b)$ .

2. Para calcular $c - A^t p$ necesitamos multiplicar el $j$ -en la fila de $A^t$ por $p$ . (es decir, el $j$ -en la columna de $A$ que se denota por $A_j$ . $x_j$ es simplemente el $j$ -a componente de $x$ y $v_j$ es el $j$ -término de la suma $x^t (c - A^t p)$ .

   • $p_i,x_j$ se deben a $x,p \ge 0$
   • $\color{red}{A^t_i} x-b_i \ge 0$ y $c_j-p^tA_j \ge 0$ se deben a $Ax \ge b$ y $A^t p \le c$ .
   • Es decir, tenemos $u_i=p_i(\color{red}{A^t_i} x-b_i) \ge 0$ y $v_j=x_j(c_j-p^tA_j) \ge 0$

La importancia de $u_i$ y $v_j$ es que nos permiten obtener \eqref {eq2}, lo que implica \eqref {pf}.