============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Um método de Newton para o problema da mochila 
             quadrático contínuo

Palestrante: Paulo José da Silva e Silva
             Dep. de Ciência da Computação
             IME-USP

Hora e Data: 14h00, sexta-feira, 27 de novembro de 2009

Local:       sala 136 do bloco A

Resumo:

O problema da mochila quadrático contínuo é o problema se se
projetar um ponto sobre a intersecção de um hiperplano e uma
caixa  no R^n.   Usando dualidade  é fácil  transformá-lo na
resolução de  uma equação  envolvendo uma função  linear por
partes unidimensional.  Soluções tradicionais desse problema
podem ser obtidas usando variações de algoritmos de busca de
medianas   e  têm   complexidade  O(n).   Porém   há  outros
algoritmos, com  caráter de métodos  iterativos, que, apesar
da  complexidade de  pior  caso ruim  O(n^2), são  bastantes
competitivos em aplicações.  Apresentamos um novo algoritmo,
baseado no  método de Newton que  tem convergência garantida
em casos particulares importantes  e que pode ser facilmente
adaptado  para  lidar  com  o caso  geral.  Faremos  algumas
comparações com métodos mais  tradicionais tanto em bases de
testes aleatórias como em um problema prático de treinamento
de máquinas de suporte vetorial.

Esse  trabalho foi  desenvolvido  em  conjunto  com   Walter
Mascarenhas (IME/USP) e  Roberto Cominetti  (Universidade do
Chile)