User Tools

Site Tools


otimizacao

This is an old revision of the document!


Error loading plugin vshare
ParseError: syntax error, unexpected 'fn' (T_STRING), expecting :: (T_PAAMAYIM_NEKUDOTAYIM)
More info is available in the error log.

Suponhamos $ f: S \subset \mathbb{R}^n \rightarrow \mathbb{R}$ e objetivo é achar máximo ou mínimo absoluto (global) da função (no conjunto $ S $).

Como já discutimos, se o ponto máximo ou mínimo estiver no interior do conjunto $ S $ necessariamente este ponto tem que ser um ponto crítico (se a função for diferenciável). Porém, precisamos verificar os pontos da fronteira (em S) e os pontos onde a função não é diferenciável para achar máximo/mínimo global.

Observação:

  • Se $ S $ é um conjunto fechado e limitado e $ f $ função contínua, sabemos que $ f $ tem máximo e mínimo.
  • Se $ S $ não for limitado ou não contem alguns de seus pontos de fronteira, é possível que $ f $ não tenha máximo ou mínimo global. Nestes casos, precisamos analisar o comportamento da função quando $ \|x\| \rightarrow \infty$ ou quando $ x $ converge a fronteira do conjunto $ S. $

Exemplos:

Ache o máximo/mínimo da fução dada por $ f(x, y)=x^2+y^2+x $ na região $ x^2 + y^2 \leq 1. $

A região dada é disco fechado de raio um que é fechada e limitada. Os pontos crítico:

$ \nabla f(x, y) = (2x+1, 2y) = (0, 0) $ e portanto $ (x, y)= (-\frac{1}{2}, 0). $ Neste ponto $ f(-\frac{1}{2},0)=-\frac{1}{4}. $

Agora anlisamos pontos da fronteira: $ x^2+y^2=1 $ e portanto $ f(x, y)= 1+x $. já que na fronteira $ -1 \leq x \leq 1 $ concluímos que o máximo na fronteira é $ 2 $ e mínimo é obtido no ponto $ (-1,0) $ com valor $ 0. $ Considerando estes tries valores temos que máximo global é $ 2 $ e obtido na fronteira, enquanto o mínimo global é alcançado no interior e o valor é $ -\frac{1}{4}. $

Exemplo: Ache máximo e mínimo da função $ f(x, y )= \frac{|xy|}{x^2+y^2+1}$ em $ \mathbb{R}^2. $

A existência de valor absoluto mostra que provavelmente a função não é diferenciável quando $ xy=0. $ Porém neste conjunto (união de duas retas) o valor da função é zero e certamente mínimo.

Então vamos analisar apenas quando $ x> 0, y>0 $ (por simetria).

$ \nabla f(x,y)=(\frac{y(y^2 +1 - x^2)}{(x^2+y^2+1)^2}, \frac{x(x^2+1-y^2)}{(x^2+y^2+1)^2})$

Verifique que não existe nenhum ponto crítico em $ x > 0, y > 0 $ pois as curvas $ x^1+1=y^2, y^2+1=x^2 $ não se cruzam.

Observe também que $ \frac{|xy|}{x^2+y^2+1} < \frac{1}{2} $ e o limite ao longo da reta $ y=x $ uando $ x\rightarrow \infty $ é $ \frac{1}{2} $ e portanto não temos máximo.

Em geral parece difícil achar máximo/mínimo ao longo de uma curva fronteira. O método de Lagrange é poderoso para tratar este problema!

Método de Lagrange

Seja $ g: U \subset \mathbb{R}^n \rightarrow \mathbb{R} $ com derivadas parciais contínuas e $ M $ um conjunto de nível

$ M = \{x \in U | g(x)=c\}. $

Queremos achar máximo de uma função $ f: U \rightarrow \mathbb{R} $ restrita ao conjunto $ M. $

Seuponhamos que $ a $ um máximo ou mínimo local de restrição da $ f $ a $ M $ e que $ a $ não seja um ponto crítico de $ g $ então $ \nabla f(a) $ é ortogonal a $ M$ no ponto $ a. $ Portanto já que $ a $ não é crítico para $ g $ temos:

$ \nabla f(a) = \lambda \nabla g(a). $

De fato $ \nabla g(a) \neq 0 $ implica que $ M $ tem vetor normal no ponto $ a $ e existe um plano tangente a $ M. $ Seja $ v $ um vetor no plano tangente e $ \gamma: I \rightarrow \mathbb{R}^n $ tal que

$ \gamma (0)=a, \gamma^{'}(0)=v. $ Já que ponto $ a $ é máximo/mínimo em $ M $ então restrito a curva também é máximo/mínimo: $ \frac{d}{dt} (f \circ \gamma)(t)|_{t=0} = 0. $

Pela regra da cadeia:

$ 0 = \nabla f(\gamma(0)) . \gamma^{'}(0) = \nabla f (a) . v = 0. $

Portanto o vetor gradiente $ \nabla f (a) $ é ortogonal a $ M $ e lembre que $ \nabla g (a) $ também é ortognal a $ M $ e consequentemente, os dois vetores gradientes são paralelos:

$ \nabla f (a) = \lambda \nabla g (a). $

Teorema: Seja $ a $ um ponto max/min da função $ f $ restrita ao conjunto $ M= \{g=0\} $ e suponhamos que $ a $ não seja um ponto crítico da $ g. $ Então $ \nabla f (a) $ é ortogonal a $ M $ no ponto $ a. $ Já que $ \nabla g (a) \neq 0 $ portanto existe $ \lambda \in \mathbb{R} $ tal que $ \nabla f (a) = \lambda \nabla g (a). $

Duas interpretação super intuitivas e honestas:

Para achar máximo/mínimo de $ f $ no conjunto $ M $ vamos imaginar individuos morando no conjunto $ M. $ Estes indivíduos não tem noção do mundo externo $ \mathbb{R}^n $ e já que $ \nabla g (a)\neq 0 $ o mundo deles localmente parece com $ \mathbb{R}^{n-1}. $ Se o ponto $ a $ é máx/min, para eles deve ser um ponto crítico. Porém o que é o gradiente da função restrita ao mundo deles?????

Aha, deve ser a sombra do gradiente $ \nabla f (a) $ no mundo deles! Portanto a projeção de $ \nabla f(a) $ sobre $ M $ no ponto $ a $ deve ser zero que isto implica ortogonalidade a $ M $ e também paralelismo de $ \nabla f (a) $ e $ \nabla g (a).$

Agora vamos abordar de outra forma, usando um exemplo explícito: Considere superfície dada por $ M:=\{g=c\} $ $ p=(p_1, \cdots, p_n) $ um ponto fora do conjunto $ M. $ Ache os pontos no conjunto $ M $ que minimizam (ou pelo menos localmente minimizam) a distância até o ponto $ p. $

Imagine um balão ocm centro $ p $ sendo enchido até tocar pela primeira vez o conjunto $ M. $ A ideia intuitiva é que sob certas hipôtese de regularidade, no ponto $ (x_1, \cdots x_n) $ em que a esfera toca $ M $ o vetor gradiente $ \nabla g (x_1,\cdots, x_n) $ é paralelo ao vetor $ (x_1-p_1, \cdots x_n-p_n)$. Por outro lado a função que estamos interessados a minimizar é a função quadrada de distância:

$ f(x)= \|x-p\|^2 = \sum_{i=1}^{n} |x_i-p_i|^2 $ e

$ \nabla f (x_1, \cdots, x_n) = 2(x_1-p_1, \cdots, x_n - p_n) $

e isto verifica o resultado de Lagrange para este caso especial da função distância.

Exercícios:

Curva de Whatsapp

$ f(x, y) = y^2 -x^3 -x^2 -x$. Usando multiplicadores de Lagrange achamos os pontos no círculo $ x^2+y^2=1$ que maximizam/minimizam a função $ f.$

Essa função foi inspirada por curva elíptica usada pelo Whatsapp ($ y^2=x^3 + 486662x^2 +x$) sobre o número primo $ 2^{255}-19.$

Entropia

A entropia de um vetor de probabilidade $ P=(p_1, \cdots, p_n), \sum_{i=1}^{n} p_i=1 $ é dada por

$ H(P):= - \sum_{i=1}^{n} p_i ln(p_i) $ sendo que definimos $ ``0 \ln(0)=0" $

Mostre que a entropia é máxima quando $ p_i= \frac{1}{n} $ e o valor máximo da entropia é $ ln(n). $

Exemplo: Queremos construir caixa retangular sem tampa com área total 12. Quais devem ser as dimensões para que o volume seja máximo?

$ A= xy + 2xz + 2yz =12$ é a área da caixa sem tampa. Queremos maximizar $ V(x, y,z)=xyz $.

Mais de um vínculo

Agora vamos considerar mais de uma restrição, i.e queremos achar máx/min da função $ f $ restrita aos conjuntos $ \{g_1=0\} $ e $ \{g_2=0\} $, \cdots.

Vamos enunciar com 2 restrições:

Teorema: Seja $ (x_0, y_0, z_0) $ um ponto extremo de $ f $ uma função $ C^1 $ sujeito restrições $ g(x, y, z)=0 $ e $ h(x, y,z)=0 $ onde $ h, g $ são funções $ C^1 $ e $ \nabla g (x_0,y_0, z_0) , \nabla h (x_0, y_0, z_0) $ são vetores linearmente independentes então existem $ \lambda, \mu \in \mathbb{R} $ tais que

$ \nabla f (x_0, y_0, z_0) = \lambda \nabla g (x_0, y_0, z_0) + \mu \nabla h (x_0, y_0, z_0). $

Onde o método não se aplica:

Vamos minimizar a função dada por $ f(x, y)=x $ na curva dada por $ g(x, y)=0 $ onde $ g(x, y)= y^2+x^4-x^3. $

A curva tem um ponto singular $ (0, 0) $, i.e $ \nabla g(0,0)=(0, 0).$ O ponto $ (0, 0) $ é um mínimo para $ f $. Porém o teorema de Lagrange não vale neste caso:

$ \nabla f (x, y) =(1, 0) $ e portanto não existe $ \lambda \in \mathbb{R} $ tal que $ \nabla f (0, 0) = \lambda \nabla g (0, 0). $

Exemplo: Considere seguintes restrições

$ g(x, y, z) = x^6 - z =0, h(x, y, z) = y^3 - z=0. $ Observe que a interseção destes dois conjuntos de nível é uma curva com seguinte parametrzação:

$ S: x \rightarrow (x, x^2, x^6), x \in \mathbb{R}. $ Agora considere $ f: \mathbb{R}^3 \rightarrow \mathbb{R}, f(x, y, z) =y. $ Observe que o ponto $ (0, 0, 0) $ é mínimo e vamos verificar se satisfaz conclusão do teorema de Lagrange:

$ \nabla f (0, 0, 0) = (0, 1, 0), \nabla g(0, 0 ,0)= (0,0,-1) = \nabla h(0,0,0) $ e portanto $ \lambda \nabla g + \mu \nabla h(0, 0, 0) = (0,0,-\lambda -\mu) $ que não pode ser igual ao vetor $ (0, 1, 0) $.

otimizacao.1695657836.txt.gz · Last modified: 2023/09/25 13:03 by 143.107.183.174