Matemática Numérica III

3 Otimização 3.2 Método de Newton 4 Autovalores e Autovetores

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

3.3 Método do gradiente conjugado

Em revisão

Métodos do gradiente conjugado são obtidos escolhendo-se as direções descendentes

d^{(k)}=-\nabla f(x^{(k)})+\beta_{k}d^{(k-1)},

(3.38)

onde $\beta_{k}$ é um escalar escolhido de forma que as direções $\{d^{(k)}\}$ sejam mutuamente ortogonais com respeito a uma dada norma. Por exemplo, o método de Fletcher-Reeves consiste em escolher

\beta_{k}=\frac{\nabla f(x^{(k)})\cdot\nabla f(x^{(k)})}{\nabla f(x^{(k-1)})% \cdot\nabla f(x^{(k-1)})},

(3.39)

o que garante que as direções sejam mutuamente ortogonais com respeito ao produto interno euclidiano.

Exemplo 3.3.1.

Implementação do Método de Fletcher-Reeves para a minimização da função de Rosenbrock dada no Exemplo 3.1.1.

⬇

1import numpy as np

2import numpy.linalg as npla

3import scipy.optimize as spopt

5# fun obj

6def fun(x):

7 '''

8 Funcao de Rosenbrock

9 '''

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

12# gradiente da fun

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# dimensao do prob

25n = 2

27# num max iters

28maxiter = 100000

29# tolerancia

30tol = 1e-10

32# aprox. inicial

33x = np.zeros(n)

35# iteracoes CG

36gf = grad(x)

37d = -gf

39for k in range(maxiter):

41 # pesquisa linear

42 alpha = spopt.line_search(fun, grad, x, d)[0]

44 # atualizacao

45 x = x + alpha * d

47 nad = npla.norm(alpha * d)

48 nfun = npla.norm(fun(x))

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

52 if ((nfun < tol) or np.isnan(nfun)):

53 break

55 # prepara nova iter

56 ngf = grad(x)

58 beta = np.dot(ngf,ngf)/np.dot(gf,gf)

59 d = -ngf + beta * d

61 gf = ngf

3.3.1 Variantes

Há várias variantes do método Fletcher-Reeves⁹⁹9Para mais detalhes, consultemos [Nocedal2006]. Algumas das mais empregadas são:

•

Método de Polak-Ribière

$\beta_{k}=\frac{\nabla f^{(k+1)}\cdot(\nabla f^{(k+1)}-\nabla f^{(}k))}{\|% \nabla f^{(}k)\|^{2}}$ (3.40)
•

Método de Hestenes-Stiefel

$\beta_{k}=\frac{\nabla f^{(k+1)}\cdot(\nabla f^{(k+1)}-\nabla f^{(}k))}{(% \nabla f^{(k+1)}-\nabla f^{(}k))\cdot d^{(}k)}$ (3.41)

Exercícios

Em revisão

E. 3.3.1.

Aplique o método um gradiente conjugado para computar o ponto mínimo da função de Rosenbrock¹⁰¹⁰10Howard Harry Rosenbrock, 1920 - 2010, engenheiro britânico. Fonte: Wikipedia: Howard Harry Rosenbrock.

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

(3.42)

com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

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

E. 3.3.2.

Aplique o método um gradiente conjugado para computar o ponto mínimo da função de Beale [Beale1955a]

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

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

$f(3,0.5)=0$

E. 3.3.3.

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

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

$f(0,-1)=3$

E. 3.3.4.

Aplique o método um gradiente conjugado 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.45)

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

$f(1,3)=0$

E. 3.3.5.

Aplique um método do gradiente conjugado 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.46)

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

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

$f(\boldsymbol{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