Tarefa 3: explicações adicionais

tarefa3	PostScript compactada - 77049 b
tarefa3	PDF compactada - 67669 b

Objetivos: separar linearmente conjuntos (Ca e Cb) de pontos do Rⁿ

• Ca = {a¹, a², ..., a^m},   Cb = {b¹, b², ..., b^k}     (aⁱ e b^j pontos do Rⁿ)
• A = [ (a¹)^t; ...; (a^m)^t]m x n,   B = [ (b¹)^t; ...; (b^k)^t]k x m,
• resover: min 1'u + 1'v, (a,b,u,v) em P   e   max a + b, (w,a,b) em D (a e b escalares)
  

                  Primal: (P)                      |  Dual: (D)
                  +-             -+ +- -+   +- -+  |              +-      -+ +- -+    +- -+
      n linhas -> | A' -B' -I  I  | | a |   | 0 |  |  m linhas -> |  A 1 0 | | w |    | 0 |
      1 linha  -> | 1'  0'  0' 0' | | b | = | 1 |  |  k linhas -> | -B 0 1 | | a | <= | 0 |
      1 linha  -> | 0'  1'  0' 0' | | u |   | 1 |  |  n linhas -> | -I 0 0 | | b |    | 1 |
                  +-             -+ | v |   +- -+  |  n linhas -> |  I 0 0 | +- -+    | 1 |
                                    +- -+          |              +-      -+          +- -+
                  (a,b,u,v) >= 0                   |  (w,a,b) livres
                  (a,b,u,v) em Rm x Rk x Rn x Rn   | (w,a,b) em Rn x R x R
                  

Exercício: prove que de fato (D) é dual de (P) e vice-versa

Interpretação geométrica

• Primal (P)
  Reescrevendo o problema (P), notamos que ele é equivalente a seguinte forma simplificada

  min 1'u + 1'v = || z ||_1
              A'a - B'b - u + v = 0 <=> A'a - B'b + z = 0, z = z+ - z-
                                                               (u = -z- e v = z+)
              1'a               = 1  (logo o vetor a pega ponto no casco convexo de A'
                    1'b         = 1  (e b pega em [B'] (A'a é um pt em [A'] e B'b em [B'])
    

  
  Atenção: havia um erro na segunda linha do problema acima, estava A'u - B'v + z = 0     [01/12/2003]

  Neste caso o z é a diferença entre pontos nos dois cascos (z=A'a - B'b) convexos, logo este problema é encontrar o pontos mais próximo nos cascos.

• Dual (D)
  Da mesma forma, reescrevendo o problema (D), chega-se a forma mais "simples"

   max a + b
               A w + a 1 <= 0          => A w <= -a 1
              -B w + b 1 <= 0          => B w >=  b 1
  	      -w       <= 1 (vetor)  => -1 <= w <= 1 => || w ||_oo <= 1
  	       w       <= 1 (vetor)  =>                 norma infinita de w
     

  Neste caso, procura-se um vetor w que separe os pontos A' e B', ou seja, cada vetor coluna de A' esteja no semi-espaço {x : w'x <= -a} e cada vetor coluna de B' esteja no semi-espaço {x : w'x >= b}.

 
Conclusão:

Em (D), se b-a > 0, então os pontos A' e B' são separáveis.
Em (P), se valor ótimo também for estritamente positivo, os cascos convexos não têm interseção, logo são separáveis.