MAC-499 - Trabalho de Formatura Supervisionado
|
|
Monografia
apresentada ao Departamento de Ciência da Computação do Instituto de
Matemática e Estatística da Universidade de São Paulo como requisito parcial
para obtenção do grau de Bacharel em Ciência da Computação |
Objetivo
O meu trabalho de formatura trata
de uma atividade inicialmente motivada por um estágio que venho fazendo desde
abril de 2000 até os dias de hoje em uma renomada empresa de consultoria para
investimentos financeiros (atualmente consultora da Secretaria de Previdência
Complementar – Governo Federal), a PPS
Portfolio Performance. Após conversa com o meu orientador, em abril de
2001, resolvemos estender tudo o que foi feito no estágio por meio de um
projeto de Iniciação Científica no qual a teoria se encontrava com a prática.
Este trabalho, que foi submetido em novembro de 2001 ao 9º Siicusp e foi
premiado com uma menção honrosa, é bem completo, iniciando com definições
básicas de otimização em finanças, mostrando a evolução do pensamento humano na
teoria de finanças e culminando na explicação de um algoritmo de Programação
Não Linear consagrado com o Prêmio Nobel em 1990, além de mostrar seu vasto
campo de aplicações.
Para concluir o trabalho, fizemos
uma breve digressão sobre as limitações do modelo estudado e mostramos uma
possível extensão, que é atualmente tema de estudos e pesquisas recentes.
Estrutura do Trabalho
O
trabalho possui um pouqinho mais do que 5.000 palavras e está dividido na
seguinte estrutura de tópicos:
Ø Definições
Básicas
o
O Problema Clássico de Finanças
o
Estendendo o Problema
Ø Métodos
para Resolver o Problema Quadrático
o
Formulação de um Modelo Quadrático
o
O Método de Wolfe
o
A Versão Paramétrica
o
Um estudo de caso.
o
Aplicações do Modelo Quadrático
o
Limitações do Modelo Quadrático
Ø Assimetria
de Portfolios
o
Formulação do Modelo
o
Possíveis Temas para Pesquisas Futuras
Ø Referências
Bibliográficas
Uma versão html do trabalho pode
ser encontrada aqui. Também há disponível para download
versões PostScript e Adobe PDF. An
English version is also avaiable in PS or Adobe PDF, submitted for publication in the Citeseer - The NECI Scientific Literature
Digital Library. Também desenvolvemos um programa didático, o
M.A.R.R.E.Q.O. (Master Advanced Research in a Routine of Efficient Quadratic
Optimization), que funciona em ambiente Windows e no qual é possível submeter
um problema quadrático qualquer e obter a solução passo a passo, enxergando
todas as mudanças de base do Simplex. Para fazer o download, clique aqui.
A Iniciação Científica
Como já dito anteriormente, a idéia de
fazer uma iniciação científica surgiu do que eu faço no meu estágio. Pensamos
em estender o que era feito e criar uma implementação de um modelo mais
sofisticado. Mais adiante irei fazer uma descrição mais detalhada do meu estágio,
no entanto, neste momento irei ater-me somente à Iniciação Científica.
Sem dúvida o primeiro desafio que
enfrentei foi começar o projeto. Tomamos como ponto de partida o modelo que eu
estava usando no estágio. Mas professor Ernesto é um tanto exigente e quando eu
fui apresentar o que eu fazia, ele não aceitou uma palavra enquanto eu não
provasse formalmente que tudo o que era feito estava correto. Na verdade nem eu
sabia se tudo o que era feito estava correto ou não. E muito menos sabia provar
que tudo estava correto. Apenas li o livro, implementei, o chefe ficou contente
e começamos a usar para os clientes. E para demonstrar tudo, tive que ler mais
do que o livro, pois ele pulava algumas demonstrações. Isso iniciou minha
capacidade de pesquisa. Demorei mais ou menos uns dois meses para terminar a
primeira parte.
Foi um alívio descobrir que tudo
realmente estava correto.
O modelo que eu tinha implementado no
estágio realmente tinha muitas limitações, aliás tinha mais limitações do que
aplicações, mas foi implementado por ser o mais fácil de se entender e fazer.
Eu já estava ciente de tais limitações. E estava ciente de que o professor
Júlio Stern havia implementado um modelo bem completo, o mais conhecido no
mundo de finanças devido à sua aplicabilidade e resultados e o menos entendido
devido à sua complicação. Então, juntamente com o professor Ernesto, o objetivo
da iniciação foi lançado: entender este modelo, explica-lo, implementa-lo,
usa-lo com dados reais e tirar conclusões.
Uma frustração encontrada neste trabalho
foi a falta de companheiros de grupo para dividir as tarefas. Se poucas pessoas
se interessam por programação linear, para programação não linear então devem
ter dois ou três alunos por turma que se interessem! O trabalho teve que ser
tocado individualmente, ou melhor, em conjunto somente com o orientador. Só
houve uma pequena reunião com a Cibele, uma ex-aluna de mestrado do professor
Júlio, onde discutimos aplicações de otimização no ramo de finanças, incluindo
a dissertação de mestrado dela e o seu atual projeto de tese de doutorado. Esta
reunião foi muito importante e produtiva. Dela surgiu a idéia de incluir no
trabalho limitações do modelo e temas para pesquisas futuras.
Como eu já havia dito, o meu orientador
é bem exigente. Os relatórios e transparências para as reuniões exigidos por
ele tinham que ser bem detalhados e nenhuma das conclusões que eu tirasse era
considerada válida enquanto uma prova formal não fosse esboçada. Isto foi um
grande desafio, todavia foi muito proveitoso porque me incentivou a pesquisar e
eu acabei até entendendo mais do assunto.
Algumas disciplinas tiveram uma
aplicação direta com o projeto, as quais mencionarei depois, mas posso
ressaltar que a formação matemática oferecida pelo BCC foi extremamente
importante. Apenas as partes mais técnicas do curso, como Sistemas Operacionais
e Programação Concorrente, não foram aplicadas no decorrer do projeto. Os
conceitos estudados durante a graduação e principalmente a
"imposição" por parte de alguns professores de que devemos demonstrar
tudo matematicamente teve uma forte aplicação no projeto. Isto não significa
que eu goste disso. Até hoje me encontro discutindo com meu ex-professor de
Programação Linear, o professor Leonidas, e eu consistentemente falo que não é
de tanta importância ter que ser tão correto formalmente. Ele argumenta que só
assim o aluno compreende mais. Às vezes, quando olho para alguns problemas a
resolver e vejo que me falta alguma base, eu concordo com a opinião do
professor. Mas em outras ocasiões, minha opinião continua a mesma - de que não
é necessário ter que demonstrar tanto as coisas.
Pretendo continuar estudando um tema
correlato durante o mestrado. Atualmente estou inscrito para o mestrado em
Estatística aqui no IME. Com base na experiência durante a iniciação, vejo que
para aprimorar minha capacidade de pesquisa, eu tenho que ouvir mais o meu
orientador, afinal a experiência dele é bem maior que a minha. Também tenho
certeza que se eu quiser me aprofundar neste tipo de atividade, minha opinião
sobre as demonstrações vai ter que mudar mais um pouco. No começo da graduação
eu achava que demonstrar as coisas era totalmente inútil. Agora, já acho que é
útil mas nem tanto. Creio que estou em um dos estados da evolução. Acho que com
o tempo e a experiência adquirida no mestrado, minha opinião vai mudar mais um
pouco.
Cronograma das Atividades Desenvolvidas
Ø Março:
definição do orientador e do tema a ser seguido no trabalho.
Ø Abril e Maio:
apresentação de um modelo inicial e demonstração de que ele é correto.
Ø Junho:
apresentação de um modelo quadrático para solução de uma instância do problema
em particular.
Ø Julho: apresentação
de um modelo quadrático paramétrico para obtenção da solução geral.
Ø Agosto: discussão
de limitações do modelo, extensões para pesquisas futuras e início da
elaboração da parte técnica da monografia.
Ø Setembro:
implementação do algoritmo e criação do M.A.R.R.E.Q.O.
Ø Outubro: elaboração
do estudo de caso e término da parte técnica da monografia.
Ø Novembro:
apresentação do trabalho à comunidade científica.
O IME na Elaboração do Trabalho
Ao
contrário do que a maioria absoluta dos alunos diz, foi a sólida formação
matemática oferecida pelo BCC que me ajudou a desenvolver tanto as atividades
do meu estágio quanto as atividades da Iniciação Científica com a maior
segurança possível. Disciplinas como Banco de Dados, Engenharia de Software,
Sistemas Operacionais e Programação Concorrente tiveram uma importância quase
nula nas minhas atividades – o que não significa que elas são inúteis, mas sim
que elas têm pouca relação com a área de Otimização Discreta, Contínua ou
Combinatória, na qual pretendo me especializar em um Mestrado ou Doutorado e,
principalmente, que EU NÃO GOSTO NEM UM POUCO DELAS.
Excetuando-se
as disciplinas fora de área, que não fazem parte do BCC e foram cursadas por
minha opção, as disciplinas que cursei e tiveram maior importância no meu
trabalho foram as seguintes:
Ø
Programação
Linear
A tão odiada dos alunos do BCC
foi a que mais me salvou. Na área financeira a maioria dos problemas são não
lineares, em particular quadráticos, mas os métodos de solução são baseados nas
condições de Kuhn-Tucker, que, para funções quadráticas e convexas, são
vértices de poliedros lineares. Assim, saber bem o Simplex é fundamental. Para
se ter uma idéia, o algoritmo que ganhou Premio Nobel em 1990 é simplesmente um
Simplex modificado, mas que consegue resolver quase tudo no campo de finanças.
Todavia, provar que o Simplex funciona não é nem um pouco importante, e foi
isto o que mais foi ensinado quando fiz Prog Lin.
Ø
Métodos
Numéricos da Álgebra Linear
Resolver bem sistemas lineares
para os diversos casos, saber lidar com matrizes positivas definidas e fazer
fatorações QR e LU é fundamental. Méritos para o Prof. Ernesto, que foi o meu
professor desta disciplina.
Ø
Métodos
de Otimização em Finanças
A disciplina do Prof. Júlio foi
muito importante, principalmente a parte introdutória e o material fornecido
(apostilas, dissertações e teses de ex-alunos).
Ø
Introdução
à Probabilidade e Estatística I e II
Todas as definições estudadas no
curso básico de estatística são ampla e diretamente utilizadas nos estudos de
otimização financeira.
O Estágio
Se para a Iniciação Científica eu acho
que demonstrar o que se aprende não é tão útil assim, para trabalhar com isso
tenho quase a certeza de que demonstrar a teoria não é necessário. Pelo menos
no meu estágio, tanto eu quanto meus superiores não se preocuparam muito em
saber explicar a teoria, limitamo-nos a usa-la.
Trabalho desde abril de 2000 em uma
consultoria financeira, a PPS. A principal especialidade desta empresa é fazer
análises de fundos de investimentos. Para isto, são usadas não só técnicas
aprendidas em um curso de economia, mas também técnicas aprendidas aqui no BCC,
como por exemplo técnicas de classificação de formas são aplicadas para
classificação de fundos. Além disso damos consultoria de investimentos em renda
variável, gerando conjuntos de investimentos ótimos - tema do meu trabalho de Iniciação
Científica. Esta última função é recente, e há um projeto para que a PPS vá
além de dar consultoria e passe a administrar fundos de investimento. Além de
consultoria, a PPS possui um software financeiro que é vendido para outros
investidores em fundos e também é utilizado pelos consultores da PPS durante
sua análises. A PPS também executa outros serviços financeiros, apenas citei
sucintamente os principais.
Atualmente,
os principais clientes da PPS são:
Ø Secretaria
de Previdência Complementar – Governo Federal;
Ø Banco
Europeu para a América Latina;
Ø Wolksvagen
Previdência Privada;
Ø Fundação Celos;
Ø Fundação
Previbayer.
Quando eu fui contratado pela PPS, eu
fui contratado para exercer a função de programador. O software da empresa
tinha um problema crítico, que era a demasiada demora na rotina de cálculos.
Meu primeiro desafio era descobir e solucionar esta demora, uma tarefa que já
outros três ou quatro programadores que vieram antes de mim tentaram executar mas
fracassaram. Graças a Deus e ao sólido conhecimento de programação obtido nas
disciplinas básicas, consegui achar o defeito (era uma falha de programação
básica no acesso ao banco de dados de cotas) e isto me abriu uma grande porta
na empresa. Além disso, facilitou-me a vida o fato de eu já estar familiarizado
com o ramo de investimentos e gostar de otimização. Foi um prato cheio para mim
e para a PPS.
Não tenho reclamações da empresa sobre
falta de tempo ou recursos humanos. Os prazos são determinados na maioria das
vezes por mim. Melhor dizendo, os chefes solicitam uma determinada
implementação e eu faço uma pequena pesquisa do que se deve ser feito e quanto
tempo eu acho que demora para executar tudo, apresentando os resultados aos
chefes. Na maioria das vezes eles concordam com os prazos estipulados e tudo
corre perfeitamente. É claro, já ocorreram situações onde pedi um prazo muito
menor do que o necessário ou a minha estimativa de prazo não condizia com a
necessidade deles. Aí não tem jeito, tive que trabalhar durante sábado,
domingo, madrugada...
Trabalhar na PPS foi muito bom para a
minha carreira acadêmica e profissional porque na PPS eles não querem apenas um
implementador. É necessário pesquisar bastante antes de implementar. As
implementações em sua maioria são de algoritmos matemáticos, o que demanda
muita capacidade de pesquisa. Até mesmo meu desempenho na faculdade melhorou
sobremaneira pelo fato de estar trabalhando na PPS. Considero lá apenas uma
extensão das atividades de pesquisa feitas na universidade.
Pretendo continuar atuando na área em
que trabalho, provavelmente na mesma empresa.
O IME na Execução do Estágio
As mesmas disciplinas que usei para
fazer o trabalho de Iniciação Científica foram usadas durante a execução do
estágio. Todavia, o estágio engloba mais coisas do que o projeto feito com o
professor Ernesto.
Recentemente resolvemos implementar
coisas novas para a consultoria, e dentre elas resolvemos implementar algum
tipo de classificação não supervisionada de fundos de investimento, da mesma
maneira que se faz para formas. Para implementar tais algoritmos, outras duas
disciplinas foram muito utilizadas e eu não gostaria de deixá-las fora do meu
relatório:
Ø
Algoritmos
em Grafos
Eu achei muito interessante ter
conseguido aplicar grafos em finanças. Mais precisamente, precisei implementar
um algoritmo de detecção de componentes em grafos não dirigidos. Durante a
implementação, montamos um grafo de distâncias, onde cada nó do grafo é um
fundo de investimento e cada aresta contém uma distância (medida de diversas
formas por meio de características peculiares dos fundos de investimento) entre
dois fundos. Dois fundos só estão ligados por tal aresta se ela a distância a
ela associada for menor do que um determinado limiar. O que queremos são os
componentes deste grafo, que são as classes de fundos de investimento.
Durante o
curso de grafos aqui no BCC não aprendi algoritmos que lidassem com grafos que
tivessem um número alto de vértices (o número de fundos de investimento do
mercado: aproximadamente 10000) e muito mais alto de arestas. Todavia
parabenizo o professor Paulo Feofiloff por ter instigado nos alunos um senso de
pesquisa, que foi suficiente para me fazer pesquisar e descobrir algoritmos
melhores para rotular componentes de grafos. Além disso, parabenizo o mesmo
professor por ter um site tão bem documentado. Também fiz MAC-122 com ele e até
os dias de hoje quando tenho alguma dúvida sobre partes básicas da matéria vou
consultar o seu site. Ele é um excelente professor, é uma pena que quando eu
tenha feito o curso não tenha aproveitado ao máximo.
Ø
Análise
e Reconhecimento de Formas
Os algoritmos apresentados pelo
professor Roberto Marcondes foram muito utilizados quando fui implementar um
algoritmo de classificação não supervisionada de fundos de investimento. Depois
eu pude estender o que era feito e implementar uma classificação supervisionada
com base no conjunto de treinamento obtido na análise de clusters inicial.
Outros conceitos que ele passou durante o semestre também foram utilizados.
Conclusões
Pude
aprender muito durante o estágio, que já havia começado desde antes do início
do trabalho de formatura. A experiência com o estágio em si já havia sido muito
boa, devido ao incentivo que é dado pela empresa à pesquisa. Imagino que isto
se deve principalmente ao fato de ambos os sócios serem professores, um deles
da FEA.
Todavia
o trabalho de formatura me propiciou uma experiência incomensurável,
instigando-me mais a pesquisar e me amadurecendo a capacidade de fazer
demonstrações matemáticas. Fiquei muito mais satisfeito por ter feito um
trabalho numa área que eu gosto e podendo aplicar de forma tão contundente a
teoria à prática. Sem dúvida, a formação matemática que o BCC dá a seus alunos
é muito importante, pois não só lhes fortalece o pensamento lógico e matemático
como os prepara para qualquer dificuldade inerente à profissão que possa
aparecer.
Agradecimentos
Não
poderia deixar de agradecer quem me ajudou durante todo este percurso. Sem
sombra de dúvidas, a primeira a que devo agradecimentos é a minha esposa, a
Keila, que me ajudou durante todo o BCC das mais diversas maneiras, até mesmo
comparecendo a aulas que não pude vir e tomando nota de todas, aprendendo a
lidar com estes editores de texto matemático para digitar equações nos mais
diversos trabalhos (por exemplo, nesta monografia), escrevendo as
transparências que utilizei durante apresentações do projeto (não foram poucas)
e também fazendo a minha comidinha, lavando e passando a roupinha e etc, além
de um grande apoio afetivo. Com certeza se eu não tivesse tanta ajuda dela
seria impossível estudar, trabalhar tanto em uma empresa externa como aqui na
USP e ainda quando surge serviço como free-lancer e além disso me
dedicar a um projeto complexo de iniciação científica.
Um
outro personagem de papel importante é o meu chefe, o Everaldo. Além dos vários
incentivos durante todo o tempo, despertou o meu interesse e capacidade de
pesquisa e estudos.
Na
seqüência dos agradecimentos ficam os meus professores Ernesto e Carlinhos, um
por ensinar bem e orientar bem durante todo o trabalho e o outro, com o qual
não tive o prazer de ter aulas, por ter me orientado bastante em questões acadêmicas,
inclusive na matrícula desta disciplina.
Por
fim, agradeço a Deus por ter me dado vida e saúde, além de ter colocado no meu
caminho as quatro pessoas acima.