MCZA014 -- Métodos de Otimização -- 2021.2

Atualizado em 25/05
Em construção (Página da edição de 2021.2 entra no ar.)

Expediente

• Professor: Aritanan Gruber
• Moodle: MD21.2
  (detalhes de andamento do curso, notas de aulas, links para artigos e vídeos das aulas, avaliações, notas, etc.)
• Atendimento: Qua 11–12h via Google Meet
  (você deve estar logado no Classroom (código: xswitg4) com sua conta da UFABC)
• Aulas assíncronas: vídeos em Aritanan Gruber’s YouTube

Ementa

Programação linear inteira. Modelos e métodos de otimização não linear. Modelos e métodos de otimização multiobjetivos.
Recomendação: Programação Matemática.

Nesta edição

Vamos estudar algoritmos para otimização convexa (contínua, não linear) e algumas de suas recentes aplicações em:

• aprendizado de máquina,
• otimização discreta (combinatória / inteira).

Muitos modelos da primeira são naturalmente convexos e resolvidos por tais algoritmos convexos. Surpreendentemente, algumas circunstâncias notoriamente não convexas (deep networks) são bem resolvidas por algoritmos convexos (stochastic gradient descent).

Na segunda, de forma igualmente surpreendente, alguns dos algoritmos mais eficientes do ponto de vista de complexidade computacional são baseados em cuidadosas relaxações convexas que exploram – e ao mesmo tempo, ignoram – a estrutura discreta do espaço das soluções viáveis.

O princípio do segredo? Em funções convexas, ótimos locais são ótimos globais!
Demais detalhes serão mostrados ao longo do curso.

Tópicos: Convexidade de conjuntos e funções. Otimização convexa, oráculos e eficiência. Dualidade e otimalidade. Métodos: gradient descent, accelarated gradient descent, stochastic gradient descent, mirror descent, multiplicative weights update, Frank-Wolfe’s, Newton’s, interior point, ellipsoid-based.

Nota: uma boa companhia / sequência pare este curso é um outro em análise convexa.

Avaliações e critérios

• 3 listas de exercícios individuais: $L_1, L_2, L_3\in[0,10]$
  média aritmética das 2 melhores; peso: 60%
• 1 projeto em dupla: $P\in[0,10]$
  peso: 40%

Nota nominal: $$ N = \frac{2}{5}P + \frac{3}{10}\max\left\{\sum_{j\in S}L_j\,:\,S\in\binom{3}{2}\right\} $$

Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$

Normalização

Sejam $\mu$ e $\sigma$ a média e o desvio padrão das notas $N$ atribuídas a todos os alunos. Cada aluno obterá uma nota normalizada: $$M = (N-\mu)/\sigma.$$

Conceito normalizado ($C_M$): reflete o seu desempenho perante os seus colegas; obtido pelo encaixe de $M$ em um dos intervalos: $$-\infty < \mathbf{F} < 0 \leq \mathbf{D} < \frac{1}{4} \leq \mathbf{C} < \frac{1}{2}\sigma \leq \mathbf{B} < \sigma \leq \mathbf{A} < \infty.$$

Considerando-se a ordenação $\mathbf{A} > \mathbf{B} > \mathbf{C} > \mathbf{D} > \mathbf{F}$, seu conceito efetivo (final / pré-recuperação) será maior ou igual ao seu conceito nominal: $$C_F = \max\{C_N,C_M\}.$$

Recuperação

Caso seu conceito $C_F$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova online de recuperação $P_R$. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Não haverá normalização na recuperação. Seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.

Bibliografia

Em tempos de pandemia, vamos utilizar somente livros cujos pdfs estão gratuitamente disponíveis online. Seguiremos [Vis] de perto, usando [Bub] quando necessário. [BoV] figura como apoio (e apresenta outras aplicações). [Nes] é um clássico, mas não faremos uso dele desta vez (fica como referência adicional). Todos os quatro são excelentes trabalhos!

• [Vis] N.K. Vishnoi, Algorithms for Convex Optimization (2020)
• [Bub] S. Bubeck, Convex Optimization: Algorithms and Complexity (2015)
• [BoV] S. Boyd, L. Vandenberghe, Convex Optimization (2004)
• [Nes] Y. Nesterov, Introductory Lectures On Convex Programming (1998)

Abaixo, dois ótimos especializados em análise convexa para conhecimento. Não serão necessários desta vez (e são gratuitos).

• [Bar] A. Barvinok, A Course in Convex Analysis, GSM v.54, American Mathematical Society (2002)
• [Roc] R.T. Rockafellar, Convex Analysis, Princeton University Press (1970)

Lista de tópicos por semana (tentativa)

• S01 – Introdução. Convexidade. Otimização Convexa.
  ([Vis] 1, 3; [Bub] 1)
• S02 – Modelos Computacionais, Eficiência. Gradiente Conjugado
  ([Vis] 2; [Bub] 2.4)
• S03 – Dualidade e Otimalidade
  ([Vis] 5)
• S04 – Gradient Descent
  ([Vis] 6; [Bub] 3.1 - 3.2)
• S05 – Mirror Descent, Multiplicative Weights Update
  ([Vis] 7; [Bub] 4)
• S06 – Accelerated Gradient Descent
  ([Vis] 8; [Bub] 3.6 - 3.7)
• S07 – Método de Newton
  ([Vis] 9)
• S08 – Método de Pontos Interiores para Programação Linear
  ([Vis] 10; [Bub] 5)
• S09 – Método de Pontos Interiores para Otimização Convexa
  ([Vis] 11; [Bub] 5)
• S10 – Método dos Elipsóides para Programação Linear
  ([Vis] 12; [Bub] 2.2 - 2.3)
• S11 – Método dos Elipsóides para Otimização Convexa
  ([Vis] 13; [Bub] 2.2 - 2.3)
• S12 – Otimização Convexa e Aleatoridade (*)
  ([Bub] 6)

Estudando para esta disciplina

Pela natureza do tópico (métodos de otimização) e pelo posicionamento na grade (Q10-Q12), este é um curso avançado de graduação e será tratado como tal. Espera-se que você, após a primeira semana, leia o conteúdo programado para as demais aulas antes de ocorrerem e se dedique à listas e projeto.

De qualquer forma, é normal fazer confusões e sentir-se perdido no início. O motivo é, em geral, a falta de familiaridade com formalismo matemático e raciocínio algorítmico.

• Refaça os exemplos fornecidos nas aulas e re-prove os principais resultados.
• Preste atenção ao processo de solução e não foque somente no resultado final.
• Assista às aulas (vídeos) e resolva os exercícios propostos durante as mesmas e os contidos nas listas.
• Estude a bibliografia indicada (monte grupos de estudo online) e faça um bom uso dos horários de atendimento.
• Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo.
• Se ainda estiver se sentindo perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Integridade acadêmica e transgressões

O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:

• I - fraudem avaliações;
• II - fabriquem ou falsifiquem dados;
• III - plageiem ou não creditem devidamente autoria;
• IV - aceitem autoria de material acadêmico sem participação na produção;
• V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”

Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.