Programação Não Linear

Ano Lectivo 2001/02

Trabalho 4: Métodos de quasi-Newton

Data de recepção: 19/04/2002; Data de entrega: 10/05/2002

1. Considere a actualização do método de quasi-Newton BFGS, dada por

B_{k+1} = B_{k} − \frac{B_{k}s_{k}s_{k}^{⊤}B_{k}}{s_{k}^{⊤}B_{k}s_{k}} + \frac{y_{k}y_{k}^{⊤}}{y_{k}^{⊤}s_{k}} ,

em que B_{k} é uma matriz simétrica e definida positiva e y_{k}^{⊤}s_{k} > 0.

(a) Prove que B_{k+1} é simétrica e definida positiva e satisfaz a equação da secante Bs_{k} = y_{k}.

(b) Nesta alínea pretende-se chegar à actualização BFGS por um processo alternativo ao da aula.

Considere, para o efeito, a factorização de Cholesky de B_{k}, dada por B_{k} = L_{k}L_{k}^{⊤}. Considere, também, a equação da secante Bs_{k} = y_{k} escrita na forma

Lv_{k} = y_{k} e L^{⊤}s_{k} = v_{k} ,

em que v_{k} é um vector auxiliar.

i. Determine L = L_{k+1}, em função de L_{k}, y_{k} e v_{k} de tal forma que a equação Lv_{k} = y_{k}

seja satisfeita e que L_{k+1} difira de L_{k} numa matriz de característica 1. ii. Utilize a expressão calculada na alínea anterior e L^{⊤}s_{k} = v_{k} com L = L_{k+1} para

concluir que v_{k} = α_{k}L_{k}^{⊤}s_{k}, em que α_{k} é um escalar real. iii. Determine α_{k}. iv. Prove que L_{k+1} assim determinada é não singular. v. Confirme que obteve a actualização BFGS, ou seja que B_{k+1} = L_{k+1}L_{k+1}^{⊤}.

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/∼lvicente/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.