Programação Não Linear

Ano Lectivo 2000/01

Trabalho 5: Teoria da optimização não linear com restrições

Data de recepção: 24/05/2001; Data de entrega: 31/05/2001

1. Considere o problema de região de confiança:

min_{p∈IR^{n}} m(p) =^{def} f + g^{⊤}p + \frac{1}{2}p^{⊤}Bp s.a. ∥p∥ ≤ Δ ,

em que Δ é um real positivo, f é um real, g é um vector em IR^{n} e B é uma matriz n × n real e simétrica.

Mostre que se p^{∗} for minimizante local do problema de região de confiança então existe um parâmetro λ^{∗} ≥ 0 tal que

(B + λ^{∗}I)p^{∗} = −g ,

λ^{∗}(Δ − ∥p^{∗}∥) = 0 e

B + λ^{∗}I é semi-definida positiva.

2. 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 impôr uma qualificação de restrições.)

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

(c) Seja Z uma matriz cujas colunas geram o espaço nulo de A. 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) Reescreva as condições de segunda ordem recorrendo à matriz Hessiana projectada.

Em caso de omissão utilizam-se as convenções e notações do Livro J. Nocedal e S. J. Wright, Numerical Optimization, Springer, 1999.