PROGRAMAÇÃO NÃO LINEAR – Exame – 09/07/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. Uma técnica de globalização deve deixar o passo de Newton ser aceite perto de um ponto a satisfazer as condições que garantem a taxa de convergência q-quadrática do método de Newton. Descreva os resultados que indicam que este comportamento acontece, de facto, nas técnicas de procura unidireccional e de região de confiança.

2. Seja x^{∗} um ponto de IR^{n} e f uma função de IR^{n} para IR tais que a Hessiana de f é contínua à Lipschitz num aberto contendo x^{∗} e definida positiva em x^{∗} (n ∈ IN). Seja {x_{k}} uma sucessão de IR^{n} a convergir para x^{∗}, gerada da seguinte forma:

x_{k+1} = x_{k} + p_{k} com ∇^{2}f(x_{k})p_{k} = −∇f(x_{k}) + r_{k} ,

em que r_{k} é um vector não nulo de IR^{n} e p_{k} ≠ 0 para todo o inteiro não negativo k. Assuma, para facilitar a apresentação, que a Hessiana de f é definida positiva em todos os pontos da sucessão {x_{k}}.

(a) Indique uma condição suficiente para que p_{k} seja uma direcção de descida.

(b) Considere a função objectivo f(x_{1}, x_{2}) = 1/2(x_{1}^{2} +x_{2}^{2}) e o ponto x_{0} = (1, 1)^{⊤}. Seja r_{0} = (−2, 1)^{⊤}. Com base no sinal de ∇f(x_{0})^{⊤}r_{0}, diga por que é que p_{0} é uma direcção de descida.

(c) Mostre que p_{k} satisfaz:

(∇^{2}f(x_{k}) − \frac{r_{k}p_{k}^{⊤}}{p_{k}^{⊤}p_{k}} ) p_{k} = −∇f(x_{k}) .

(d) Recorrendo ao resultado da alínea anterior, prove que {x_{k}} converge q-superlinearmente para x^{∗} se e só se

lim_{k→+∞} \frac{∥r_{k}∥}{∥p_{k}∥} = 0 .

v.s.f.f.

3. Considere o seguinte problema de regiões de confiança:

min f + g^{⊤}s + \frac{1}{2}s^{⊤}Bs s.a. ∥s∥_{2} ≤ Δ_{1} e ∥s − a∥_{2} ≤ Δ_{2} ,

em que g e a são vectores de IR^{n}, B é uma matriz simétrica n × n, f é um real e Δ_{1} e Δ_{2} são reais positivos (n ∈ IN). Assuma que ∥a∥_{2} ≤ Δ_{1}. Mostre que um minimizante local s deste problema para o qual ∥s∥_{2} < Δ_{1} satisfaz

(B + λ_{2}I) s = −g + λ_{2}a

em que λ_{2} é um real não negativo.

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

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

(a) Resolva o problema geometricamente, confirmando, depois, que no minimizante obtido, o simétrico do gradiente da função objectivo pertence ao cone normal.

(b) Escreva as condições necessárias de primeira ordem no ponto obtido anteriormente, indicando qual a qualificação de restrições que é verificada.

(c) Será possível encontrar um vector de multiplicadores tal que a condição de complementaridade estrita é verificada? E se a função objectivo fosse \frac{1}{2}(x_{1} − 2)^{2} + \frac{1}{2}(x_{2} − 2)^{2}?

(d) Escreva a função de barreira logarítmica para este problema. Como é que encontraria, numericamente, um ponto inicial para o método da barreira logarítmica?