✎ otimizacao []

You've loaded an old revision of the document! If you save it, you will create a new version with this data.

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:

- Ordered List Item Se $  S $ é um conjunto fechado e limitado e $  f $ função contínua, sabemos que $  f $ tem máximo e mínimo.

- Ordered List Item 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. $

<color #ed1c24>Exemplos:</color>

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}. $

<color #ed1c24>Exemplo:</color> 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.$

<color #22b14c>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.$</color>

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). $

<color #ed1c24>Exemplo:</color> 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) $.

Edit summary

Note: By editing this page you agree to license your content under the following license: CC Attribution-Share Alike 4.0 International