• Document: 2005)
  • Size: 94.81 KB
  • Uploaded: 2019-06-13 20:18:13
  • Status: Successfully converted


Some snippets from your converted document:

Optimização e Algoritmos (2004/2005) Instituto Superior Técnico – Engenharia Electrotécnica e de Computadores Série de Problemas 3 Regras de Armijo e Wolfe, Introdução às funções convexas Problema 1.[Regras de Armijo e Wolfe] Considere o problema de op- timização min φ(t) (1) t>0 onde φ : [0, +∞) → R é uma função de classe C 1 (ou seja, diferenciável e com derivada contı́nua). Aqui, assume-se que φ (0) < 0 (ou seja, φ é inicial- mente decrescente). Este programa de optimização surge como subproblema nos algoritmos de optimização que operam por pesquisa em linhas. Nesse contexto, dado que o objectivo primordial é minimizar uma função objec- tivo f em Rn (da qual φ é apenas uma fatia unidimensional), não se torna importante resolver exactamente o problema (1). É suficiente resolver (1) aproximadamente, ou seja, basta encontrar em R+ = (0, +∞) um ponto t que seja “aceitável”. O critério de “aceitabilidade” depende da regra adop- tada. Neste problema, introduzem-se 2 regras: a regra de Armijo e a regra de Wolfe. Ambas as regras estabelecem uma partição de R+ em 3 conjuntos disjuntos: A, D, E. Esses conjuntos têm o seguinte significado: o conjunto A é o conjunto dos pontos “aceitáveis”; D é o conjunto dos pontos demasiado “à direita”; o conjunto E é o conjunto dos pontos demasiado “à esquerda”. (Atenção: esta terminologia não significa forçosamente que, por exemplo, todos os pontos em D sejam estritamente maiores que os pontos em A; veja os exemplos adiante). Mais especificamente, temos A = { t > 0 : φ(t) ≤ φ(0) + σφ (0)t } Armijo: D = { t > 0 : φ(t) > φ(0) + σφ (0)t } (2) E =∅ A = { t > 0 : φ(t) ≤ φ(0) + σφ (0)t e φ (t) ≥ λφ (0) } Wolfe: D = { t > 0 : φ(t) > φ(0) + σφ (0)t } (3) E = { t > 0 : φ(t) ≤ φ(0) + σφ (0)t e φ (t) < λφ (0) } As constantes σ e λ são escolhidas pelo utilizador, mas devem satisfazer 0 < σ < λ < 1. (Note que, para a regra de Armijo, nunca existem pontos demasiado “à esquerda”). (a) [Regra de Armijo: exemplo 1] Considere a função 98 4 95 φ(t) = 8t5 − t + 42t3 − t2 − 3t 3 6 cujo gráfico se apresenta na figura 1. Usando a regra de Armijo, determine (aproximadamente) os conjuntos A, E e D e represente-os em R+ para (i) 1 σ = 0.4 (ii) σ = 0.6 e (iii) σ = 0.8. Sugere-se a utilização do MATLAB 2 1 0 −1 −2 −3 −4 0 0.5 1 1.5 2 2.5 Figura 1: φ(t) [Problema 1(a)] para uma determinação numérica mais precisa de A, D, E. Em qualquer dos casos, é útil neste tipo de problemas começar por desenhar as rectas φ(0) + σφ (0)t sobrepostas ao gráfico da função φ(t). A tı́tulo de exemplo, exibe-se na figura 2 o caso referente a σ = 0.4. (b) [Regra de Armijo: exemplo 2] Repita a alı́nea anterior para a função φ(t) = t2 − 2t cujo gráfico se apresenta na figura 3. (c) [Regra de Wolfe: exemplo 1] Considere de novo a função 98 4 95 φ(t) = 8t5 − t + 42t3 − t2 − 3t 3 6 cujo gráfico se apresenta na figura 1. Usando a regra de Wolfe, determine os conjuntos A, E e D e represente-os em R+ para (i) (σ, λ) = (0.4, 0.6) (ii) (σ, λ) = (0.6, 0.8) e (iii) (σ, λ) = (0.8, 0.9). (d) [Regra de Wolfe: exemplo 2] Considere de novo a função φ(t) = t2 − 2t cujo gráfico se apresenta na figura 3. Usando a regra de Wolfe, determine os conjuntos A, E e D e represente-os em R+ para (i) (σ, λ) = (0.4, 0.6) (ii) (σ, λ) = (0.6, 0.8) e (iii) (σ, λ) = (0.8, 0.9). Problema 2.[Regra de Armijo: propriedade básica] Considere a regra de Armijo descrita no problema 1 e uma função φ : [0, +∞) → R de classe 2 2 1 0 −1 −2 −3 −4 0 0.5 1 1.5 2 2.5 Figura 2: φ(t) e φ(0) + 0.4φ (0)t [Problema 1(a)] C 1 e com φ (0) < 0. Mostre que, para qualquer d ∈ D, existe um ponto “aceitável” no intervalo (0, d). [Pista:

Recently converted files (publicly available):