Matemática Numérica III

3 Otimização 3.1 Métodos de declive 3.3 Método do gradiente conjugado

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

3.2 Método de Newton

Em revisão

O método de Newton⁶⁶6Isaac Newton, 1642 - 1727, matemático, físico, astrônomo, teólogo e autor inglês. Fonte: Wikipédia: Isaac Newton. para problemas de otimização é um método de declive com direções descendentes

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boldsymbol{d% }^{(k)}=-H^{-1}\left(\boldsymbol{x}^{(k)}\right)\nabla f\left(\boldsymbol{x}^{% (k)}\right),

(3.23)

assumindo que a hessiana $H$ seja definida positiva dentro de uma vizinhança suficientemente grande do ponto de mínimo $\boldsymbol{x}^{*}$ . Esta escolha é baseada no polinômio de Taylor da função objetivo $f$

f\left(\boldsymbol{x}^{(k+1)}\right)\approx f\left(\boldsymbol{x}^{(k)}\right)% +\nabla f\left(\boldsymbol{x}^{(k)}\right)\cdot\boldsymbol{d}^{(k)}+\frac{1}{2% }\boldsymbol{d}^{(k)}\cdot H\left(\boldsymbol{x}^{(k)}\right)\boldsymbol{d}^{(% k)}.

(3.24)

Com isso, escolhemos $\boldsymbol{x}^{(k+1)}$ de forma a minimizar o lado direito desta aproximação, i.e.

\frac{\partial}{\partial d_{i}^{(k)}}\left(f\left(\boldsymbol{x}^{(k)}\right)+% \nabla f\left(\boldsymbol{x}^{(k)}\right)\cdot\boldsymbol{d}^{(k)}+\frac{1}{2}% \boldsymbol{d}^{(k)}\cdot H\left(\boldsymbol{x}^{(k)}\right)\boldsymbol{d}^{(k% )}\right)=0

(3.25)

para $i=1,2,\dotsc,n$ . Ou seja, temos

\nabla f\left(\boldsymbol{x}^{(k)}\right)+H\left(\boldsymbol{x}^{(k)}\right)% \boldsymbol{d}^{(k)}=\boldsymbol{0}

(3.26)

o que leva a (3.23).

Observação 3.2.1.(Computação da direção)

Na implementação computacional, não é necessário computar a inversa da hessiana, a direção $d^{(k)}$ pode ser mais eficientemente computada resolvendo-se

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}H(x^{(k)})d^{% (k)}=-\nabla f(x^{(k)}).

(3.27)

Observação 3.2.2.(Solver linear)

O método usado para computar a solução de (3.27) é chamado de solver linear. Por exemplo, Newton-Krylov⁷⁷7Alexei Nikolajewitsch Krylov, 1863 - 1945, engenheiro e matemático russo. Fonte: Wikipédia. é o nome dado ao método de Newton que utiliza um método de subespaço de Krylov como solver linear. Mais especificamente, Newton-GMRES quando o GMRES é escolhido como solver linear. Uma escolha natural é Newton-GC, tendo em vista que o método de gradiente conjugado é ideal para matriz simétrica e definida positiva.

Exemplo 3.2.1.

Seguindo o Exemplo 3.1.1, temos que a hessiana associada é a matriz simétrica $H=[h_{i,j}]_{i,j=1}^{n,n}$ com

$\displaystyle h_{1,1}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{1}^{2}}=1200x_{1}^{2}-400x_{2}+2$	(3.28)
$\displaystyle h_{1,2}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{1}\partial x_{2}}=-400x_{1}$	(3.29)

$\displaystyle h_{i,j}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}=200(\delta_{i% ,j}-2x_{i-1}\delta_{i-1,j})-400(\delta_{i+1,j}-2x_{i}\delta_{i,j})$
	$\displaystyle-400\delta_{i,j}(x_{i+1}-x_{i}^{2})+2\delta_{i,j}$	(3.30)

$\displaystyle h_{n-1,n}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{n-1}\partial x_{n}}=-400x_{n-1}$	(3.31)
$\displaystyle h_{n,n}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{n-1}}=200$	(3.32)

Notemos que a hessiana é uma matriz tridiagonal.

⬇

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

24def hess(x):

25 x = np.asarray(x)

26 H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)

27 diagonal = np.zeros_like(x)

28 diagonal[0] = 1200*x[0]**2-400*x[1]+2

29 diagonal[-1] = 200

30 diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]

31 H = H + np.diag(diagonal)

33 return H

35# dimensao

36n = 2

38# num max iters

39maxiter = 100000

40# tolerancia

41tol = 1e-10

43# aprox. inicial

44x = np.zeros(n)

46for k in range(maxiter):

48 # direcao descendente

49 d = npla.solve (hess(x),-grad(x))

51 # pesquisa linear

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

54 # atualizacao

55 x = x + alpha * d

57 nad = npla.norm(alpha * d)

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

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

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

63 break

Observação 3.2.3.(Métodos quasi-Newton)

Métodos tipo Newton são aqueles que utilizam uma aproximação para a inversa da matriz hessiana. Uma estratégia comumente aplicada, é a de atualizar a hessiana apenas em algumas iterações, baseando-se em uma estimativa da taxa de convergência. Na Subseção 2.1.1, exploramos esta técnica no contexto de resolução de sistemas não lineares.

Exercícios

Em revisão

E. 3.2.1.

Aplique o método de Newton para computar o ponto mínimo da função de Rosenbrock⁸⁸8Howard 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.33)

com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

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

E. 3.2.2.

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

		$\displaystyle f(x,y)=(1.5-x+xy)^{2}$		(3.34)
		$\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.2.3.

Aplique o método de Newton 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.35)
		$\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.2.4.

Aplique o método de Newton 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.36)

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

$f(1,3)=0$

E. 3.2.5.

Aplique o método de Newton 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.37)

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