MCCC013-23 -- Otimização Linear -- Q2024.3

Expediente

• Professor: Aritanan Gruber , sala S-539.2
• Aulas: Seg. 10–12h e Qui. 08–10h na S-214.0
• Atendimento: Ter. 10–12h (na S-539.2)
• Monitoria: Guilherme Afonso Gigeck, Zzz. XX–YYh na sala de monitoria (5o andar, torre 2)
• Moodle: OL (Q24.3-DA1)
  andamento do curso, links úteis, material, avaliações, notas, mensagens, etc.

Ementa

Problemas de otimização linear: viabilidade e otimalidade, formulações e equivalências. Sistemas de inequações lineares e lemas de alternativas. Dualidade linear e condições de otimalidade. Geometria, estrutura e representação de poliedros. Matrizes totalmente unimodulares e poliedros inteiros. Método Simplex: fases, ciclagem e regras de pivotação, desempenho, variante dual. Elementos do método dos elipsoides: complexidade e significância teórica. Métodos de pontos interiores: redução de potencial e caminho central. Otimização paramétrica e análise de sensibilidade.

Objetivos

Entender e usar algumas das técnicas para construção de modelos de otimização linear e realizar argumentações precisas sobre a correção deles. Adquirir intuição geométrico-algébrica aprendendo a demonstrar resultados elementares de poliedros, lemas de alternativas, dualidade e condições de otimalidade. Ser capaz de argumentar sobre correção e complexidade computacional dos métodos algorítmicos vistos, identificando semelhanças e diferenças cruciais entre os mesmos.

Recomendação

Álgebra Linear, Funções de Várias Variáveis, Processamento da Informação, Matemática Discreta.

Avaliações e critérios

• duas listas de exercícios $L_1$ e $L_2$; datas de entrega a serem definidas ao longo do quadrimestre;
  
• projeto final $H\in[0,10]$; data de entrega a ser definida ao longo do quadrimestre;
  
• duas provas regulares $P_1$ e $P_2$ e uma prova substitutiva $P_3$ aberta;
  
  • P1 : Seg. 11/11 @ 10h
  • P2 : Seg. 16/12 @ 10h
  • P3 : Qui. 19/12 @ 08h

Nota nominal ($N$): com $$ P = \frac{1}{2}\max\left\{\sum_{j\in S}P_j\,:\,S\in\binom{[3]}{2}\right\} = \frac{1}{2}\max\left\{P_1+P_2,P_1+P_3,P_2+P_3\right\}, \quad P_j\in[0,10] $$ e $$ L = \frac{1}{2}\big(L_1 + L_2\big), \quad L_j\in[0,10] $$ tem-se que $$ N = \frac{3}{5}P + \frac{1}{5}L + \frac{1}{5}H. $$

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.$$

Recuperação

Caso seu conceito $C_N$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova 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$. Note que 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

Usaremos diretamente Bertsimas-Tsitsiklis [A], Gärtner-Matousek [C], e Vanderbei [1]. Os três são muito didáticos e se “complementam.”

Para material mais avançado em teoria e algoritmos, consulte Nemhauser-Wolsey [D] e, principalmente, Schrijver [E]. Para modelagem, recomendamos Chen-Batson-Dand [B], Fourer-Gay-Kerninghan [I] e Williams [J]. Conceitos de álgebra linear são cobertos em nível introdutório em Axler [K] e Strang [N] e, em forma mais avançada, em Hoffman-Kunze [O]. A referência clássica para análise convexa é Rockafellar [M]; Bertsekas-Nedic-Ozdaglar [L] é uma boa alternativa – ambos contêm muito mais material do que vamos precisar. Para otimização além de linear, consulte Bertsekas [F], Boyd-Vendenberghe [G] e Ruszczynski [H].

Otimização Linear e Linear Inteira

• [A] D. Bertsimas e J. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific (1997)
• [B] D. Chen, R. Batson e Y. Dand, Applied Integer Programming: Modeling and Solution, Wiley (2010)
• [C] B. Gärtner e J. Matousek, Understanding and Using Linear Programming, Springer (2007)
• [D] G. Nemhauser e L. Wolsey, Integer and Combinatorial Optimization, Willey (1988)
• [E] A. Schrijver, Theory of Linear and Integer Programming, Wiley (1986)
• [1] R. Vanderbei, Linear Programming - Foundations and Extensions, 5th ed., Springer (2020)

Otimização Convexa e Não-Linear

• [F] D. Bertsekas, Nonlinear Programming, 3rd ed., Athena Scientific (2016)
• [G] S. Boyd e L. Vendenberghe, Convex Optimization, Cambridge University Press (2004)
• [H] A. Ruszczynski, Nonlinear Optimization, Princeton University Press (2006)
• [P] N.K. Vishnoi, Algorithms for Convex Optimization (2020)

Modelagem e Ferramentas

• [I] R. Fourer, D. Gay e B. Kerninghan, AMPL: A Modeling Language for Mathematical Programming, 2nd ed., Thompson (2003)
• [J] H. Williams, Model Building in Mathematical Programming, 5th ed., Willey (2013)

Álgebra Linear e Análise Convexa

• [K] S. Axler, Linear Algebra Done Right, 3rd ed., Springer (2015)
• [L] D. Bertsekas, A. Nedic e E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific (2003)
• [M] T. Rockafellar, Convex Analysis, Princeton University Press (1970)
• [N] G. Strang, Introduction to Linear Algebra, 5th ed., Wellesley Publishers (2016)
• [O] K. Hoffman e R. Kunze, Linear Algebra, 2nd ed., Prentice Hall (1971)

Lista de tópicos por semana (tentativa)

Detalhes de cada tópico (coberto nas aulas) serão atualizados no Moodle ao longo do quadrimestre.

• S01 – Introdução à Otimização e Dualidade Lineares
  (BT[A] 1.1 – 1.4, 1.6, 1.8, 4.1, 4.2; GM[C] 1.1 – 1.4, 2.1 – 2.5, 3.1, 4.1, 6.1, 6.2)
• S02 – Elementos de Álgebra Linear e Convexidade
  (BT[A] 1.5, 2.1; GM[C] Apêndice, 4.3; A[N] 1.B, 1.C, 2.A – 2.C, 3.A – 3.C, 6.A – 6.C)
• S03 – Geometria e Estrutura de Poliedros I
  (BT[A] 2.2 – 2.8, 4.2 – 4.4, 4.6, 4.7; GM[C] 4.1 – 4.4, 6.1, 6.2, 6.4, 6.7)
• S04 – Geometria e Estrutura de Poliedros II
  (BT[A] 2.2 – 2.8, 4.2 – 4.4, 4.6, 4.7; GM[C] 4.1 – 4.4, 6.1, 6.2, 6.4, 6.7)
• S05 – Geometria e Estrutura de Poliedros III
  (BT[A] 2.2 – 2.8, 4.2 – 4.4, 4.6, 4.7; GM[C] 4.1 – 4.4, 6.1, 6.2, 6.4, 6.7)
• S06 – Método(s) Simplex I
  (BT[A] 3.1 – 3.5, 3.7, 4.5; GM[C] 5.1 – 5.10)
• S07 – Método(s) Simplex II
  (BT[A] 3.1 – 3.5, 3.7, 4.5; GM[C] 5.1 – 5.10)
• S08 – Análises Paramétrica e de Sensibilidade
  (BT[A] 5.1 – 5.4, 6.1, 6.2, 12.1)
• S09 – Método(s) de Pontos Interiores
  (BT[A] 9.1 – 9.6)
• S10 – Método de Elipsoides
  (BT[A] 8.1 – 8.5)
• S11 – Matrizes Totalmente Unimodulares e Poliedros Inteiros
  (BT[A] 10.1 – 10.3, 11.1, 11.2; GM[C] 3.1 – 3.4)
• S12 – Exame final e substitutiva

Estudando para esta disciplina

A natureza do tópico, o posicionamento do curso na grade, e a lista de pré-requisitos indicam que esta é uma disciplina de nível intermediário; e será tratada como tal. Você deve assistir às aulas, estudar a bibliografia indicada, e dedicar-se às listas de exercícios.

Caso seus pré-requisitos não estejam tão sólidos quanto desejável (falta de familiaridade com formalismo matemático e raciocínio algorítmico, atitude passiva com relação ao aprendizado, tempo dedicado insuficiente, etc.), será possível fazer confusões e sentir-se perdido no início.

Alguns procedimentos que costumam funcionar em cursos introdutórios para mitigar os motivos relacionados também costumam funcionar por aqui:

• Refaça os exemplos e re-prove os resultados fornecidos em sala de aula.
• Preste atenção aos processos de solução (aprenda-os!) e não foque somente nos resultados finais.
• Assista ativamente às aulas; resolva os exercícios nelas propostos e os contidos nas listas.
• Estude a bibliografia indicada, monte grupos de estudo, 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. “Ouvir” às aulas e “ler” os livros tem pouco ou nenhum efeito neste curso – e em qualquer disciplina matemática/algorítmica que o valha.
• Se ainda assim, sentir-se perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Note que você não será convidado a regurgitar respostas fornecidas em aula ou presente nos livros. As questões em listas e provas testarão sua capacidade de entender os problemas e apresentar uma solução para eles; às vezes, serão uma adaptação simples ou uma extensão direta do que foi visto, outras, será necessário relacionar dois ou mais métodos ou conceitos apresentados, e outras ainda, irão requerer análise e raciocínio mais profundo (o que leva tempo, então não deixe nada para a última hora!).

Tenha em mente: além do escrito acima, para aproveitar bem este curso, você deve ler os slides e familiarizar-se com o material na leitura sugerida correspondentes antes da aula, e estudá-los com afinco depois.

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.

LLMs, GPTs e similares

Representam um grande avanço da inteligência artificial generativa sendo assim, por este ponto de vista, resultados magníficos. De qualquer forma, soluções transcritas e/ou entregues que tenham sido produzidas por eles enquadram-se no Artigo 25 acima.

Para pensar ao longo do curso: Do que adianta as máquinas aprenderem e os alunos não?