PROGRAMAÇÃO NÃO LINEAR – Exame – 10/07/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 duas vezes continuamente diferenciável e considere a mudança de variáveis:

x = Ry , em que R ∈ IR^{n×n} é uma matriz não singular.

Considere a função g : IR^{n} → IR definida por g(y) = f(Ry).

(a) Mostre que o método de Newton é invariante ao escalonamento nas variáveis, ou seja, que as fórmulas x_{k+1} = x_{k} − α_{k}∇^{2}f(x_{k})^{−1}∇f(x_{k}) e y_{k+1} = y_{k} − α_{k}∇^{2}g(y_{k})^{−1} ∇g(y_{k}) são equivalentes.

(b) Mostre que o método da descida máxima é invariante ao escalonamento ortogonal nas variáveis, ou seja, que quando a matriz R é ortogonal é possível provar uma equivalência do género da da alínea anterior (em que a direcção de Newton é substituída pela de descida máxima).

2. Seja f : IR^{n} → IR uma função duas vezes continuamente diferenciável em que ∇^{2}f é contínua à Lipschitz em IR^{n} (com constante L > 0).

Considere um método de região de confiança baseado no modelo quadrático

m_{k}(s) =^{def} f(x_{k}) + ∇f(x_{k})^{⊤}s + 1/2s^{⊤}∇^{2}f(x_{k})s .

A finalidade deste exercício é provar que, para um dado x_{k} tal que ∇f(x_{k}) ≠ 0, é sempre possível encontrar um Δ_{k} tal que

ρ_{k} =^{def} \frac{f(x_{k}) − f(x_{k} + s_{k})}{m_{k}(0) − m_{k}(s_{k})} ≥ η , η ∈ (0, 1/4) .

Sugestão: Analise |ρ_{k}−1| e utilize a propriedade m_{k}(0)−m_{k}(s_{k}) ≥ 1/2a min{Δ_{k}, a/b}, em que a = ∥∇f(x_{k})∥ e b = ∥∇^{2}f(x_{k})∥. Note que x_{k} se supõe constante (ou seja que o passo s_{k} vai sendo rejeitado) à medida que o valor de Δ_{k} diminui, até que a condição ρ_{k} ≥ η seja satisfeita.

v.s.f.f.

3. Considere o seguinte problema

min −b^{⊤}x s.a. x^{⊤}Qx ≤ 1 ,

em que x, b ∈ IR^{n}, b ≠ 0 e Q ∈ IR^{n×n} é uma matriz simétrica e definida positiva.

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

(b) Seja x^{∗} um ponto a verificar as condições necessárias de primeira ordem. Seja λ^{∗} o correspondente multiplicador. i. Mostre que λ^{∗} = \frac{1}{2}(x^{∗})^{⊤}b.

ii. Prove que a função objectivo em x^{∗} vale −\sqrt{b^{⊤}Q^{−1}b}.

(c) Prove, através das condições suficientes de segunda ordem, que um ponto que verifica as condições necessárias de primeira ordem é um minimizante local estrito.

4. Considere o seguinte problema

min f(x_{1}, x_{2}) = \frac{1}{2}(−x_{1}^{2} + x_{2}^{2}) s.a. − x_{1} + 1 = 0 .

(a) Escreva a função Lagrangeana aumentada L_{A}(x, λ; 1/c), em que o parâmetro μ é substituído por 1/c, com c ∈]0, +∞]. (Note que fazer μ → 0^{+} corresponde a fazer c → +∞.)

(b) Escreva o gradiente e a Hessiana de L_{A}(x, λ; 1/c) em ordem a x e conclua que a Hessiana ∇_{xx}^{2}L_{A}(x, λ; 1/c) é mal condicionada quando c → +∞.

(c) Verifique que este problema tem solução óptima (minimizante global) única em (x_{1}^{∗}, x_{2}^{∗}) = (1, 0)^{⊤} (e que o correspondente multiplicador é λ^{∗} = 1).

(d) Mostre que quando c_{k} > 1,

x_{k} = (\frac{c_{k} − λ^{k}}{c_{k} − 1} , 0)^{⊤}

é a solução óptima de min_{x∈IR} L_{A}(x, λ^{k}; 1/c_{k}).

(e) Demonstre que quando c_{k} > 1, a fórmula para actualizar os multiplicadores do método de Lagrangeano aumentado é dada por

λ^{k+1} = −\frac{λ^{k}}{c_{k} − 1} + \frac{c_{k}}{c_{k} − 1}

e que, introduzindo λ^{∗} = 1, se obtém

λ^{k+1} − λ^{∗} = −\frac{λ^{k} − λ^{∗}}{c_{k} − 1} .

O que é que conclui a partir desta expressão relativamente à taxa de convergência de {λ^{k}}?