Programação Não Linear

Ano Lectivo 2000/01

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

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

1. Mostre que o conjunto dos minimizantes globais de uma função convexa é convexo.

2. Prove que se uma função for estritamente convexa e existir um minimizante local então ela possui um único minimizante global.

3. [Optimização com restrições.] Prove que uma região admissível definida algebricamente por funções c_{i} (i ∈ E) afins e por funções c_{i} (i ∈ I) côncavas é um conjunto convexo.

4. [Problemas de mínimos quadrados não lineares.] Considere a função

f(x) = \frac{1}{2}∥r(x)∥^{2} = \frac{1}{2} ∑_{j=1}^{m} r_{j}(x)^{2},

em que m > n e as m funções r_{j} : IR^{n} ⟶ IR são duas vezes continuamente diferenciáveis. Seja ainda J(x) a matriz cujas linhas são dadas pelos m gradientes das funções r_{j}.

(a) Mostre que, se J(x)^{⊤}r(x) ≠ 0, −J(x)^{⊤}r(x) é uma direcção de descida para a função f.

(b) Confirme que quando r(x) = 0 a matriz Hessiana de f é dada por

∑_{j=1}^{m} ∇r_{j}(x)∇r_{j}(x)^{⊤} = J(x)^{⊤}J(x).

Mostre que, se r(x) = 0 e J(x) tiver característica n, então o ponto x verifica as condições suficientes de segunda ordem.

5. [Sistemas de equações não lineares.] 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. Assuma que a matriz Jacobiana de r em x, J(x), é não singular. Mostre que a direcção −J(x)^{−1}r(x) é de descida para a função f(x) = 1/2∥r(x)∥^{2}.

6. Mostre que a sucessão {1/k} não converge para 0 q-linearmente.

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

8. 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. Considere a função

f(x_{1}, x_{2}) = (x_{1} + x_{2}^{2})^{2}.

(a) Escreva funções para calcular o valor de f, do seu gradiente e da sua Hessiana.

(b) Confirme, chamando uma destas funções, que p^{⊤} = (−1, 1) é uma direcção de descida de f em x^{⊤} = (1, 0).

(c) Calcule a direccção de Newton para f em x^{⊤} = (1, 0) e confirme, recorrendo à direcção de descida máxima, que se trata de uma direcção de descida.