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

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boldsymbol{x% }^{(k+1)}=\boldsymbol{x}^{(k)}+\alpha^{(k)}\boldsymbol{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}% \boldsymbol{d}^{(k)}\cdot\nabla f(\boldsymbol{x}^{(k)})<0,\quad\text{se }% \nabla f(\boldsymbol{x}^{(k)})\neq 0,$		(3.6)
	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{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(\boldsymbol{x}^{(k)}+\alpha^{(k)}\boldsymbol{d}^{(k)})-f(\boldsymbol{x}^{(k)% })=\alpha^{(k)}\nabla f(\boldsymbol{x}^{(k)})\cdot\boldsymbol{d}^{(k)}+\varepsilon,

(3.8)

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

(3.9)

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.

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(\boldsymbol{x}^{(k)}+\alpha\boldsymbol{d}^{(k)}).

(3.10)

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.

Condições de Wolfe

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

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

(3.11)

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 (3.11) 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}\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)},

(3.12)

para $\beta\in[\sigma,1/2]$ . Notemos que o lado esquerdo de (3.12) é 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, (3.11) e (3.12) são conhecidas como condições de Wolfe²²2Philip Wolfe, 1927 - 2016, matemático estadunidense. Fonte: Wikipédia..

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

\boldsymbol{d}^{(k)}=-\nabla f(\boldsymbol{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(\boldsymbol{x})=\sum_{i=1}^{n}100\left(x_{i+1}-x_{i}^{2}\right)^{2}+(1-x_{i}% )^{2}.

(3.14)

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})$		(3.15)
	$\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}$		(3.16)
	$\displaystyle\frac{\partial f}{\partial x_{n}}=200\left(x_{n}-x_{n-1}^{2}\right)$		(3.17)

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

Código 14: 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. 3.1.1.

Aplique o método do gradiente para computar o ponto mínimo da função de Rosenbrock⁵⁵5Howard 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.18)

com

a)

$n=2$ .
b)

$n=3$ .
c)

$n=4$ .
d)

$n=5$ .
e)

$n=10$ .

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

E. 3.1.2.

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

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

Aplique o método do gradiente 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.20)
		$\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.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 $\boldsymbol{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 $\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

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