Matemática numérica III

3 Otimização 3 Otimização 3.2 Método de Newton

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

3.1 Métodos de declive

Em revisão

Um método de declive consiste em uma iteração tal que, dada uma aproximação inicial $\bm{x}^{(0)}\in\mathbb{R}^{n}$ , computa-se

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bm{x}^{(k+1)% }=\bm{x}^{(k)}+\alpha^{(k)}\bm{d}^{(k)},

(3.5)

com tamanho de passo $\alpha^{(k)}>0$ , para $k=0,1,2,\ldots$ , até que um dado critério de parada seja satisfeito. As direções descendentes são tais que

	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \bm{d}^{(k)}\cdot\nabla f(\bm{x}^{(k)})<0,\quad\text{se }\nabla f(\bm{x}^{(k)}% )\neq 0,$		(3.6)
	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \bm{d}^{(k)}=0,\quad\text{noutro caso.}$		(3.7)

Observação 3.1.1.(Condição de convergência)

Da série de Taylor¹¹1Brook Taylor, 1685 - 1731, matemático britânico. Fonte: Wikipédia: Brook Taylor., temos que

f(\bm{x}^{(k)}+\alpha^{(k)}\bm{d}^{(k)})-f(\bm{x}^{(k)})=\alpha^{(k)}\nabla f(% \bm{x}^{(k)})\cdot\bm{d}^{(k)}+\varepsilon,

(3.8)

com $\varepsilon\to 0$ quando $\alpha^{(k)}\to 0$ . Como consequência da continuidade de $f$ , para $\alpha^{(k)}$ suficientemente pequeno, o sinal do lado esquerdo é igual ao do lado direito da última equação. Logo, para tais $\alpha^{(k)}$ e para uma direção descendente $\bm{d}^{(k)}\neq 0$ , temos garantido que

f(\bm{x}^{(k)}+\alpha^{(k)}\bm{d}^{(k)})<f(\bm{x}^{(k)}).

(3.9)

Notamos que um método de declive fica determinado pelas escolhas da direção de declive $\bm{d}^{(k)}$ e do tamanho do passo $\alpha^{(k)}$ . Primeiramente, trataremos deste último item.

3.1.1 Pesquisa linear

Em revisão

O método de pesquisa linear consiste em escolher $\alpha^{(k)}$ com base na resolução do seguinte problema de minimização

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\min_{\alpha% \in\mathbb{R}}\phi(\alpha):=f(\bm{x}^{(k)}+\alpha\bm{d}^{(k)}).

(3.10)

Entretanto, a resolução exata deste problema muitas vezes não é factível. Aplicam-se, então, técnicas aproximadas para a resolução desse problema. Essas técnicas são chamadas de pesquisa linear não exata.

Condições de Wolfe

Uma abordagem popular de pesquisa linear não exata baseia-se nas condições de Wolfe [9]. Trata-se de duas condições que devem ser satisfeitas pela escolha de $\alpha^{(k)}$ .

A condição de Armijo estabelece que a escolha de $\alpha^{(k)}$ deve ser tal que

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}f\left(\bm{x}% ^{(k)}+\alpha^{(k)}\bm{d}^{(k)}\right)\leq f(\bm{x}^{(k)})+\sigma\alpha^{(k)}% \nabla f\left(\bm{x}^{(k)}\right)\cdot\bm{d}^{(k)},

(3.11)

para alguma constante $\sigma\in(0,1/2)$ . Ou seja, espera-se que a redução em $f$ seja proporcional à derivada direcional de $f$ com relação à direção $\bm{d}^{(k)}$ no ponto $\bm{x}^{(k)}$ . Em aplicações computacionais, $\sigma$ normalmente é escolhido no intervalo $[10^{-5},10^{-1}]$ .

A condição (3.11) não é suficiente para evitar escolhas muito pequenas de $\alpha^{(k)}$ . Para tanto, pode-se empregar a condição de curvatura, que requer que

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\nabla f\left% (\bm{x}^{(k)}+\alpha^{(k)}\bm{d}^{(k)}\right)\cdot\bm{d}^{(k)}\geq\beta\nabla f% \left(\bm{x}^{(k)}\right)\cdot\bm{d}^{(k)},

(3.12)

para $\beta\in(\sigma,1)$ . Notemos que o lado esquerdo de (3.12) é igual a $\phi^{\prime}(\alpha^{(k)})$ . Ou seja, esta condição impõe que $\phi^{\prime}(\alpha^{(k)})$ não seja muito negativa em comparação com $\phi^{\prime}(0)$ . Normalmente, escolhe-se $\beta\in[10^{-1},9\,10^{-1}]$ . Juntas, (3.11) e (3.12) são conhecidas como condições de Wolfe²²2Philip Wolfe, 1927 - 2016, matemático estadunidense. Fonte: Wikipédia: Philip Wolfe..

3.1.2 Método do gradiente

Em revisão

O método do gradiente (ou método do máximo declive) é um método de declive tal que as direções descendentes são opostas ao gradiente de $f$ , isto é,

\bm{d}^{(k)}=-\nabla f(\bm{x}^{(k)}).

(3.13)

É imediato verificar que as condições (3.6)-(3.7) são satisfeitas.

Exemplo 3.1.1.

Consideramos o problema de encontrar o mínimo da função de Rosenbrock³³3Howard Harry Rosenbrock, 1920 - 2010, engenheiro britânico. Fonte: Wikipedia: Howard Harry Rosenbrock.

f(\bm{x})=\sum_{i=1}^{n-1}\left[100\left(x_{i+1}-x_{i}^{2}\right)^{2}+(1-x_{i}% )^{2}\right].

(3.14)

O valor mínimo dessa função é zero e ocorre no ponto $\bm{x}=\bm{1}$ . Essa função é comumente usada como caso-padrão para testar métodos de otimização.

Para o método do gradiente, precisamos das seguintes derivadas parciais:

	$\displaystyle\frac{\partial f}{\partial x_{1}}=-400x_{1}\left(x_{2}-x_{1}^{2}% \right)-2(1-x_{1})$		(3.15)
	$\displaystyle\frac{\partial f}{\partial x_{j}}=200\left(x_{j}-x_{j-1}^{2}% \right)-400x_{j}\left(x_{j+1}-x_{j}^{2}\right)-2(1-x_{j}),\quad j=2,\ldots,n-1$		(3.16)
	$\displaystyle\frac{\partial f}{\partial x_{n}}=200\left(x_{n}-x_{n-1}^{2}\right)$		(3.17)

Código 14: Algoritmo do Gradiente

⬇

1import numpy as np

2import numpy.linalg as npla

3import scipy.optimize as spopt

5# função objetivo

6def fun(x):

7 '''

8 Função de Rosenbrock

9 '''

10 return sum(100.*(x[1:]-x[:-1]**2.)**2. + (1.-x[:-1])**2.)

12# gradiente da função objetivo

13def grad(x):

14 xm = x[1:-1]

15 xm_m1 = x[:-2]

16 xm_p1 = x[2:]

17 der = np.zeros_like(x)

18 der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)

19 der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0])

20 der[-1] = 200*(x[-1]-x[-2]**2)

22 return der

24# dimensão do problema

25n = 2

27# número máximo de iterações

28maxiter = 100000

29# tolerância

30tol = 1e-10

32# aproximação inicial

33x = np.zeros(n)

35for k in range(maxiter):

36 # direção descendente

37 d = -grad(x)

39 # pesquisa linear

40 alpha = spopt.line_search(fun, grad, x, d,

41 c1=0.0001, c2=0.9)[0]

43 # atualização

44 x = x + alpha * d

46 nad = npla.norm(alpha * d)

47 nfun = abs(fun(x))

49 if ((k+1) % 10 == 0):

50 print(f"{k+1}: {alpha:1.2e} {nad:1.2e} {nfun:1.2e}")

52 if (nfun < tol):

53 break

Exercícios

Em revisão

E. 3.1.1.

Aplique o método do gradiente para computar o ponto mínimo da função de Rosenbrock⁴⁴4Howard Harry Rosenbrock, 1920 - 2010, engenheiro britânico. Fonte: Wikipedia: Howard Harry Rosenbrock.

f(\bm{x})=\sum_{i=1}^{n-1}\left[100\left(x_{i+1}-x_{i}^{2}\right)^{2}+(1-x_{i}% )^{2}\right]

(3.18)

com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

$f(\bm{1})=0$

E. 3.1.2.

Aplique o método do gradiente para computar o ponto mínimo da função de Beale [2]

	$\displaystyle f(x,y)=(1.5-x+xy)^{2}+(2.25-x+xy^{2})^{2}$
	$\displaystyle\text{}\qquad+(2.625-x+xy^{3})^{2}.$		(3.19)

para $\bm{x}\in[-4.5,4.5]^{2}$ .

$f(3,0.5)=0$

E. 3.1.3.

Aplique o método do gradiente para computar o ponto mínimo da função de Goldstein-Price [6]

	$\displaystyle f(x,y)=\left[1+\left(x+y+1\right)^{2}\left(19-14x\right.\right.$
	$\displaystyle\text{}\qquad\left.\left.+3x^{2}-14y+6xy+3y^{2}\right)\right]$
	$\displaystyle\text{}\qquad\times\left[30+\left(2x-3y\right)^{2}\left(18-32x% \right.\right.$
	$\displaystyle\text{}\qquad\left.\left.+12x^{2}+48y-36xy+27y^{2}\right)\right]$		(3.20)

$f(0,-1)=3$

E. 3.1.4.

Aplique o método do gradiente para computar o ponto mínimo da função de Booth

f(x,y)=\left(x+2y-7\right)^{2}+\left(2x+y-5\right)^{2}

(3.21)

para $\bm{x}\in[-10,10]^{2}$ .

$f(1,3)=0$

E. 3.1.5.

Aplique o método do gradiente para computar o ponto mínimo da função de Rastrigin

f(x)=10n+\sum_{i=1}^{n}\left[x_{i}^{2}-10\cos(2\pi x_{i})\right],

(3.22)

para $\bm{x}\in[-5.12,5.12]^{n}$ , com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

$f(\bm{0})=0$

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Política de uso de dados

Política de uso de dados

Matemática numérica III

3.1 Métodos de declive

Observação 3.1.1.(Condição de convergência)

3.1.1 Pesquisa linear

Condições de Wolfe

3.1.2 Método do gradiente

Exemplo 3.1.1.

Exercícios

E. 3.1.1.

E. 3.1.2.

E. 3.1.3.

E. 3.1.4.

E. 3.1.5.

Envie seu comentário