Programação Não Linear

Ano Lectivo 2001/02

Trabalho 2: Métodos de procura unidireccional.

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

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

2. Considere um método de procura unidireccional da forma x_{k+1} = x_{k}+α_{k}p_{k} com α_{k} a satisfazer as condições de Wolfe e

p_{k} = − [ 0 ; ⋮ ; 0 ; \frac{∂f}{∂x_{i_{k}}} (x_{k}) ; 0 ; ⋮ ; 0 ] ,

em que i_{k} é um índice para o qual |\frac{∂f}{∂x_{j}} (x_{k})| assume o maior valor em j ∈ \{1, …, n\}. Suponha que a função f : N ⊂ IR^{n} → IR é continuamente diferenciável no aberto N e que este contém L(x_{0}). Suponha ainda que f é limitada inferiormente em L(x_{0}) e que ∇f é contínua à Lipschitz em N.

(a) Mostre que p_{k} é uma direcção de descida se ∇f(x_{k}) ≠ 0 e conclua que estamos nas condições de assegurar convergência global.

(b) Prove que todo o ponto de acumulação de {x_{k}} é estacionário.

3. Nas condições do Teorema 3.5, prove que os limites (3.30) e (3.31) são equivalentes.

4. Seja {x_{k}} uma sucessão a convergir q-superlinearmente para x^{∗}. Demonstre que

lim_{k⟶+∞} \frac{∥x_{k+1} − x_{k}∥}{∥x_{k} − x^{∗}∥} = 1.

Sugestão: Considere o “triângulo” de vértices x_{k}, x_{k+1} e x^{∗} e utilize a desigualdade triangular.

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