Programação Não Linear

Ano Lectivo 2003/04

Trabalho 6: Métodos numéricos para optimização não linear com restrições

Data de recepção: 04/05/2004; Data de entrega: 20/05/2004

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

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

(a) Identifique, geometricamente, a solução óptima do problema e confirme que esse minimizante global satisfaz as condições suficientes de segunda ordem.

(b) Repare, agora, no seguinte problema em x_{1}, x_{2}, e s:

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

em que μ é um parâmetro real positivo.

i. Escreva as condições necessárias de primeira ordem para este problema quando x_{1} e

s assumem valores positivos. ii. Reescreva estas condições eliminando o multiplicador associado à restrição x_{1} + x_{2} − s = 1. Identifique, depois, aproximações para os multiplicadores associados às restrições x_{1} ≥ 0 e x_{1} + x_{2} ≥ 1 do problema original.

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 Matlab

Os códigos mencionados em baixo foram escritos pelo professor da disciplina, em Matlab, e com uma finalidade pedagógica no âmbito da disciplina. 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.

1. Leia, tente compreender e execute os códigos escritos em Matlab para a minimização da função do exercício 17.1 do livro Nocedal e Wright. Os códigos estão disponíveis em

         http://www.mat.uc.pt/∼lnv/pnl/e17ponto1.tar.gz

(a) Corra o método de penalização quadrática e o método da função Lagrangeana aumentada. Comente os resultados obtidos.

(b) Faça um novo teste utilizando o sistema linear (17.18) para obter a direcção de Newton para o método de penalização quadrática e explique a diferença nos resultados obtidos.