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

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. Considere o teorema da convergência local do método de Newton para a minimização de uma função f : IR^{n} → IR com Hessiana contínua à Lipschitz num aberto N de IR^{n} contendo o ponto x^{∗}. Existem duas constantes, relacionadas com a função f, que influenciam a região de convergência local q-quadrática e a correspondente desigualdade na norma do erro absoluto de uma iteração para a seguinte. Quais são essas constantes e como é que essa influência é exercida?

2. Seja f : IR^{n} → IR uma função duas vezes continuamente diferenciável em IR^{n}. Dado um ponto y ∈ IR^{n} em que a matriz Hessiana é não singular, considere a direcção d(y) definida por

d(y) = −∇f(y) − ∇^{2}f(y)^{−1}∇f(y) .

(a) Mostre que d(y) é uma direcção de descida quando ∇^{2}f(y) é definida positiva e ∇f(y) ≠ 0.

(b) Mostre que d(y) é uma direcção de descida se ∥∇^{2}f(y)^{−1}∥_{2} < 1 e ∇f(y) ≠ 0.

(c) Considere, agora, as funções reais de duas variáveis reais f(x_{1}, x_{2}) = x_{1}^{4} + 6x_{2}^{2} + 4x_{1}x_{2} e f(x_{1}, x_{2}) = x_{1}^{4} + 6x_{2}^{2}. Seja y = (1, 1)^{⊤}. Calculando apenas ∇^{2}f(y) e os seus valores próprios, mostre que d(y) é, para ambas as funções, uma direcção de descida.

(d) Em que outras situações, para além das descritas nas alíneas a e b, é que d(y) é uma direcção de descida?

v.s.f.f.

3. Considere um problema de programação não linear com |I| restrições de desigualdade

min f(x) s.a c_{i}(x) ≥ 0, i ∈ I ,

em que todas as funções envolvidas são continuamente diferenciáveis de IR^{n} para IR. Considere uma sucessão de pontos {x_{k}} em IR^{n}, a convergir para um ponto admissível x^{∗}, em que x_{k} satisfaz

∇f(x_{k}) − ∑_{i∈A(x_{k})} λ_{i}^{k}∇c_{i}(x_{k}) = 0, λ_{i}^{k} ≥ 0, i ∈ A(x_{k}), λ_{i}^{k} = 0, i ∉ A(x_{k}) ,

para um dado λ^{k} ∈ IR^{|I|}.

(a) Mostre que quando o conjunto {∇c_{i}(x^{∗}), i ∈ A(x^{∗})} é linearmente independente, ou seja, que quando a qualificação de restrições LICQ é satisfeita, o ponto x^{∗} satisfaz as condições necessárias de primeira ordem.

(b) O que poderá dizer sobre x^{∗} quando apenas se sabe ser verdadeira a qualificação de restrições de Mangasarian–Fromovitz (MFCQ)?

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

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

(a) Identifique, geometricamente, a solução óptima do problema e confirme que esse minimizante global satisfaz as condições suficientes de segunda ordem.

(b) Repare, agora, no seguinte problema em x_{1}, x_{2}, e s:

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

em que μ é um parâmetro real positivo.

i. Escreva as condições necessárias de primeira ordem para este problema quando

x_{1} e s assumem valores positivos. ii. Reescreva estas condições eliminando o multiplicador associado à restrição

x_{1} + x_{2} − s = 1. Identifique, depois, aproximações para os multiplicadores associados às restrições x_{1} ≥ 0 e x_{1} + x_{2} ≥ 1 do problema original.