Programação Não Linear

Ano Lectivo 2003/04

Trabalho 4: Métodos de quasi-Newton

Data de recepção: 01/04/2004; Data de entrega: 20/04/2004

1. Considere a actualização do método de quasi-Newton PSB (Powell-symmetric-Broyden):

B_{k+1} = B_{k} + \frac{(y_{k} − B_{k}s_{k})s_{k}^{⊤} + s_{k}(y_{k} − B_{k}s_{k})^{⊤}}{s_{k}^{⊤}s_{k}} − \frac{(y_{k} − B_{k}s_{k})^{⊤}s_{k}}{(s_{k}^{⊤}s_{k})^{2}} s_{k}s_{k}^{⊤} .

Prove que B_{k+1} é a solução óptima única de

min_{B∈IR^{n×n}} ∥B − B_{k}∥_{F} s.a. B = B^{⊤} e Bs_{k} = y_{k} ,

através dos seguintes passos:

(a) Em primeiro lugar, prove que B_{k+1} é simétrica e que satisfaz a equação da secante Bs_{k} = y_{k}.

(b) De seguida, mostre que

∥(B_{k+1} − B_{k})r∥_{2} ≤ ∥(B − B_{k})r∥_{2} ,

quaisquer que sejam a matriz B simétrica a satisfazer a equação da secante e o vector r ∈ IR^{n} a verificar r^{⊤}s_{k} = 0. Note que

∥\frac{s_{k}s_{k}^{⊤}}{s_{k}^{⊤}s_{k}} ∥_{F} = 1

e que ∥Av∥_{2} ≤ ∥A∥_{F} ∥v∥_{2}.

(c) Mostre, depois, que

∥B_{k+1} − B_{k}∥_{F}^{2} ≤ ∥B − B_{k}∥_{F}^{2} ,

qualquer que seja a matriz B simétrica a satisfazer a equação da secante. Demonstre, primeiro, as propriedades:

∥A∥_{F}^{2} =^{def} ∑_{i,j=1}^{n} a_{ij}^{2} = ∑_{j=1}^{n} ∥Ae_{j}∥_{2}^{2} = tr(A^{⊤}A) e ∥AQ∥_{F}^{2} = ∥A∥_{F}^{2} ,

em que Q representa uma matriz ortogonal em IR^{n×n}.

Em caso de omissão utilizam-se as convenções e notações do Livro J. Nocedal e S. J. Wright, Numerical Optimization, Springer, 1999.

Exercícios de Matlab

Os códigos mencionados em baixo foram escritos pelo professor da disciplina, em Matlab, e com uma finalidade pedagógica no âmbito da disciplina. Para cada exercício, entregue as funções que forem pedidas e o diário da sua sessão de Matlab. O diário pode ser gravado num ficheiro através do comando diary. Utilize format compact para poupar espaço.

1. Leia, tente compreender e execute os códigos escritos em Matlab para a minimização da função do exercício 4.3 do livro Nocedal e Wright). Os códigos estão disponíveis em

         http://www.mat.uc.pt/∼lnv/pnl/e4ponto3.tar.gz

(a) Compare o método de Newton e o método BFGS, ambos implementados no código, para n = 10, n = 100 e n = 200 e explique os resultados obtidos.

(b) Para n = 10, corra o método BFGS e o método BFGS com procura unidireccional, com e sem a alteração (8.20). Explique os resultados obtidos.