Programação Não Linear

Ano Lectivo 2001/02

Trabalho 3: Métodos de região de confiança

Data de recepção: 05/04/2002; Data de entrega: 19/04/2002

Considere o problema de região de confiança PRC(Δ):

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.

O Teorema 4.3 diz que p^{∗} é minimizante \underline{global} do PRC(Δ) \underline{se e só se} existir um parâmetro λ ≥ 0 tal que

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

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

B + λI é semi-definida positiva.

Se B + λI for não singular (neste caso, definida positiva) então o minimizante global é único.

Prova-se também que o problema PRC(Δ) não tem nenhum minimizante p^{∗} com ∥p^{∗}∥ = Δ se e só se B for definida positiva e ∥B^{−1}g∥ < Δ.

As condições necessárias do Teorema 4.3 serão demonstradas quando forem introduzidas as condições necessárias de primeira e de segunda ordem gerais para problemas de optimização não linear com restrições. Chama-se a atenção para o facto das condições do Teorema 4.3 serem também suficientes, mesmo num contexto não convexo, uma vez que nada é assumido sobre o sinal dos valores próprios de B.

1. Caracterize p^{∗}.

2. Suponha que B + λI é sempre não singular para todo o λ ≥ 0. Prove que

lim_{λ→+∞} p(λ) = 0 e

lim_{λ→+∞} \frac{d^{⊤}p(λ)}{∥p(λ)∥} = 0 quando d^{⊤}g = 0 .

Represente geometricamente o arco descrito por p(λ) de 0 a +∞.

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.