Programação Não Linear

Ano Lectivo 2000/01

Trabalho 2: Métodos de procura unidireccional

Data de recepção: 12/03/2001; Data de entrega: 26/03/2001 Exercícios sobre métodos de procura unidireccional

1. (a) Mostre que o método de Newton é invariante ao escalonamento de f, ou seja que o passo de Newton não se altera quando se substitui f(x) por αf(x), com α ∈ IR^{+}.

(b) Mostre que as condições de Wolfe (CW) são invariantes ao escalonamento de f. Conclua que o método de Newton com procura unidireccional através das CW é invariante ao escalonamento.

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. Demonstre, para uma função quadrática estritamente convexa, que o passo de Newton satisfaz as CW com c_{1} em (0, 1/2] e c_{2} real positivo qualquer.

4. Seja {B_{k}} uma sucessão de matrizes simétricas e definidas positivas. Prove que se o número de condição de B_{k} for limitado uniformemente por M > 0, ou seja se

∥B_{k}∥∥B_{k}^{−1}∥ ≤ M para todo o k,

então

cos(θ_{k}) =^{def} \frac{−∇f(x_{k})^{⊤}p_{k}}{∥∇f(x_{k})∥∥p_{k}∥} ≥ \frac{1}{M} ,

em que p_{k} = −B_{k}^{−1}∇f(x_{k}).

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