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:
\begin{array}{c|rrrrrrrrrr} x_i & 0,422924 & 0,85996 & 0,979937 & 1,37834 & 2,10748 & 2,16787 & 2,31275 & 2,87202 & 2,95637 & 3,04747\\hline y_i & -2,715 & -1,51359 & -1,06674 & 0,196853 & 2,32341 & 2,48318 & 2,95162 & 4,62148 & 4,7908 & 5,2032 \end{array}
  • 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):
Variáveis: m\in\mathbb{R},\; b\in\mathbb{R},\; R\ge 0.
Restrições (para todo i=1,\dots,10):
m x_i + b - y_i \le R,
-(m x_i + b - y_i) \le R.
Objetivo:
\text{minimizar } R.
  • 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.).
Fórmulas para OLS (método clássico):
m_{\text{OLS}} = \frac{n\sum x_i y_i - (\sum x_i)(\sum y_i)}{n\sum x_i^2 - (\sum x_i)^2},\qquad b_{\text{OLS}}=\overline{y}-m_{\text{OLS}}\overline{x},
onde \overline{x}=\dfrac{1}{n}\sum x_i,\\ \overline{y}=\dfrac{1}{n}\sum y_i e aqui n=10.
  • Eu calculei (passo a passo com somas) os termos necessários a partir dos dados do enunciado e obtive, arredondando com cuidado, os resultados:
\sum_{i=1}^{10} x_i \approx 19,105121,\qquad \sum_{i=1}^{10} y_i \approx 17,275213,
\sum_{i=1}^{10} x_i^2 \approx 44,544013,\qquad \sum_{i=1}^{10} x_i y_i \approx 57,1689.
Substituindo nas fórmulas deu:
m_{\text{OLS}}\approx 3,004\quad\text{e}\quad b_{\text{OLS}}\approx -4,0095.
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):
\begin{array}{c|rrrrrrrrrr} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\hline r_i & -0,0255 & 0,0886 & 0,0020 & -0,0674 & -0,0029 & 0,0247 & -0,0131 & -0,0080 & 0,0817 & -0,0526 \end{array}
  • Observações úteis:
    • 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:
0,0886-\delta = 0,0674+\delta \quad\Rightarrow\quad \delta \approx 0,010625.
  • 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:
m_{\infty} \approx 3,004,\qquad b_{\infty}\approx -4,020125,\qquad R_{\min}\approx 0,07798.
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.
  • Assim uma solução muito boa para (ii) é
m_1 \approx 3,004,\qquad b_1 \approx -4,004305,\qquad \sum_{i=1}^{10}|r_i|\approx 0,360655.

Passo 8

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

Exercícios relacionados