Colabore! Saiba mais screen_rotation

Ao navegar por este site , você concorda com a Política de Uso de Dados.

| | | | |

2 Sistemas Não Lineares e Otimização 2.1 Sistemas Não-Lineares 3 Autovalores e Autovetores

2.2 Problemas de Minimização

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

Em revisão

Vamos considerar o seguinte problema de minimização: dada a função objetivo $f:D\subset\mathbb{R}^{n}\to\mathbb{R}$ , resolver

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}\min_{% \boldsymbol{x}\in D}f(\boldsymbol{x}).

(2.29)

No que segue e salvo dito explicitamente ao contrário, vamos assumir que o problema está bem determinado e que $f$ é suficientemente suave. Ainda, vamos assumir as seguintes notações:

•

gradiente de $f$

$\nabla f(\boldsymbol{x})=\left(\frac{\partial f}{\partial x_{1}}(\boldsymbol{x% }),\dotsc,\frac{\partial f}{\partial x_{n}}(\boldsymbol{x})\right)$ (2.30)
•

derivada direcional de $f$ com respeito a $\boldsymbol{d}\in\mathbb{R}^{n}$

$\frac{\partial f}{\partial\boldsymbol{d}}(\boldsymbol{x})=\nabla f(\boldsymbol% {x})\cdot\boldsymbol{d}$ (2.31)
•

matriz hessiana de $f$ , $H=[h_{i,j}]_{i,j=1}^{n,n}$

$h_{i,j}(\boldsymbol{x})=\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}(% \boldsymbol{x})$ (2.32)

Observação 2.2.1 (Condições de Otimização).

Se $\nabla f(\boldsymbol{x}^{*})=0$ e $H(\boldsymbol{x}^{*})$ é positiva definida, então $\boldsymbol{x}^{*}$ é um mínimo local de $f$ em uma vizinhança não vazia de $\boldsymbol{x}^{*}$ . Consulte mais em [8, Seção 7.2]. Um ponto $\boldsymbol{x}^{*}$ tal que $\nabla f(\boldsymbol{x}^{*})=0$ é chamado de ponto crítico.

2.2.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 $\boldsymbol{x}^{(0)}\in\mathbb{R}^{n}$ , computa-se

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}\boldsymbol{x}% ^{(k+1)}=\boldsymbol{x}^{(k)}+\alpha^{(k)}\boldsymbol{d}^{(k)},

(2.33)

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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}\boldsymbol{d}% ^{(k)}\cdot\nabla f(\boldsymbol{x}^{(k)})<0,\quad\text{se }\nabla f(% \boldsymbol{x}^{(k)})\neq 0,$		(2.34)
	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}\boldsymbol{d}% ^{(k)}=0,\quad\text{noutro caso.}$		(2.35)

Observação 2.2.2 (Condição de Convergência).

Da Série de Taylor⁴⁰⁴⁰endnote: ⁴⁰Brook Taylor, 1685 - 1731, matemático britânico. Fonte: Wikipédia:Brook Taylor., temos que

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

(2.36)

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

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

(2.37)

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

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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}\min_{\alpha% \in\mathbb{R}}\phi(\alpha):=f(\boldsymbol{x}^{(k)}+\alpha\boldsymbol{d}^{(k)}).

(2.38)

Entretanto, a resolução exata deste problema é muitas vezes não factível. Técnicas de aproximações para a resolução deste problema são, então, aplicadas. Tais técnicas são chamadas de pesquisa linear não exata.

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

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

(2.39)

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

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

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

(2.40)

para $\beta\in[\sigma,1/2]$ . Notemos que o lado esquerdo de (2.40) é igual a $\phi^{\prime}(\alpha^{(k)})$ . Ou seja, este condição impõe que $\alpha^{(k)}$ seja maior que $\beta\phi^{\prime}(0)$ . Normalmente, escolhe-se $\beta\in[10^{-1},1/2]$ . Juntas, (2.39) e (2.40) são conhecidas como condições de Wolfe⁴¹⁴¹endnote: ⁴¹Philip Wolfe, 1927 - 2016, matemático estadunidense. Fonte: Wikipédia..

2.2.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 o oposto do gradiente da $f$ , i.e.

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

(2.41)

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

Exemplo 2.2.1.

Consideramos o problema de encontrar o mínimo da função de Rosenbrock⁴²⁴²endnote: ⁴²Howard 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}.

(2.42)

O valor mínimo desta função é zero e ocorre no ponto $\boldsymbol{x}=\boldsymbol{1}$ . Esta função é comumente usada como caso padrão para teste de métodos de otimização.

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

	$\displaystyle\frac{\partial f}{\partial x_{1}}=-400x_{1}\left(x_{2}-x_{1}^{2}% \right)-2(1-x_{1})$		(2.43)
	$\displaystyle\frac{\partial f}{\partial x_{j}}=\sum_{i=1}^{n}200\left(x_{i}-x_% {i-1}^{2}\right)(\delta_{i,j}-2x_{i-1}\delta_{i-1,j})$
	$\displaystyle\qquad-2(1-x_{i-1})\delta_{i-1,j}$		(2.44)
	$\displaystyle\frac{\partial f}{\partial x_{n}}=200\left(x_{n}-x_{n-1}^{2}\right)$		(2.45)

onde, $\delta_{i,j}$ é o delta de Kronecker⁴³⁴³endnote: ⁴³Leopold Kronecker, 1923 - 1891, matemático alemão. Fonte: Wikipédia: Leopold Kronecker..

Código 5: Algoritmo do Gradiente

⬇

1import numpy as np

2import numpy.linalg as npla

3import scipy.optimize as spopt

5# fun obj

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

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# problem dimension

25n = 2

27# num max iters

28maxiter = 100000

29# tolerancia

30tol = 1e-10

32# aprox. inicial

33x = np.zeros(n)

35for k in range(maxiter):

36 # direcao 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 # atualizacao

44 x = x + alpha * d

46 nad = npla.norm(alpha * d)

47 nfun = npla.norm(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. 2.2.1.

Aplique o método do gradiente para computar o ponto mínimo da função de Rosenbrock⁴⁴⁴⁴endnote: ⁴⁴Howard 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}

(2.46)

com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

Resposta.

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

E. 2.2.2.

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

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

Resposta.

$f(3,0.5)=0$

E. 2.2.3.

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

		$\displaystyle f(x,y)=\left[1+\left(x+y+1\right)^{2}\left(19-14x\right.\right.$		(2.48)
		$\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]$

Resposta.

$f(0,-1)=3$

E. 2.2.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}

(2.49)

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

Resposta.

$f(1,3)=0$

E. 2.2.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],

(2.50)

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

Resposta.

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

2.2.3 Método de Newton

Em revisão

O método de Newton⁴⁵⁴⁵endnote: ⁴⁵Isaac 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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}\boldsymbol{d}% ^{(k)}=-H^{-1}\left(\boldsymbol{x}^{(k)}\right)\nabla f\left(\boldsymbol{x}^{(% k)}\right),

(2.51)

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

(2.52)

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

(2.53)

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

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

(2.54)

o que leva a (2.51).

Observação 2.2.3 (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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}H(x^{(k)})d^{(% k)}=-\nabla f(x^{(k)}).

(2.55)

Observação 2.2.4 (Solver linear).

O método usado para computar a solução de (2.55) é chamado de solver linear. Por exemplo, Newton-Krylov⁴⁶⁴⁶endnote: ⁴⁶Alexei 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 2.2.2.

Seguindo o Exemplo 2.2.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$	(2.56)
$\displaystyle h_{1,2}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{1}\partial x_{2}}=-400x_{1}$	(2.57)
$\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}$	(2.58)
$\displaystyle h_{n-1,n}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{n-1}\partial x_{n}}=-400x_{n-1}$	(2.59)
$\displaystyle h_{n,n}$	$\displaystyle=\frac{\partial^{2}f}{\partial x_{n-1}}=200$	(2.60)

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 2.2.5 (Métodos Tipo 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.2, exploramos esta técnica no contexto de resolução de sistemas não lineares.

Exercícios

Em revisão

E. 2.2.6.

Aplique o método de Newton para computar o ponto mínimo da função de Rosenbrock⁴⁷⁴⁷endnote: ⁴⁷Howard 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}

(2.61)

com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

Resposta.

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

E. 2.2.7.

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

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

Resposta.

$f(3,0.5)=0$

E. 2.2.8.

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

		$\displaystyle f(x,y)=\left[1+\left(x+y+1\right)^{2}\left(19-14x\right.\right.$		(2.63)
		$\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]$

Resposta.

$f(0,-1)=3$

E. 2.2.9.

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}

(2.64)

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

Resposta.

$f(1,3)=0$

E. 2.2.10.

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],

(2.65)

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

Resposta.

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

2.2.4 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)},

(2.66)

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)})},

(2.67)

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

Observação 2.2.6 (Variantes).

Outras variações comumente empregadas são o Método de Polak-Ribière e suas variantes. Consulte mais em [7, Seção 5.2].

Exemplo 2.2.3.

Implementação do Método de Fletcher-Reeves para a minimização da função de Rosenbrock dada no Exemplo 2.2.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

Exercícios

Em revisão

E. 2.2.11.

Aplique o método um gradiente conjugado para computar o ponto mínimo da função de Rosenbrock⁴⁸⁴⁸endnote: ⁴⁸Howard 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}

(2.68)

com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

Resposta.

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

E. 2.2.12.

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

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

Resposta.

$f(3,0.5)=0$

E. 2.2.13.

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

		$\displaystyle f(x,y)=\left[1+\left(x+y+1\right)^{2}\left(19-14x\right.\right.$		(2.70)
		$\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]$

Resposta.

$f(0,-1)=3$

E. 2.2.14.

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}

(2.71)

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

Resposta.

$f(1,3)=0$

E. 2.2.15.

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],

(2.72)

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

Resposta.

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

Envie seu comentário

As informações preenchidas são enviadas por e-mail para o desenvolvedor do site e tratadas de forma privada. Consulte a Política de Uso de Dados para mais informações. Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

| | | |