PROGRAMAÇÃO NÃO LINEAR – Exame – 09/06/04

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

Duração: 2h30m

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

1. Considere um problema de optimização não linear sem restrições da forma min_{x∈IR^{n}} f(x), em que f é uma função continuamente diferenciável de IR^{n} para IR, e um método a gerar uma sucessão de pontos {x_{k}} através da fórmula

x_{k+1} = x_{k} − α_{k}∇f(x_{k}),

com α_{k} a satisfazer a condição f(x_{k+1})−f(x_{k}) ≤ −c_{1}α_{k}∥∇f(x_{k})∥^{2} (em que c_{1} ∈ (0, 1)).

(a) Identifique esta condição.

(b) Assuma, agora, que f é limitada inferiormente em L(x_{0}). Prove que lim_{k→+∞} ∇f(x_{k}) = 0 se α_{k} ≥ α_{min} > 0 para todo o k.

(c) Que outra condição asseguraria um comportamento do tipo α_{k} ≥ α_{min} > 0 para todo o k?

2. Considere, novamente, um problema de optimização não linear sem restrições da forma min_{x∈IR^{n}} f(x), com f continuamente diferenciável de IR^{n} para IR.

(a) No contexto dos métodos de quasi-Newton, mostre que

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

satisfaz a equação de secante

s_{k}^{⊤}Bs_{k} = y_{k}^{⊤}s_{k} (B ∈ IR^{n×n})

com s_{k} = x_{k+1} − x_{k} e y_{k} = ∇f(x_{k+1}) − ∇f(x_{k}).

(b) Considere um método, que se assume bem definido, da forma x_{k+1} = x_{k} + α_{k}p_{k} com p_{k} = −B_{k}^{−1}∇f(x_{k}), B_{0} = I e α_{k} a satisfazer as condições de Wolfe. Qual é o método que estudou para este problema que mais se assemelha a este?

(c) Com a escolha B_{0} = I, escreva B_{1} (assumindo x_{1} ≠ x_{0}). Mostre que B_{1} é uma matriz definida positiva se f for estritamente convexa.

v.s.f.f.

3. Considere o problema de programação não linear

min_{x∈IR^{n}} f(x) s.a x ≥ 0

com f uma função duas vezes continuamente diferenciável de IR^{n} para IR.

(a) Escreva a função de barreira logarítmica P (x; μ) para este problema e os seus gradiente ∇_{x}P (x; μ) e Hessiana ∇_{xx}^{2}P (x; μ) em ordem a x. Identifique o mau condicionamento do sistema que determina o passo de Newton, ∇_{xx}^{2}P (x; μ)Δx = −∇_{x}P (x; μ), quando uma das componentes de x se aproxima de zero (ou seja, quando x se aproxima da fronteira de {x ∈ IR^{n} : x > 0}).

(b) Seja D a matriz diagonal cujos elementos diagonais são as componentes de x. Multiplique a equação da alínea anterior por D e faça a mudança de variável Δx = DΔ̂x (assumindo que todas as componentes de x são positivas). Verifique que o novo sistema apresenta uma matriz simétrica e que o mau condicionamento mencionado na alínea anterior já não se manifesta.

(c) Mostre que num ponto x para o qual x ≥ 0 e ∇f(x) ≥ 0, as condições necessárias de primeira ordem para este problema se resumem a D∇f(x) = 0.

4. Considere o seguinte problema de optimização não linear:

min_{x∈IR^{2}} \frac{1}{2}(x_{1} + 1)^{2} + \frac{1}{2}(x_{2} + 1)^{2} s.a e^{x_{1}} − x_{2} − 2 ≥ 0, e^{x_{1}} + x_{2} ≥ 0.

(a) À luz dos teoremas de existência e unicidade de minimizantes, o que poderia afirmar sobre este problema?

(b) Mostre que o ponto (0, −1)^{⊤} satisfaz as condições necessárias de primeira ordem e escreva o conjunto F e o cone F_{1} para este ponto.

(c) Mostre que o ponto (0, −1)^{⊤} satisfaz as condições suficientes de segunda ordem.

(d) Prove que o ponto (0, −1)^{⊤} é o minimizante global. (Sugestão: averigúe que não existe mais nenhum ponto a satisfazer as condições necessárias de primeira ordem.)