/div>
Optimização, um dos problemas elementares da física matemática, economia, engenharia, e muitas outras áreas da matemática aplicada, é o problema de encontrar o valor máximo ou mínimo de uma função, chamada função objectiva, bem como os valores das variáveis de entrada onde esse valor óptimo ocorre. No cálculo elementar de uma única variável, este é um problema muito simples que equivale a encontrar os valores de x para os quais df/dx é zero.
Problemas de optimização multivariável são mais complicados porque podemos impor restrições. Consideramos restrições que podem ser expressas na forma g(x,y,z)=c para alguma função g e constante c. Estas são chamadas restrições de igualdade, e o conjunto de pontos que satisfazem estas restrições é chamado o conjunto viável, que denotamos por S. Por exemplo, se nos for pedido que encontremos o valor máximo de f(x,y) no círculo unitário, então g(x,y)=x²+y² uma vez que o círculo unitário é definido por x²+y²=1,
A técnica padrão para resolver este tipo de problema é o método dos multiplicadores de Lagrange. Neste artigo, vou derivar o método e dar algumas demonstrações da sua utilização.
Motivação e derivação
A função f tem um extremo local (máximo ou mínimo) num ponto P quando a derivada parcial de f é zero para cada uma das variáveis independentes e quando o ponto não é um ponto de sela (uma situação com a qual não precisaremos de gastar tempo a lidar aqui). Podemos escrever isto de forma compacta como ∇f=0, onde ∇ denota o operador do gradiente:
Em optimização restrita, contudo, só porque f tem um máximo ou mínimo local num ponto do conjunto viável, não se segue que f toma o seu valor óptimo no conjunto viável nesse ponto.
Como exemplo, vamos considerar o seguinte problema de optimização:
Ao escrever o gradiente, podemos ver que f tem um mínimo local quando x=0 e y=1:
p>Outras mais, f(0,1)=0, mas f(0,-1)=-4 por isso embora (0,1) seja um mínimo local de f(x,y), não é o mínimo de f(x,y) no círculo da unidade.
Como outro exemplo, vamos maximizar f(x,y)=y no círculo unitário. O gradiente de f(x,y)=y é um vector constante pelo que f(x,y) não tem máximos ou mínimos locais, mas no círculo unitário f tem um valor máximo de 1, ocorrendo em (0,1).
A razão desta falha é que o gradiente mede a taxa de variação de f(x,y,z) em relação à posição no espaço tridimensional, mas queremos medir a taxa de variação de f(x,y,z) em relação à posição no conjunto viável. Para um problema tridimensional, S será ou uma curva ou uma superfície, e em geral para problemas com n variáveis, S será uma hipersuperfície de dimensão estritamente inferior a n.
A abordagem mais natural é considerar curvas em S. Que P seja um ponto em S para o qual f(P) toma um valor localmente óptimo em S mas ∇f(P) não é necessariamente zero, e que r(t) seja a parametrização de qualquer curva em S que passe por P, isto é:
se S é uma curva, então r(t) é apenas uma parametrização de S. Além disso, let r(T)=P, r′(T)≠0, e let h(t) = f(r(t)) para que h′(T)=0. Vamos expandir h′(t) usando a regra da corrente:
>/div>
Desde que r(t) está sempre em S, o vector de velocidade r′(t) deve ser sempre tangente à superfície ou curva de S, pois se r′(t) tivesse um componente perpendicular à superfície, ou seja, dirigido para fora da superfície, então haveria pontos onde r(t) sai de S. Como isto é verdade para qualquer curva r(t) que passe por P, segue-se que ∇f(P) é perpendicular a qualquer vector tangente à superfície em P. Assim, se P é um ponto onde f toma um valor máximo ou mínimo em relação à posição em S, então ∇f(P) é perpendicular a S.
O inverso também é verdadeiro: Uma vez que r′(T) nunca é zero e sempre paralelo a S, então se ∇f(P) é perpendicular a S, então h′(T)=∇f(P)∙r′(T)=0.
Mas como é que de facto encontramos pontos onde ∇f é perpendicular a S? Aqui está a resposta: O conjunto S é o conjunto de todos os pontos onde g(x,y,z)=c, ou seja, S é um conjunto de níveis de g. Isto significa que ∇g é perpendicular a S para todos os pontos em S, portanto ∇f e ∇g são paralelos em pontos em S onde f toma valores óptimos. Isto significa que f toma os seus valores óptimos em S precisamente quando ∇f=λ∇g para alguma constante λ. A constante λ é chamada o multiplicador indeterminado de Lagrange, e é aqui que o método recebe o seu nome. O problema da optimização de f pode agora ser resolvido encontrando quatro incógnitas x, y, z, e λ que resolvem estas quatro equações:
p>>P>P>Posto de outra forma, o nosso objectivo agora é optimizar a função f-λg com respeito a x, y, e z sem restrições, encontrando onde ∇(f-λg)=0.
E se houver mais do que uma restrição? Suponha agora que temos de optimizar f(x,y,x) sujeito a g(x,y,z)=c e h(x,y,z)=d. Eis o que fazemos. Para optimizar f sujeito a g(x,y,z)=c, optimizamos f-λg sem restrição, de modo que a primeira restrição é cuidada substituindo f por f-λg, e resta-nos optimizar f-λg sujeito à restrição h(x,y,z)=d. Este é um problema com apenas uma restrição, pelo que basta adicionar outro multiplicador de Lagrange μ, e o problema agora é optimizar f-λg-μh sem restrição.
Vejamos agora alguns exemplos.
A área máxima de um rectângulo
Para um dado perímetro, qual é a maior área possível de um rectângulo com esse perímetro? Podemos formular isto como um problema multiplicador de Lagrange. Se a largura e altura forem x e y, então desejamos maximizar f(x,y)=xy para g(x,y)=2x+2y=c. O sistema de equações resultante é:
As duas primeiras equações dizem-nos imediatamente que x=y, por isso a área máxima ocorre quando o rectângulo é um quadrado. Ao ligar isto à terceira equação, vemos que x=y=c/4, pelo que a área máxima de um rectângulo com perímetro c é c²/16.
A (modificado) problema Putnam
O concurso matemático Putnam é um concurso em formato de exame oferecido todos os meses de Dezembro a estudantes universitários. Os estudantes têm seis horas para resolver 12 problemas extremamente desafiantes. O exame é tão difícil que, de uma possível nota de 120, a média de notas na maioria dos anos é de 0 ou 1. Hoje vamos analisar uma versão modificada (para simplificar e evitar questões de direitos de autor) do problema A3 do exame de 2018:
Há dois problemas. O primeiro é que a função objectiva tem uma característica muito indesejável: é uma soma de co-seno, e somas de funções trigonométricas podem ser difíceis de lidar. O segundo é que não há maneira de fazer a função de restrição aparecer clara e explicitamente na função objectiva, embora à primeira vista possa parecer que isto deveria ser possível. Os problemas de Putnam envolvem frequentemente “armadilhas” como esta, onde se pode ser atraído para perder tempo numa abordagem que não levará a uma solução se não se parar para pensar no que se está a fazer. É uma armadilha que seria especialmente perigosa para um concorrente com experiência em concursos de matemática do ensino secundário, onde as identidades trigonométricas tendem a ser uma forte ênfase.
Mas quando vemos um problema que diz “maximizar f sujeito a g=0”, devemos pensar imediatamente nos multiplicadores de Lagrange. Vamos estabelecer o nosso sistema de equações:
Agora podemos usar as nossas identidades de trigonometria para fazer a restrição aparecer explicitamente. Reescrever o sistema de equações usando a fórmula de duplo ângulo:
p> O resultado é:
Agora cancele a função seno de cada lado, e acrescentar as equações:
p>>e isto significa que λ=0, portanto, de acordo com as equações multiplicadoras de Lagrange, isto significa que:
Por isso w, x, y, e z são todos multiplicações inteiras de π/2. Para mesmo os multiplicadores inteiros de π/2, digamos m=2k para alguns k. inteiros:
Mas se m é um número inteiro ímpar, então cos(mπ/2)=0. Isto significa que temos três opções de como podemos satisfazer a equação de constrangimento. Em primeiro lugar, podemos definir w, x, y, e z, tudo a multiplicações inteiras estranhas de π/2, digamos k, l, m, e n, então:
A primeira linha está a mostrar que a equação de restrição está satisfeita, e a segunda linha é o resultado de ligar esses valores à função objectiva, o que nos dá -4.
A segunda opção é que podemos definir duas das variáveis para múltiplos inteiros ímpares de π/2, digamos k e l, e as outras duas para inteiros pares, digamos 2m e 2n onde m é par e n é ímpar. O resultado de ligar isto à equação de restrição é:
Assim, a equação de restrição é satisfeita. Aqui está o resultado de os ligar à função objectiva:
A opção final é que podemos definir todas as variáveis até mesmo para multiplicações inteiras de π/2, digamos 2k, 2l, 2m, e 2n, onde k e l são pares e m e n são ímpares. O resultado de ligar isto à equação de restrição é:
Assim, o constrangimento é satisfeito. Agora ligamo-los à função objectiva a obter:
Então a resposta é 4, que coincidentemente se revela ser o valor máximo global da função objectiva.
Verifica este outro artigo que escrevi para uma discussão de outro problema Putnam.
Theorem de Thomson
Agora, em vez de optimizar uma função, vamos usar o método dos multiplicadores de Lagrange para optimizar uma função: um objecto que pega numa função e devolve um número. Os integrais definitivos são um exemplo chave. Esta demonstração final mostrará como o método dos multiplicadores de Lagrange pode ser utilizado para encontrar a função que minimiza o valor de um integral definido.
Como demonstração, consideramos um facto fundamental da electrostática, o estudo de sistemas sujeitos a forças eléctricas em equilíbrio mecânico para que nenhuma das cargas esteja em movimento. Mostraremos que quando um condutor, um corpo em que a carga eléctrica pode mover-se livremente, está em equilíbrio com qualquer sistema de forças eléctricas, então não há campo eléctrico no interior do corpo do condutor. Este é o Teorema de Thomson. Este teorema é normalmente declarado em termos do facto físico fundamental de que a energia de um sistema em equilíbrio mecânico estável é mínima:
p>Theorem de Thomson: A energia electrostática de um corpo condutor de tamanho e forma fixos é minimizada quando as cargas são distribuídas de modo a tornar o potencial ϕ constante no corpo de modo a que E=-∇ϕ=0.
Leve ρ(r) ser a função de distribuição de carga e ϕₑₓₜ o potencial devido a quaisquer fontes externas ao corpo condutor. A energia electrostática total pode ser expressa como um U funcional de ρ(r):
Estes são integrais de volume sobre o corpo do condutor. A primeira integral é uma integral dupla realizada primeiro sobre as coordenadas primas e depois sobre as não primas. Queremos minimizar U como uma função de ρ(r) dado que a carga total é independente da distribuição da carga:
f>Felizmente, o método dos multiplicadores de Lagrange funciona para os funcionais com restrições. Introduzir um multiplicador de Lagrange indeterminado, e depois, em vez de optimização restrita em U, realizar uma optimização sem constrangimentos nas seguintes funções:
por analogia com derivados de funções, o objectivo aqui é encontrar a distribuição de carga ρ de tal forma que quando ρ é variado por uma pequena variação δρ, a mudança em I, δI, é zero:
/div>>
This não é bem um derivado porque δρ é uma função e não um número, por isso não faz sentido falar do limite, uma vez que δρ vai a zero, mas a intuição básica é a mesma.
Comecemos por expandir a U:
p>Esta pode parecer mal, mas podemos simplificar muito isto. Primeiro, visto que δρ é muito pequeno, (δρ)² é tão pequeno que podemos ignorá-lo, por isso assumamos que δρ(r)δρ(r′)=0. Em seguida, ao alterarmos a ordem de integração, vemos isso:
Também podemos ver que o U aparece na expansão. Isto dá-nos o suficiente para simplificar o U:
Agora podemos expandir δI:
Agora podemos considerar o integral sobre δρ(r):
Para que isto seja verdade para qualquer escolha da variação δρ(r), o termo entre parênteses deve ser zero, portanto:
Mas isto integral é apenas o potencial em r devido às cargas no interior do condutor pelo que o lado esquerdo desta equação dá o potencial total em cada ponto r no interior do condutor, portanto ρ(r) é a distribuição que torna constante o potencial total dentro do condutor. Isto completa a prova.
Isto também seria válido se a energia electrostática do condutor fosse maximizada, caso em que o condutor está em equilíbrio instável. Na prática nunca se encontram condutores em equilíbrio instável porque o movimento térmico aleatório dos electrões no condutor irá rapidamente, na ordem de 10-¹⁴ segundos para condutores metálicos, conduzir o sistema para fora do equilíbrio instável e para um equilíbrio estável.