Exercício 11: Regressão linear é um caso particular de problema de quadrados mınimos, no qual deseja-se calcular a função f(x)=m x+b que melhor se ajusta a um conjunto de m pontos: ( x_{i}, y_{i} ). Usualmente, este problema é resolvido de forma a minimizar o erro quadrático: \sum_{i=1}^{m}\left(f\left(x_{i}\right)-y_{i}\right)^{2}. Transforme o problema em um PL e resolva: i) minimizando o maior residual (erro de predição), ii) minimizando a soma dos residuais. Discuta as diferenças entre as duas modelagens.
Resolva o problema de ajuste para o seguinte conjunto de pontos:
x_{i}
0.422924
0.85996
0.979937
1.37834
2.10748
2.16787
2.31275
2.87202
2.95637
3.04747
f\left(x_{i}\right)
-2.715
-1.51359
-1.06674
0.196853
2.32341
2.48318
2.95162
4.62148
4.7908
5.2032
Passo 1
Vou separar muito claramente o que o enunciado pede e quais dados temos:
O enunciado pede: transformar o problema de ajuste linear por mínimos quadrados em dois modelos de programação linear (PL) e resolver numericamente para o conjunto de pontos dado:
(i) minimizar o maior residual (norma infinito dos resíduos, também chamado ajuste Chebyshev);
(ii) minimizar a soma dos residuais (interpreto isto como minimizar a soma dos valores absolutos dos resíduos, isto é norma L_1, porque a soma dos resíduos assinados pode ser anulada artificialmente).
Os pontos fornecidos (peguei os valores do enunciado) são, para i=1,\dots,10:
O que será calculado: para cada modelagem (i) e (ii) devemos fornecer os valores de m e b da reta f(x)=m x + b. Para (i) também é útil reportar o valor mínimo do maior residual R. Para (ii) é útil reportar a soma dos resíduos absolutos no ponto ótimo.
A partir daqui começo a transformar e resolver os modelos.
Passo 2
Primeiro uma explicação didática sobre como transformar problemas com valor absoluto em programação linear.
Quando aparece um residual r_i = f(x_i)-y_i = m x_i + b - y_i e queremos trabalhar com |r_i| (valor absoluto), a técnica padrão em PL é introduzir uma variável auxiliar não negativa u_i\ge 0 e forçar
u_i \ge r_i,\qquad u_i \ge -r_i,
ou seja
u_i \ge m x_i + b - y_i,\qquad u_i \ge -\big(m x_i + b - y_i\big).
Com isso, em qualquer solução viável u_i = |r_i| no ótimo se o objetivo minimizar soma ou máximo de |r_i|. É a forma linear de “representar” |\cdot|.
Para minimizar o maior residual (norma infinito) é suficiente introduzir uma variável R\ge 0 e forçar para todo i:
-R \le m x_i + b - y_i \le R,
ou, em forma de restrições lineares equivalentes,
m x_i + b - y_i \le R,\qquad - (m x_i + b - y_i) \le R.
O objetivo é minimizar R. Esse é um PL (variáveis m,b,R).
Para minimizar a soma dos valores absolutos (norma L_1) introduzimos u_i\ge 0 com as duas desigualdades acima e minimizamos \sum_i u_i. Esse também é um PL (variáveis m,b,u_1,\dots,u_{10}).
Esses dois modelos são o que o enunciado pede que se transforme em PL; agora escrevo explicitamente.
Passo 3
Modelos PL escritos explicitamente (forma pronta para enviar a um resolvedor LP):
Modelo (i) minimizar o maior residual (Chebyshev):
Modelo (ii) minimizar a soma dos residuais absolutos (norma L_1):
Variáveis: m\in\mathbb{R},\; b\in\mathbb{R},\; u_i\ge 0 para i=1,\dots,10.
Restrições (para todo i):
u_i \ge m x_i + b - y_i,
u_i \ge -(m x_i + b - y_i).
Objetivo:
\text{minimizar } \sum_{i=1}^{10} u_i .
Observação didática: esses dois PLs são padrões. No (i) minimizamos a maior violação (útil quando se quer controlar o pior erro). No (ii) minimizamos erro total absoluto (mais robusto a outliers do que mínimos quadrados, mas menos sensível a pequenas variações do que quadrados).
Passo 4
Estratégia prática para resolver numericamente (sem depender de um pacote, passo a passo numérico e ideas para a prova):
Uma maneira rápida de obter uma boa inicial é calcular a reta dos mínimos quadrados ordinários (OLS). OLS não é objetivo pedido, mas costuma ficar perto das soluções L1 e L∞ quando os pontos estão quase lineares. Vou calcular OLS como referência — isso também é um bom truque na prova: use OLS como chute inicial para um PL e depois ajuste com as técnicas de PL (igualdade de extremos, mediana, etc.).
Isso nos dá uma reta inicial \hat f_{\text{OLS}}(x)=3,004\,x - 4,0095.
Explicação rápida (didática): OLS minimiza \sum (m x_i + b - y_i)^2. A fórmula acima resulta de igualar derivadas parciais a zero (sistema normal) e resolver para m,b. É o método padrão; mas lembre-se: OLS penaliza fortemente grandes resíduos ao quadrado e não é o que nos pediram — apenas um passo útil.
Passo 5
Cálculo dos resíduos com a reta OLS e análise para guiar a solução dos PLs.
Defino o residual (predição menos verdadeiro): r_i = m x_i + b - y_i.
Usando (m_{\text{OLS}},b_{\text{OLS}})=(3,004,\,-4,0095) calculei os resíduos (valores arredondados):
A maior residual absoluto com OLS é cerca de 0,0886 (no ponto i=2).
No problema de minimax (L∞) a solução ótima normalmente “equaliza” os resíduos extremos: o melhor R é tal que existem pelo menos três pontos com resíduos atingindo \pm R (regra prática de equioscillação para retas), mas aqui, devido à quase-linearidade e aos pequenos resíduos, uma boa aproximação é ajustar somente a interceta para igualar o máximo positivo ao máximo negativo (manobra simples que frequentemente já produz o ótimo ou fica muito próximo).
Vou usar essa ideia prática como atalho numérico (explico o raciocínio em seguida) e depois justifico por que é válido para a prova.
Passo 6
Resolução aproximada do modelo (i) — minimizar o maior residual (L∞), via ajuste da intercepta a partir de OLS.
Intuição e técnica rápida (útil em prova): começar com a reta OLS e ver o maior resíduo positivo e o maior resíduo negativo em magnitude. Se o maior resíduo positivo for maior que o maior resíduo negativo, podemos descer a reta (diminuir b) de forma a reduzir o maior positivo até igualá-lo ao maior negativo em magnitude. Isso tende a diminuir R até o ponto em que um dos outros resíduos possa passar a ser o máximo — então é necessário verificar todos.
Com os resíduos calculados no Passo 5:
maior positivo (máximo de r_i) é r_{2}\approx 0,0886;
maior negativo em magnitude é |r_4|\approx 0,0674.
Se reduzirmos b em \delta>0 (isto é, tornamos b mais negativo em \delta), todos os resíduos r_i diminuem em \delta. Queremos \max_i |r_i| mínimo; uma primeira aproximação é resolver para \delta tal que o maior positivo remanescente iguale em magnitude o maior negativo remanescente:
Logo uma reta candidata é \displaystyle m\approx 3,004,\quad b\approx b_{\text{OLS}}-\delta \approx -4,0095 - 0,010625 = -4,020125.
Verificação dos resíduos com essa reta (subtrai-se \delta dos resíduos do OLS): os resíduos passam a ter máximos em magnitude aproximadamente R\approx 0,07798. Verifiquei todos os 10 resíduos e o maior valor absoluto ficou \approx 0,07798. Assim esta reta é uma solução muito boa (próxima do ótimo). Para este conjunto de pontos tão “quase-lineares” a diferença entre essa aproximação e o ótimo exato do PL é desprezível para uso em prova (se for necessário o exato, usar um solver LP garante precisão).
Portanto, para (i) temos, com boa precisão numérica:
Nota didática: em provas, essa técnica de “equalizar extremos” é válida porque a solução ótima do problema Chebyshev para ajuste linear atinge o valor mínimo R em pelo menos três pontos (equioscillação). Quando os pontos estão bem comportados, ajustar só b a partir de OLS já produz a equalização de dois extremos; geralmente só é preciso checar se outro ponto ultrapassa esse valor. Se sim, seria preciso ajustar também m e resolver o sistema linear formado por três equalidades (três equações lineares em m,b,R) — procedimento que também é direto de fazer manualmente.
Passo 7
Resolução aproximada do modelo (ii) — minimizar a soma dos resíduos absolutos (norma L_1) usando mediana condicional e otimização unidimensional.
Explicação teórica curta e prática:
Se fixarmos m, o valor ótimo de b que minimiza \sum_i |m x_i + b - y_i| é a mediana dos valores t_i = y_i - m x_i. Isso é fácil de demonstrar: para função g(b)=\sum |(m x_i - y_i)+b| a derivada lateral muda de sinal na mediana dos (y_i - m x_i). Então, para cada m podemos obter o b ótimo em O(n) encontrando essa mediana.
Assim o problema L1 reduz-se a um problema unidimensional em m: minimizar G(m)=\sum_i |m x_i + b(m) - y_i|, onde b(m)=\operatorname{median}(y_i - m x_i). A função G(m) é convexo e piecewise-linear; o ótimo pode ser encontrado checando os pontos onde a ordenação dos y_i - m x_i muda (ou simplesmente usando um solver unidimensional). Na prova, uma aproximação numérica cuidadosa já costuma bastar.
Aplicando essa ideia com m próximo de m_{\text{OLS}}=3,004:
Calculei t_i = y_i - m_{\text{OLS}} x_i e obtive os 10 valores (listados no Passo 5). A mediana (média entre 5.º e 6.º valores quando ordenados) foi
b_{\text{mediana para } m_{\text{OLS}}} \approx -4,004305.
Ou seja, para m=3,004 o b que minimiza a soma dos absolutos é b\approx -4,004305.
Com essa escolha, calculei os resíduos r_i = m x_i + b - y_i e a soma dos absolutos:
\sum_{i=1}^{10} |r_i| \approx 0,360655.
Observação prática: note que esta soma é ligeiramente menor que a soma dos absolutos na reta OLS (que era cerca de 0,36645). Para encontrar o m que minimiza a soma total absoluta precisa-se variar m e recalcular a mediana de y_i - m x_i; mas, por inspeção local, o valor m que minimiza G(m) está muito próximo de 3,004 para estes dados. Fazer uma busca unidimensional fina (por exemplo, varrer m em torno de 3,004 e recalcular b(m)) dá um m que difere apenas em poucos milésimos. Para nossos propósitos de prova e treinamento numérico, a precisão 3 casas decimais é suficiente.
Interpretação e comparação entre as duas modelagens (didática e intuitiva):
Minimizar o maior residual (L∞, Chebyshev):
Objetivo: controlar o pior erro (minimizar a máxima previsão errada).
Comportamento: tende a “distribuir” os erros de modo que nenhum ponto fique com erro muito grande; é ótimo quando se quer garantia sobre o pior caso.
Resultado prático aqui: R_{\min}\approx 0,07798. A reta Chebyshev fica um pouco deslocada em relação a OLS para equalizar extremos e reduzir o máximo absoluto do residual.
Minimizar a soma dos absolutos (L1):
Objetivo: minimizar o erro total absoluto. É mais robusto a outliers do que OLS (porque não eleva ao quadrado) e tende a colocar a metade dos resíduos positivos e a outra metade negativos (quando possível).
Comportamento: concentra-se em reduzir o erro total mais do que o pior erro isolado; alguns resíduos podem ser um pouco grandes se isso reduzir o total.
Resultado prático aqui: soma total de absolutos menor (aprox. 0,360655) e reta apenas ligeiramente diferente da OLS; ela equaliza a mediana dos termos y_i - m x_i.
Comparações práticas e dicas para prova:
L∞ é apropriado quando um grande erro é crítico (ex.: engenharia com limites de tolerância).
L1 é apropriado quando se quer robustez a outliers e um balanço entre erros (e tem interpretação de minimização da soma de distâncias verticais).
L2 (método habitual) penaliza mais outliers grandes; L1 é menos sensível a outliers; L∞ protege contra o pior caso.
Em provas: mostre as transformações propostas (introdução de u_i ou R), argumente sobre por que as desigualdades representam |\cdot| e descreva a técnica de solução (equalizar extremos para L∞ ou usar mediana condicional para L1). Se pedirem número exato, resolva o PL com um solver; se pedirem cálculo manual, use a técnica de igualar/resolver 3 equações (três igualdades ativas) no caso L∞ ou a mediana condicional no caso L1.
Resposta
(i) Minimizar o maior residual (L∞): m \approx 3,004,\; b \approx -4,020125,\; R_{\min}\approx 0,07798
(ii) Minimizar a soma dos resíduos absolutos (L1): m \approx 3,004,\; b \approx -4,004305,\; \sum_{i=1}^{10}|r_i|\approx 0,360655