Programação Não Linear

Ano Lectivo 2003/04

Trabalho 2: Métodos de procura unidireccional.

Data de recepção: 04/03/2004; Data de entrega: 23/03/2004 Exercícios sobre métodos de procura unidireccional

1. Considere as hipóteses do Teorema 3.2 (convergência global para procura unidireccional).

(a) Mostre que se existir δ ∈ (0, 1] tal que cos θ_{k} ≥ δ para todo o k então {∇f(x_{k})} converge para zero.

(b) O que poderá dizer sobre os possíveis pontos de acumulação de {x_{k}}?

(c) Se a condição cos θ_{k} ≥ δ se verificar apenas para uma subsucessão, {k_{j}}, o que poderá dizer sobre os possíveis pontos de acumulação de {x_{k}}?

(d) O método da descida máxima, com procura unidireccional a satisfazer as condições de Wolfe, é globalmente convergente nas condições deste teorema? Porquê?

(e) Faça, agora, p_{k} = −B_{k}^{−1}∇f(x_{k}), com B_{k} simétrica e definida positiva para todo o k. Suponha que existe M ≥ 1 tal que κ(B_{k}) ≤ M para todo o k. Conclua que tal método, com procura unidireccional a satisfazer as condições de Wolfe, é globalmente convergente nas condições deste teorema.

2. Descreva graficamente uma situação que evidencie a possível não verificação das CW quando 0 < c_{2} < c_{1} < 1.

3. Seja x^{∗} um ponto de IR^{n} e f uma função de IR^{n} para IR tais que a Hessiana de f é contínua à Lipschitz num aberto contendo x^{∗} e definida positiva em x^{∗} (n ∈ IN). Seja {x_{k}} uma sucessão de IR^{n} a convergir para x^{∗}, gerada da seguinte forma:

x_{k+1} = x_{k} + p_{k} com ∇^{2}f(x_{k})p_{k} = −∇f(x_{k}) + r_{k} ,

em que r_{k} é um vector não nulo de IR^{n} e p_{k} ≠ 0 para todo o k.

(a) Mostre que p_{k} satisfaz:

(∇^{2}f(x_{k}) − \frac{r_{k}p_{k}^{⊤}}{p_{k}^{⊤}p_{k}} ) p_{k} = −∇f(x_{k}) .

(b) Recorrendo ao resultado da alínea anterior, prove que {x_{k}} converge q-superlinearmente para x^{∗} se e só se

lim_{k→+∞} \frac{∥r_{k}∥}{∥p_{k}∥} = 0 .

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 de Rosenbrock (ver os exercícios 2.1 e 3.1 do livro Nocedal e Wright). Comente os resultados para os dois pontos iniciais dados em Rosenbrock.m. Os códigos e instruções para os instalar estão disponíveis em

         http://www.mat.uc.pt/∼lnv/pnl/Rosenbrock.html