Extremos condicionados e o método dos multiplicadores de Lagrange

Nas aplicações são comuns problemas de optimização de funções em que o extremo da função é procurado num conjunto de pontos especificado por uma condição da forma $G(\boldsymbol{x})=0$ em que $G$ é uma função escalar ou vectorial. Tais problemas designam-se problemas de extremos condicionados. Vamos verificar que, sob condições relativamente gerais, o formalismo que desenvolvemos sobre espaços tangente e normal de uma variedade num dos seus pontos permite-nos justificar com facilidade um método de busca de pontos de extremo de tais problema que é conhecido como método dos multiplicadores de Lagrange.

---

Seja $f:A\subset\mathbb{R}^n\to \mathbb{R}$ uma função diferenciável no aberto $A$ e suponhamos que procuramos os seus pontos de extremo quando restringidos a um conjunto $\{\boldsymbol{x}\in \mathbb{R}^n: G(\boldsymbol{x})=\boldsymbol{0}\}$ sendo $G:A\to\mathbb{R}^d$, $0\lt d \lt n$, uma função $C^1(A)$. Suponhamos que $\boldsymbol{x}_0$ é uma solução deste problema e, numa vizinhança de $\boldsymbol{x}_0$, $G(\boldsymbol{x})=\boldsymbol{0}$ define uma variedade $n-d$ dimensional $M$ e $DG(\boldsymbol{x}_0)$ é sobrejectiva.

Seja também $\alpha(t)$ é uma qualquer parametrização de um caminho diferenciável tal que $\alpha(t_0)=\boldsymbol{x}_0$ e numa vizinhança de $t_0$ temos $G(\alpha(t))=\boldsymbol{0}$. Então a função $t\mapsto f(\alpha(t))$ tem um extremo local em $t_0$ donde este ponto é um seu ponto de estacionaridade e portanto $Df(\alpha(t_0))\alpha'(t_0)=0$ ou, relembrando a definição de espaço tangente e espaço normal, $Df(\boldsymbol{x}_0)$ é ortogonal a $T_M(\boldsymbol{x}_0)$, ou seja, $Df(\boldsymbol{x}_0)\in N_M(\boldsymbol{x}_0)$. Mas, da discussão de como determinar o espaço normal de uma variedade descrita implicitamente, sabemos que $N_M(\boldsymbol{x}_0)$ é gerado pelos vectores $DG_i(\boldsymbol{x}_0)$, com $i=1,\dots, d$. Então deve ser satisfeita a igualdade \[Df(\boldsymbol{x}_0)+\sum_{i=1}^d \lambda_i DG_i(\boldsymbol{x}_0)=0\] para alguns números reais $\lambda_i$. Assim, qualquer solução $\boldsymbol{x}_0$ do nosso problema para a qual as hipóteses que fizemos façam sentido deve ser também solução do sistema \begin{equation}\begin{cases}Df(\boldsymbol{x})+\sum_{i=1}^d \lambda_i DG_i(\boldsymbol{x})=0 \\ G(\boldsymbol{x})=\boldsymbol{0} \end{cases}\label{eq:20:sel}\end{equation} que é conhecido por sistema de Euler-Lagrange e em que os $d$ números $\lambda_i$ são conhecidos por multiplicadores de Lagrange. Note que se trata de um sistema de $n+d$ equações a $n+d$ incógnitas.

Teorema (de Euler-Lagrange). Sejam $A\subset\mathbb{R}^n$ um aberto, $\boldsymbol{x}_0\in A$, $f:A\subset\mathbb{R}^n\to \mathbb{R}$ uma função diferenciável e $G:A\to\subset\mathbb{R}^d$ uma função de classe $C^1(A)$ tal que $M=\{\boldsymbol{x}:G(\boldsymbol{x})=\boldsymbol{0}\}$ é uma variedade de classe $C^1$. Se $\boldsymbol{x}_0$ é um ponto de extremo da restrição de $f$ a $M$ e $DG(\boldsymbol{x}_0)$ é sobrejectiva, então existem $d$ números reais $\lambda_1, \dots, \lambda_d$ tais que $\boldsymbol{x}_0$ satisfaz ($\ref{eq:20:sel}$).

Teste

Tal como o sistema de estacionaridade para extremos em pontos interiores ao domínio, o sistema de Euler-Lagrange fornece uma condição necessária para existência de um extremo. Frequentemente usaremos argumentos casuísticos para estabelecer se as soluções desse sistema são ou não pontos de extremo. Por exemplo, se a restrição define uma variedade limitada e fechada, usaremos muitas vezes o teorema de Weierstrass e o cálculo da função num número finito de soluções para determinar os pontos de extremo absoluto. No entanto também discutiremos o análogo dos métodos baseados em termos de segunda ordem da fórmula de Taylor.

Para funções e condições relativamente simples é possível resolver analiticamente o sistema de Euler-Lagrange.

Consideramos a seguir exemplos ilustrativos do método. O primeiro é um exemplo modelo em baixa dimensão que nos permitirá ganhar alguma intuição geométrica.

Exemplo. Considere-se o problema que consiste em determinar os extremos absolutos de $x^2+y^2$ sobre a linha de equação $x^2+y^4=1$.

Introduzindo $f(x,y)=x^2+y^2$ e $G(x,y)=x^2+y^4$ obtemos o sistema de Euler-Lagrange: \[\begin{cases}2x+2\lambda x  = 0, \\  2 y+4 \lambda y^3 =0, \\  x^2+y^4 =1. \end{cases}\] A primeira equação pode ser satisfeita com $x=0$ ou $\lambda =-1$.

Consideremos primeiro o caso $x=0$. Da terceira equação então $y=\pm 1$ e podemos satisfazer a segunda equação com $\lambda = -1/2$. Obtivemos assim duas soluções do sistema que correspondem a $(x,y)=(0,1)$ e $(x,y)=(0,-1)$.

Considera-se agora eventuais soluções correspondendo a $\lambda=-1$. Com este valor de $\lambda$ a segunda equação toma a forma $2y-4y^3=0$ que tem soluções $0$, e $\pm\sqrt{2}/2$. Os valores correspondentes de $x$ podem ser obtidos da terceira equação obtendo-se soluções correspondentes a $(x,y)=(1,0), (-1,0)$, $(\sqrt{3}/2,\sqrt{2}/2)$, $(-\sqrt{3}/2,\sqrt{2}/2)$, $(-\sqrt{3}/2,-\sqrt{2}/2)$, e $(\sqrt{3}/2,-\sqrt{2}/2)$.

Note-se que nos 8 pontos determinados a função $f$ só toma dois valores: $1$ em $(0,1)$, $(0,-1)$, $(1,0)$ e $(-1,0)$; $5/4$ em $(\sqrt{3}/2,\sqrt{2}/2)$, $(-\sqrt{3}/2,\sqrt{2}/2)$, $(-\sqrt{3}/2,-\sqrt{2}/2)$, e $(\sqrt{3}/2,-\sqrt{2}/2)$.

Dado que o conjunto $S=\{(x,y)\in\mathbb{R}^2: x^2+ y^4=1\}$ é um conjunto limitado e fechado, a continuidade de $f$ garante, via teorema de Weierstrass, a existência de máximo e mínimo absoluto de $f$ em $S$, que serão $5/4$ e $1$ respectivamente, ocorrendo nos pontos de extremo indicados atrás.

Note que sendo $f$ o quadrado da distância à origem o que estivemos a fazer correspondeu a determinar os pontos a maior e menor distância à origem sobre a linha $x^2+y^4=1$. Fim de exemplo.

Teste

O exemplo seguinte é uma aplicação clássica.

Exemplo (Média aritmética e média geométrica). A média aritmética de $n$ números reais não negativos $y_1,\dots, y_n$ é dada por $\frac{1}{n}\sum_{i=1}^n y_i$ e a média geométrica é dada por $\sqrt[n]{y_1\dots y_n}$. Vamos provar, através de um problema de extremos condicionados, que a média geométrica é sempre menor ou igual à média aritmética. Para isso definimos $f:\mathbb{R}^n\to \mathbb{R}$ via $f(x_1,\dots, x_n)=x_1\dots x_n$ e procuramos os extremos absolutos de $f$ em $S^{n-1}=\{(x_1,\dots,x_n)\in\mathbb{R}^n:x_1^2+\dots+x_n^2=1\}$. Note que sabemos que esses extremos existem pelo teorema de Weierstrass e que terão que ser soluções do sistema de Euler-Lagrange.

O sistema de Euler-Lagrange neste caso é \[\begin{cases} x_2 x_3\dots x_n+\lambda 2x_1 = 0 \\ x_1 x_3\dots x_n+\lambda 2x_2 = 0 \\ \dots \\ x_1 x_2\dots x_{n-1}+\lambda 2x_n = 0 \\ x_1^2+x_2^2+\dots+x_n^2=1 \end{cases}\] Multiplicando ambos os membros da primeira equação por $x_1$, ambos os membros da segunda equação por $x_2$,..., ambos os membros da $n$-ésima equação por $x_n$ e adicionando membro a membro as $n$ equações que obtemos dessa forma, estabelecemos que quaisquer soluções devem satisfazer \[n x_1 x_2\dots x_n + 2\lambda (x_1^2 + x_2^2+ \dots + x_n^2)=0.\] Daí que, usando a última equação do sistema, conseguimos eliminar $\lambda$ via $\lambda=-\frac{1}{2}n x_1 x_2\dots x_n$, obtendo-se \[\begin{cases} x_2 x_3\dots x_n- n x_1^2  x_2\dots x_n= 0 \\ x_1 x_3 \dots x_n-n x_1 x_2^2\dots x_n = 0 \\ \dots \\ x_1 x_2\dots x_{n-1}- n x_1 x_2 \dots x_n^2 = 0. \end{cases}\] Notando que soluções em que uma coordenada é nula não conduzem de certeza a extremos absolutos vamos limitarnos a considerar as soluções verificando $|x_i|=\frac{1}{\sqrt{n}}$ para cada $i$. Nestes pontos $f$ vale $\pm n^{-n/2}$ dependendo o sinal do número de coordenadas com valor negativo ser par ou ímpar. Portanto o máximo absoluto de $f$ sobre $S^{n-1}$ é $ n^{-n/2}$ e o mínimo absoluto é $- n^{-n/2}$.

Sejam agora $y_1,\dots,y_n\gt 0$ e $x_1,\dots,x_n\gt 0$ tais que $x_i^2=y_i$ para $i=1,\dots,n$. Então \[\sqrt[n]{y_1\dots y_n} = \sqrt[n]{x_1^2\dots x_n^2} = \left(\sqrt[n]{x_1\dots x_n}\right)^2 \frac{\sum_{i=1}^n x_i^2}{\sum_{i=1}^n x_i^2}  = \left(f\left(\frac{x_1}{(\sum x_i^2)^{1/2}},\dots, \frac{x_n}{(\sum x_i^2)^{1/2})}\right)\right)^{2/n} \sum x_i^2\leq \frac{ \sum x_i^2}{n}= \frac{ \sum y_i}{n}\] provando que a média aritmética é maior ou igual à média geométrica. Fim de exemplo.

Exemplo (Extremos de formas quadráticas sobre $\partial B_1(\boldsymbol{0})$). Seja $S$ uma matriz simétrica real $n\times n$ definindo uma forma quadrática $Q$ via $Q(\boldsymbol{x})=S\boldsymbol{x} \cdot \boldsymbol{x}$. Consideramos o problema que consiste em determinar quanto valem e aonde ocorrem os extremos de $Q$ sobre $\partial B_1(\boldsymbol{0})$ (que tais extremos existem é uma consequência do teorema de Weierstrass). Tal é um problema de extremos condicionados para $Q$ sob a restrição $G(\boldsymbol{x})=0$ em que $G(\boldsymbol{x})=\|\boldsymbol{x}\|^2 - 1$.

Acontece que, como \[Q(\boldsymbol{x}+\boldsymbol{h}) - Q(\boldsymbol{x})=  2 S\boldsymbol{x} \cdot \boldsymbol{h} + S\boldsymbol{h} \cdot \boldsymbol{h},\] estabelecemos com facilidade que derivada de $Q$ num ponto $\boldsymbol{x}$ é a aplicação linear $DQ$ definida por $DQ(\boldsymbol{x})(\boldsymbol{h})=2 S\boldsymbol{x} \cdot \boldsymbol{h}$. De forma análoga $DG(\boldsymbol{x})(\boldsymbol{h})= 2 \boldsymbol{x} \cdot \boldsymbol{h}$. Daí que o correspondente sistema de Euler-Lagrange seja simplesmente \[\begin{cases}S \boldsymbol{x} = \lambda \boldsymbol{x} \\ \| \boldsymbol{x}\|^2 = 1.\end{cases}\] Isto mostra que os extremos deste problema ocorrem necessariamente em vectores próprios de $S$ e serão iguais ao maior e menor valores próprios de $S$.

Exercício. Sejam $A$ e $B$ matrizes $n\times n$ reais simétricas definindo formas quadráticas $F(\boldsymbol{x})=A\boldsymbol{x}\cdot \boldsymbol{x}$ e $G(\boldsymbol{x})=B\boldsymbol{x}\cdot \boldsymbol{x}$ sendo $G$ definida positiva. Mostre que os pontos de extremo de $F$ no conjunto $\{\boldsymbol{x}\in\mathbb R^n: G(\boldsymbol{x})=1\}$ são necessariamente vectores próprios de $B^{-1}A$.

Exercício. Aplique o resultado do exemplo anterior ao problema de determinar  $\max_{\boldsymbol{x}\in\mathbb{R}^n\setminus\{ \boldsymbol{0}\}}\frac{\|T(\boldsymbol{x})\|}{\|\boldsymbol{x}\|}$ em que $T$ é uma aplicação linear de $\mathbb{R}^n$ em $\mathbb{R}^n$.

Classificação de soluções do sistema de Euler-Lagrange via métodos de 2ª ordem

Uma questão natural é saber se os métodos de segunda ordem (ou superior) usados para classificar pontos de estacionaridade podem ser usados também para problemas de extremos condicionados. Veremos que sim desde que adaptemos os nossos métodos de uma forma que se vai revelar natural.

Analisemos a situação de uma forma relativamente informal continuando a considerar o problema de determinação de extremos de uma função real $f$ suficientemente regular definida num certo subconjunto de $\mathbb{R}^n$, sob uma condição $G(\boldsymbol{x})=\boldsymbol{0}$ com $G$ também suficientemente regular. Seja $r(t) =(x_i(t))_{i=1,\dots n}$ um caminho regular tal que $\boldsymbol{x}_0=r(0)$ é solução do problema de extremos condicionados e $G(r(t))=\boldsymbol{0}$ para $t$ numa vizinhança de $0$. Então $f(r(t))$ tem um extremo local para $t=0$. Para fixar ideias suponhamos que é um mínimo. Supondo $f$ e $r$ duas vezes diferenciáveis devemos ter \[\begin{gather*}\left.\frac{d}{dt}(f(r(t))\right|_{t=0}= 0, \\ \left.\frac{d^2}{dt^2}(f(r(t))\right|_{t=0}\geq 0.\end{gather*}\] Calculando a segunda derivada \[\frac{d^2}{dt^2}(f(r(t))  =\frac{d}{dt}\left(\sum_{i=1}^n\frac{\partial f}{\partial x_i}(r(t))\frac{dx_i}{dt}\right) =\sum_{i,j=1}^n \frac{\partial^2 f}{\partial x_i \partial x_j}(r(t))\frac{dx_i}{dt}\frac{dx_j}{dt}+\sum_{i=1}^n\frac{\partial f}{\partial x_i}(r(t))\frac{d^2x_i}{dt^2}.\] donde \begin{equation}\sum_{i,j=1}^n \frac{\partial^2 f}{\partial x_i \partial x_j}(\boldsymbol{x}_0)\frac{dx_i}{dt}(0)\frac{dx_j}{dt}(0)+\sum_{i=1}^n\frac{\partial f}{\partial x_i}(\boldsymbol{x}_0)\frac{d^2x_i}{dt^2}(0)\geq 0. \label{eq:20:1}\end{equation}

Como $G(r(t))\equiv 0$, um cálculo análogo conduz-nos, para $k=1,\dots, d$, a \begin{equation}\sum_{i,j=1}^n \frac{\partial^2 G_k}{\partial x_i \partial x_j}(\boldsymbol{x}_0)\frac{dx_i}{dt}(0)\frac{dx_j}{dt}(0)+\sum_{i=1}^n\frac{\partial G_k}{\partial x_i}(\boldsymbol{x}_0)\frac{d^2x_i}{dt^2}(0)= 0. \label{eq:20:2}\end{equation}

Como $\boldsymbol{x}_0$ é uma solução do sistema de Euler-Lagrange podemos combinar ($\ref{eq:20:1}$) e ($\ref{eq:20:2}$) de maneira a obter \[\sum_{i,j=1}^n \frac{\partial^2 (f+\sum_{k=1}^d \lambda_k G_k)}{\partial x_i \partial x_j}(\boldsymbol{x}_0)\frac{dx_i}{dt}(0)\frac{dx_j}{dt}(0)\geq 0.\]

Assim, se $(\boldsymbol{x}_0,(\lambda_k)_{k=1,\dots,d})$ é uma solução do sistema de Euler-Lagrange que é um ponto de mínimo (resp. máximo), a matriz hessiana de $f+\sum_{k=1}^d \lambda_k G_k$ no ponto $\boldsymbol{x}_0$ define uma forma quadrática que toma valores não negativos (resp. não positivos) nas direcções tangenciais à variedade $M$ definida por $G(\boldsymbol{x})=\boldsymbol{0}$ em $\boldsymbol{x}_0$.

Reciprocamente suponha-se que $(\boldsymbol{x}_0,(\lambda_k)_{k=1,\dots,d})$ é uma solução do sistema de Euler-Lagrange e que a matriz hessiana $H$ de $f+\sum_{k=1}^d \lambda_k G_k$ no ponto $\boldsymbol{x}_0$ define uma forma quadrática que toma valores positivos (resp. negativos) nas direcções tangenciais à variedade $M$ naquele ponto. Será que podemos concluir que $\boldsymbol{x}_0$ é um ponto de mínimo (resp. máximo) relativo da restrição de $f$ à variedade $M$? A resposta à pergunta anterior é afirmativa e esboçamos a seguir uma justificação.

Mais detalhes

Começamos por notar que a demonstração do critério análogo para extremos em pontos interiores ao domínio também é utilizável se só tivermos informação quanto ao sinal da forma quadrática em direcções definindo um cone fechado $C$ de vértice $\boldsymbol{x}_0$ em $\mathbb{R}^n$ (isto é um conjunto fechado invariante por homotetias de razão positiva) obtendo-se nesse caso a existência de um extremo da restrição da função a $\boldsymbol{x}_0+T_M(\boldsymbol{x}_0)\equiv\{\boldsymbol{x}_0+\lambda \boldsymbol{h}: \boldsymbol{h}\in C, \lambda \geq 0\}$. Seja $P$ a projecção sobre o espaço tangente a $M$ no ponto $\boldsymbol{x}_0$ e $I$ a identidade. Por continuidade da forma quadrática definida por $H$  sobre $S^{n-1}$, esta tem valores positivos para direcções não nulas num cone fechado  $C_\epsilon \equiv \{\boldsymbol{h}\in \mathbb{R}^n: \|(I-P)(\boldsymbol{h})\| \leq \epsilon \|P(\boldsymbol{h})\|\}$, para $\epsilon\gt 0$ e suficientemente pequeno. Podemos então afirmar que a restrição de $f+\sum_{k=1}^d \lambda_k G_k$ a $\boldsymbol{x}_0+C_\epsilon$ tem um mínimo (resp. máximo) local em $\boldsymbol{x}_0$.

Ora existe $r\gt 0$ tal que $B_r(\boldsymbol{x}_0)\cap M \subset \{\boldsymbol{x}_0+ \boldsymbol{h}: \boldsymbol{h}\in C_\epsilon\}$. Então podemos também afirmar que a restrição de $f+\sum_{k=1}^d \lambda_k G_k$ a $\boldsymbol{x}_0+C_\epsilon$ tem um mínimo (resp. máximo) local em $\boldsymbol{x}_0$. Mas como $\sum_{k=1}^d \lambda_k G_k\equiv 0$ sobre $M$ concluímos que $\boldsymbol{x}_0$ é um ponto de mínimo (resp. máximo) local da restrição de $f$ a $M$.