Programação Não Linear

Ano Lectivo 2003/04

Trabalho 1: Teoria e fundamentos numéricos de optimização não linear sem restrições

Data de recepção: 17/02/2004; Data de entrega: 02/03/2004 Exercícios sobre teoria e fundamentos numéricos de optimização não linear sem restrições

1. Seja f(x) = \frac{1}{2}∥x∥^{2} = \frac{1}{2}x^{⊤}x, x ∈ IR^{n}, e S = \{x ∈ IR^{n} : Ax = b\} o conjunto das soluções de um sistema de equações lineares possível e indeterminado com A ∈ IR^{m×n} e b ∈ IR^{m} (n e m são inteiros positivos).

(a) Prove que S é um conjunto convexo e fechado.

(b) Mostre que f é contínua e uniformemente convexa em S.

(c) Caracterize a existência e unicidade de minimizantes (de f em S) com base apenas nos resultados dados na aula teórica.

2. Seja f : IR^{n} → IR uma função duas vezes continuamente diferenciável em IR^{n}. Dado um ponto y ∈ IR^{n} em que a matriz Hessiana é não singular, considere a direcção d(y) definida por

d(y) = −∇f(y) − ∇^{2}f(y)^{−1}∇f(y) .

(a) Mostre que d(y) é uma direcção de descida quando ∇^{2}f(y) é definida positiva e ∇f(y) ≠ 0.

(b) Mostre que d(y) é uma direcção de descida se ∥∇^{2}f(y)^{−1}∥_{2} < 1 e ∇f(y) ≠ 0.

(c) Considere, agora, as funções reais de duas variáveis reais f(x_{1}, x_{2}) = x_{1}^{4} + 6x_{2}^{2} + 4x_{1}x_{2} e f(x_{1}, x_{2}) = x_{1}^{4} + 6x_{2}^{2}. Seja y = (1, 1)^{⊤}. Calculando apenas ∇^{2}f(y) e os seus valores próprios, mostre que d(y) é, para ambas as funções, uma direcção de descida.

(d) Em que outras situações, para além das descritas nas alíneas a e b, é que d(y) é uma direcção de descida?

3. Mostre que a sucessão {1 + 10^{−k}} converge para 1 q-linearmente.

4. Prove que a sucessão {1 + (0.5)^{2^{k}}} apresenta uma taxa de convergência q-quadrática para 1.

5. Estude a taxa de convergência da sucessão {x_{k}} definida por (0.5)^{2^{k}} se k for par e x_{k−1}/k se k for ímpar.

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.

Exercícios de iniciação ao Matlab

Estes exercícios têm por objectivo iniciar a utilização do pacote de software Matlab, desenvolvido para Cálculo Científico e Análise e Álgebra Linear Numéricas.

O Matlab é uma marca registada pela The MathWorks, Inc. (endereço de correio electrónico

info@mathworks.com e endereço na Web http://www.mathworks.com). O comando help pode ser

utilizado para descobrir o modo de utilização de qualquer outro comando. Executando o comando doc tem-se acesso a uma página contendo o manual de utilização. Para cada exercício, entregue as funções que forem pedidas e o diário da sua sessão de Matlab. O diário pode ser gravado num ficheiro através do comando diary. Utilize format compact para poupar espaço. Utilize também format long, a fim de o conhecer.

1. Execute os seguintes comandos em Matlab:

     x     = (-128:128)'/128;
     A     = [x.^0 x.^1 x.^2 x.^3];
     [Q,R] = qr(A,0);
     scale = Q(257,:);
     Q     = Q*diag(1 ./scale);
     plot(Q)

(a) Explique o que é que a execução de cada comando está a realizar.

(b) Trace na mesma figura e nos mesmos 257 pontos do eixo das abcissas os primeiros quatro polinómios de Legendre P_{0}(x) = 1, P_{1}(x) = x, P_{2}(x) = \frac{3}{2}x^{2} − \frac{1}{2} e P_{3}(x) = \frac{5}{2}x^{3} − \frac{3}{2}x.

(c) Calcule as normas ℓ_{2} dos vectores erro obtidos subtraindo as quatro colunas de Q aos respectivos quatro vectores utilizados em (b). Como é que está feita a distribuição do erro ao longo das 257 componentes de cada vector erro?

2. Nas alíneas a e b explique o raciocínio matemático que sustenta a correspondente implementação.

(a) Escreva uma função que, dada a matriz H simétrica, devolve uma matriz simétrica E para a qual o menor valor próprio de H + E não é inferior a 10^{−4}.

(b) Escreva uma função que, dada a matriz H simétrica, devolve uma matriz simétrica E para a qual H + E é definida positiva (sem calcular valores próprios de H).

(c) Explique qual seria a utilidade destes procedimentos em optimização não linear (sem restrições).