PROGRAMAÇÃO NÃO LINEAR – Exame – 05/07/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 método iterativo, para minimizar uma função f, cujo passo é baseado na resolução do seguinte problema de região de confiança:

min_{s̄∈IR^{n}} c_{k} + g_{k}^{⊤}s̄ + \frac{1}{2}s̄^{⊤}H_{k}s̄ s.a ∥D_{k}s̄∥ ≤ Δ_{k},

em que c_{k} = f(x_{k}), g_{k} = ∇f(x_{k}) e H_{k} é uma matriz simétrica de ordem n. Assuma que f : IR^{n} → IR é continuamente diferenciável, que Δ_{k} é um real positivo e que D_{k} é uma matriz n-por-n não singular.

(a) Escreva um problema equivalente a este mas colocado nas variáveis s = D_{k}s̄.

(b) Escreva a condição de decréscimo de Cauchy para o problema de região de confiança da alínea (a).

(c) Sabendo que a aproximação da Hessiana deve ser uniformemente limitada para que o método de região de confiança seja globalmente convergente para pontos estacionários, a que condição é que a sucessão {D_{k}} deveria obedecer para se atingisse este objectivo?

(d) Com base na alínea (b) seria possível provar que lim_{k→+∞} D_{k}^{−1}∇f(x_{k}) = 0. Qual seria a condição a impor a {D_{k}} para que se obtivesse lim_{k→+∞} ∇f(x_{k}) = 0?

2. Considere o problema min_{u∈IR^{nu}} f(y(u), u) em que f : IR^{n_{y}+n_{u}} → IR e c : IR^{n_{y}+n_{u}} → IR^{n_{y}} são funções duas vezes continuamente diferenciáveis e a matriz Jacobiana parcial de c em ordem a y, c_{y}(y, u), é não singular em IR^{n_{y}+n_{u}}. Assuma que y(u) satisfaz c(y(u), u) = 0 para todo o u ∈ IR^{n_{u}}. (Nas aulas foram considerados problemas de controlo óptimo discretizados com esta estrutura. A notação é a mesma.)

(a) Seja {u_{k}} uma sucessão gerada a partir de u_{k+1} = u_{k} + Δu_{k}, em que: (i) ∇_{xx}^{2}L_{k}Δx_{k}+∇_{x}L_{k} é ortogonal ao espaço nulo da matriz Jacobiana de c em (y(u_{k}), u_{k}), com as derivadas do Lagrangeano L a serem calculadas em (y(u_{k}), u_{k}, λ(u_{k})); (ii) Δx_{k} = W (y(u_{k}), u_{k})Δu_{k} com

W (y, u) = ( \begin{matrix}−c_{y}(y, u)^{−1}c_{u}(y, u) \\ I_{n_{u}} \end{matrix} ) .

Diga por que motivo é que uma sucessão assim gerada converge q-quadraticamente para um ponto a satisfazer as condições suficientes de segunda ordem deste problema, se u_{0} estiver suficiente próximo deste ponto. v.s.f.f.

(b) Mostre que a condição de q-superlinearidade de Dennis-Moré se pode escrever na forma

lim_{k→+∞} \frac{∥W_{k}^{⊤} (∇_{xx}^{2}L_{k} − ( \begin{matrix}0 & 0 \\ 0 & B_{k} \end{matrix} )) W_{k}Δu_{k}∥}{∥Δu_{k}∥} = 0,

com W_{k} = W (y(u_{k}), u_{k}).

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

min_{x∈IR^{n}} f(x) s.a h(x) = 0,

em que f : IR^{n} → IR e h : IR^{n} → IR^{m} são funções duas vezes diferenciáveis (m < n).

(a) Mostre que as condições necessárias de primeira ordem para este problema são equivalentes a ∇_{x}L(x, λ) = 0 e ∇_{λ}L(x, λ) = 0, em que L(x, λ) é a função Lagrangeana.

(b) Mostre que a linearização destas condições resulta no sistema de equações lineares:

( \begin{matrix}∇_{xx}^{2}L(x, λ) & ∇h(x) \\ ∇h(x)^{⊤} & 0 \end{matrix} ) ( \begin{matrix}Δx \\ Δλ \end{matrix} ) = − ( \begin{matrix}∇_{x}L(x, λ) \\ h(x) \end{matrix} ) .

(c) Escreva as condições necessárias de primeira ordem do seguinte problema:

min_{Δx∈IR^{n}} ∇f(x)^{⊤}Δx + Δx^{⊤}∇_{xx}^{2}L(x, λ)Δx s.a ∇h(x)^{⊤}Δx + h(x) = 0.

Designe por λ^{+} os multiplicadores destas condições.

(d) Prove que λ^{+} = λ + Δλ, em que λ^{+} são os multiplicadores da alínea (c) e Δλ é o passo da alínea (b).

4. Considere o problema min_{x∈IR^{2}} x_{2} s.a x_{1}^{2} − x_{2} = 0.

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

(b) Seja Q(x; μ) a função de penalização quadrática. Indique uma expressão (em função de μ) para os pontos estacionários desta função.

(c) Seja, agora, L_{A}(x, μ; λ) a função de Lagrangeano aumentado. Repita o processo da alínea (b), calculando os pontos estacionários desta função, como expressões de μ e de λ.

(d) Mostre que se λ for negativo o ponto estacionário em (c) está mais perto da solução do problema do que o ponto estacionário em (b).

(e) Verifique que λ^{+} é negativo se resultar da actualização do método de multiplicadores (com x_{1} = λ = 0 e x_{2} < 0).