PROGRAMAÇÃO NÃO LINEAR – Exame – 13/07/00

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

Duração: 2h30m

Atenção: Justifique todas as suas respostas. Podem ser utilizados o livro adoptado e os apontamentos das aulas.

1. Mostre que as condições de Wolfe (CW) são invariantes ao escalonamento. Ou seja, mostre que se f(x) for uma função continuamente diferenciável e as CW forem satisfeitas em x_{k}, então também são satisfeitas em x_{k} para a função αf(x), com α ∈ IR^{+}. Conclua que o método de Newton com procura unidireccional através das CW é invariante ao escalonamento.

2. O método de Newton modificado (com procura unidireccional) e o método de região de confiança estão intimamente relacionados. Dada uma função duas vezes continuamente diferenciável, considere o seguinte modelo quadrático modificado

min_{p∈IR^{n}} m̄_{k}(p) = f(x_{k}) + ∇f(x_{k})^{T} p + \frac{1}{2}p^{T} ∇^{2}f(x_{k})p + \frac{λ_{k}}{2} p^{T} E_{k}p,

em que λ_{k} ∈ IR e E_{k} ∈ IR^{n×n} é uma matriz simétrica e definida positiva.

Calculando o gradiente ∇m̄_{k}(p) e igualando-o ao vector nulo, relacione este modelo quadrático com:

(a) o método de Newton modificado (faça λ_{k} = 1);

(b) o método de região de confiança (faça E_{k} = I).

Sejam agora n = 2 e f(x_{1}, x_{2}) = x_{1}^{4} + x_{2}^{2}.

(c) Mostre que esta função apresenta um único mínimo em (0, 0).

(d) Qual é o número de condição de ∇^{2}f(x_{1}, x_{2}) quando x_{1} < 1/\sqrt{6}? O que acontece ao número de condição quando x_{1} se aproxima de zero?

(e) Que método escolheria para minimizar uma função com este condicionamento? Justifique.

v.s.f.f.

3. Considere uma função f : IR^{n} ⟶ IR e um ponto x^{∗} nas condições do teorema que garante a taxa de convergência local q-quadrática do método de Newton. Considere o método BFGS com um tamanho de passo definido por α_{k} = 1, a gerar uma sucessão {x_{k}} a convergir para x^{∗}.

(a) O que é que pode dizer sobre a convergência da sucessão {B_{k}} das matrizes geradas pelo método BFGS?

(b) O que é que pode dizer sobre a convergência de {x_{k}}?

4. Considere o seguinte problema

min_{x∈IR^{n}} f(x) s.a. Ax = b,

com b ∈ IR^{m}, A ∈ IR^{m×n}, m < n e f uma função duas vezes continuamente diferenciável.

(a) Escreva as condições necessárias de primeira e de segunda ordem deste problema. Diga se é necessário ou não impor uma restrição de qualificação.

(b) Escreva as condições suficientes de segunda ordem deste problema. Seja Z uma matriz cujas colunas geram o espaço nulo de A. Reescreva estas condições recorrendo à matriz Hessiana projectada.

(c) Seja x ∈ IR^{n} tal que Ax = b. Mostre que as condições necessárias de primeira ordem se resumem a Z^{T} ∇f(x) = 0.

(d) Mostre que a linearização de Z^{T} ∇f(x) = 0 e a manutenção da admissibilidade dos iterandos conduz ao método

x_{k+1} = x_{k} + Zu_{k}, Z^{T} ∇^{2}f(x_{k})Zu_{k} = −Z^{T} ∇f(x_{k}),

com Ax_{0} = b.