PROGRAMAÇÃO NÃO LINEAR – Exame – 20/06/00

DEPARTAMENTO DE MATEMÁTICA DA F.C.T.U.C.

Duração: 2h30m

Atenção: Justifique todas as suas respostas. Podem ser utilizados o livro adoptado e os apontamentos das aulas.

1. Considere o sistema de equações não lineares:

r(x) = 0

em que a função r : IR^{n} ⟶ IR^{n} é continuamente diferenciável. Seja J(x) a sua matriz Jacobiana.

(a) Mostre que a direcção −J(x)^{−1}r(x) é de descida para a função

f(x) = \frac{1}{2}∥r(x)∥_{2}^{2} = \frac{1}{2}r(x)^{T} r(x).

(b) Seja {x_{k}} a sucessão definida por

x_{k+1} = x_{k} + p_{k}, em que J(x_{k})p_{k} = −r(x_{k}).

Assuma que {x_{k}} converge para x^{∗} tal que J(x^{∗}) é não singular e que J é contínua à Lipschitz num aberto de IR^{n} contendo x^{∗}. Demonstre que

i. r(x^{∗}) = 0; ii. a taxa de convergência local é q-quadrática.

(Utilize o facto de r(x_{k}) − r(x^{∗}) = ∫_{0}^{1} J(x^{∗} + t(x_{k} − x^{∗}))(x_{k} − x^{∗}) dt.)

(c) Considere agora o método quasi-Newton (designado por método de Broyden) definido iterativamente por

\begin{aligned}x_{k+1} & = & x_{k} − A_{k}^{−1}r(x_{k}), \\ s_{k} & = & x_{k+1} − x_{k}, \\ y_{k} & = & r(x_{k+1}) − r(x_{k}), \\ A_{k+1} & = & A_{k} + \frac{(y_{k}−A_{k}s_{k})s_{k}^{T}}{s_{k}^{T} s_{k}} , \end{aligned}

k = 0, 1, 2, … (em que A_{0} ∈ IR^{n×n} é uma matriz não singular e x_{0} ∈ IR).

i. Mostre que A_{k+1} satisfaz a equação de secante As_{k} = y_{k}. ii. Demonstre que A_{k+1} é a solução óptima do problema

min_{A∈IR^{n×n}} ∥A − A_{k}∥_{2}^{2} s.a. As_{k} = y_{k}.

iii. Mostre que se A_{k+1} satisfaz a equação de secante e A_{k+1} = A_{k} + u_{k}v_{k}^{T} então

A_{k+1} = A_{k} + \frac{(y_{k} − A_{k}s_{k})v_{k}^{T}}{v_{k}^{T} s_{k}} .

(Conclua então que o método de Broyden resulta de v_{k} = s_{k}.)

2. Considere o problema de região de confiança

min_{p∈IR^{n}} g^{T} p + \frac{1}{2}p^{T} Bp s.a. ∥p∥_{2} ≤ Δ,

com g ∈ IR^{n}, B ∈ IR^{n×n}, B = B^{T} e Δ > 0.

(a) Escreva as condições necessárias de primeira e de segunda ordem deste problema. Atenção: Reescreva primeiro ∥p∥_{2} ≤ Δ na forma Δ^{2} − ∥p∥_{2}^{2} ≥ 0 e designe por λ o multiplicador associado a esta restrição. Indique em que condições é que a hipótese LICQ (independência linear dos gradientes das restrições activas) é satisfeita.

(b) Reescreva as condições determinadas na alínea anterior de forma a poder comparálas com as condições que caracterizam a solução óptima do PRC.

(c) Sejam agora n = 3,

B = ( \begin{matrix}1 & 0 & 0 \\ 0 & −2 & 0 \\ 0 & 0 & 3 \end{matrix} ) e g = ( \begin{matrix}1 \\ g_{2} \\ 1 \end{matrix} ) .

i. Escreva por extenso a função racional ∥p(λ)∥_{2}^{2} = ∥ − (B + λI)^{−1}g∥_{2}^{2}. ii. Considere g_{2} = 1 e mostre, geometricamente, como pode ser obtida a solução

óptima deste PRC. iii. Considere g_{2} = 0 e indique o valor de Δ que separa o caso fácil do difícil.

3. Considere o problema

min −x^{2} s.a. 1 − x^{2} ≥ 0.

(a) Mostre que a função de barreira logarítmica P (x; μ) tem um minimizante x = 0 se μ > 1 e dois minimizantes x = ±\sqrt{1 − μ} se μ < 1. Que tipo de ponto é x = 0 quando μ < 1?

(b) Seja {μ_{k}} uma sucessão de parâmetros de barreira menores do que um a convergir para zero. Seja ainda x_{k} = (−1)^{k}\sqrt{1 − μ_{k}} uma sucessão de minimizantes de P (x; μ_{k}). i. Verifique que as subsucessões {x_{2k+1}} e {x_{2k}} convergem para pontos de acu-

mulação diferentes, ambos soluções do problema original. ii. Acha que o método da barreira logarítmica oscilaria da mesma forma? Porquê?

Qual é a componente deste método que impediria esse comportamento?