PROGRAMAÇÃO NÃO LINEAR – Exame – 12/06/01

DEPARTAMENTO DE MATEMÁTICA DA F.C.T.U.C.

Duração: 2h30m

Atenção: Justifique todas as suas respostas. Podem-se consultar o livro adoptado e os apontamentos das aulas.

1. Seja f : IR^{n} → IR uma função continuamente diferenciável. A condição de decréscimo suficiente em métodos de procura unidireccional, dada por

f(x_{k} + α_{k}p_{k}) ≤ f(x_{k}) + c_{1}α_{k}∇f(x_{k})^{⊤}p_{k} , c_{1} ∈ (0, 1),

desempenha um papel “semelhante” à condição

\frac{f(x_{k}) − f(x_{k} + s_{k})}{m_{k}(0) − m_{k}(s_{k})} ≥ η , η ∈ (0, 1/4),

dos métodos de região de confiança, em que m_{k}(s) = f(x_{k}) + ∇f(x_{k})^{⊤}s + 1/2s^{⊤}B_{k}s e B_{k} ∈ IR^{n×n} é simétrica. Mostre que esta afirmação faz sentido, escolhendo, para o efeito, B_{k} = 0 em m_{k}(s), e associando s_{k} a α_{k}p_{k}.

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.

v.s.f.f.

3. Considere o seguinte problema

min f(x) s.a. a_{i} ≤ x_{i} ≤ b_{i} , i = 1, …, n ,

em que x, a, b ∈ IR^{n} e f é uma função duas vezes continuamente diferenciável em IR^{n}.

(a) Escreva, no contexto deste problema, as condições necessárias de primeira e de segunda ordem, e comente a necessidade de impôr uma qualificação de restrições.

(b) Escreva, no contexto deste problema, as condições suficientes de segunda ordem.

(c) No caso em que existe complementaridade estrita, reescreva a parte de segunda ordem destas condições suficientes recorrendo a uma submatriz da Hessiana de f.

(d) Sejam, agora, n = 2, a = (0, 0)^{⊤}, b = (1, 1)^{⊤} e f(x_{1}, x_{2}) = −x_{1}x_{2} + x_{2}. Verifique, analiticamente e geometricamente, se são válidas em (x_{1}^{∗}, x_{2}^{∗}) = (1, 1)^{⊤} as condições necessárias de primeira ordem. Verifique também, para este ponto (x_{1}^{∗}, x_{2}^{∗}), a validade das condições de segunda ordem.

4. Considere a fórmula de actualização do método BFGS que gera as aproximações simétricas {B_{k}} em IR^{n×n} das matrizes Hessianas, dada por

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

(a) Mostre que se B_{k} é simétrica então B_{k+1} também é simétrica.

(b) Mostre que B_{k+1} satisfaz a equação da secante.

(c) Mostre que se B_{k} é definida positiva então B_{k+1} também é definida positiva. Sugestão: Considere a decomposição de Cholesky B_{k} = L_{k}L_{k}^{⊤} e faça a = L_{k}^{⊤}z e b = L_{k}^{⊤}s_{k} para um dado vector z ∈ IR^{n} e prove que

z^{⊤} (B_{k} − \frac{1}{s_{k}^{⊤}B_{k}s_{k}} B_{k}s_{k}s_{k}^{⊤}B_{k}) z ≥ 0 ,

utilizando, para o efeito, a desigualdade de Cauchy-Schwarz. De seguida considere a outra parcela, \frac{1}{y_{k}^{⊤}s_{k}} y_{k}y_{k}^{⊤}.