Rascunho dos acetatos das aulas - norg

Transcrição

Bioinformática Avançada e Biologia de Sistemas –
Optimização
A. Ismael F. Vaz
Departamento de Produção e Sistemas
Escola de Engenharia
Universidade do Minho
[email protected]
Mestrado em Bioinformática
Ano lectivo 2009/2010
A. Ismael F. Vaz (UMinho)
Optimização
Bioinformática 09/10
1 / 218
Conteúdo
1
Introdução
2
Optimização
3
Optimização não linear sem restrições
4
R - Introdução
5
Método de Segurança de Newton
6
Método quasi-Newton
7
Optimização sem restrições com o R
8
Optimização não linear com restrições de igualdade
9
Optimização não linear com restrições de desigualdade
10
Optimização com restrições com o R
Optimização
2 / 218
Introdução
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
3 / 218
Introdução
Apresentação - Docente
Aulas teóricas e teórico-práticas
A. Ismael F. Vaz - [email protected]
www.norg.uminho.pt/aivaz
Horário de atendimento
Marcação por email.
Optimização
4 / 218
Introdução
Apresentação - Disciplina
Página da disciplina;
Três fichas TPs para resolver ao longo desta parte do módulo (Nota
mínima de 8);
A classificação final do módulo é:
Ficha TP1+Ficha TP2+Ficha TP3
.
3
A classificação na Unidade Curricular (UC) tem uma fórmula de
cálculo própria.
É obrigatória a presença em 2/3 das aulas efectivas (1/3 de faltas –
atenção às justificações/estatutos).
Optimização
5 / 218
Introdução
Material necessário e de apoio
Calculadora científica;
Folhas das fichas TPs;
Papel e caneta;
Livro de Computação Numérica;
www.norg.uminho.pt/emgpf
Sebenta de Optimização Não Linear;
www.norg.uminho.pt/emgpf
Software R - http://www.r-project.org;
Fichas TPs e acetatos disponíveis na página;
Optimização
6 / 218
Introdução
Motivação da disciplina
Optimização
A optimização é uma área da matemática aplicada com inúmeras
aplicações no nosso dia a dia.
Exemplo de aplicações
Poluição do ar (determinação de políticas óptimas), Robótica
(determinação de trajectórias óptimas), Processos de fermentação
semi-contínua (etanol, cerveja!!), etc... e astrofísica.
Engenharia
Está presente em todas as áreas da engenharia (sem excepção)...
Optimização
7 / 218
Introdução
Controlo óptimo - Um exemplo
Problema de optimização do processo semi-contínuo de produção de
Etanol.
O problema de optimização é: (t0 = 0 e tf = 61.2 dias)
com
max J(tf ) ≡ x3 (tf )x4 (tf )
u(t)
s.a
dx1
x1
= g1 x1 − u
dt
x4
dx2
150 − x2
= −10g1 x1 + u
dt
x4
x3
dx3
= g2 x1 − u
dt
x4
dx4
=u
dt
0 ≤ x4 (tf ) ≤ 200
0.408
x2
g1 =
1 + x3 /16
0.22 + x2
1
x2
g2 =
1 + x3 /71.5
0.44 + x2
onde x1 , x2 e x3 são as concentrações da
massa celular, substrato e produto (g/L),
e x4 é o volume (L). As condições iniciais
são:
0 ≤ u(t) ≤ 12
x(t0 ) = (1, 150, 0, 10)T .
∀t ∈ [t0 , tf ]
Optimização
8 / 218
Introdução
Abordagem para a resolução
Grande exigência em termos numéricos;
Grande exigência em termos de programação;
Solução da equação diferencial com o CVODE (software em C);
Problemas codificados em AMPL (linguagem de modelação);
Algoritmo para optimização sem derivadas;
Optimização
9 / 218
Introdução
Programa detalhado
Aula
1
2
3
4
5
6
Matéria
Grafos (Cláudio Alves)
Optimização Combinatória (Cláudio Alves)
Ficha de avaliação.
Introdução à optimização não linear (sem restrições). Definições e
condições de optimalidade.
Introdução ao R. Definição de vectores e matrizes. Codificação de
funções matemáticas e operadores.
Método de Newton e quasi-Newton. Modelação de casos em R (função
nlm e optim).
7
8
9
10
Ficha de Avaliação. Introdução à optimização não linear com restrições. Tipos de problemas e suas características. Condições de
optimalidade. Tratamento de restrições lineares e não lineares.
Modelação de casos e uso de R (funções solveLP, constrOptim e Rdonlp2).
Modelação de casos e uso de R (funções solveLP, constrOptim e Rdonlp2).
Revisões e Ficha de avaliação.
Optimização
10 / 218
Optimização
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
11 / 218
Optimização
Classificação
Os problemas de optimização podem ser classificados de acordo com:
as funções envolvidas (na função objectivo e nas restrições)
o tipo de variáveis usadas (inteiras, binárias, discretas, contínuas,
etc...)
o tipo de restrições consideradas (igualdade, desigualdade, infinitas,
complementaridade, etc...)
o tipo de solução que se pretende obter (local ou global)
diferenciabilidade das funções envolvidas (optimização com ou sem
derivadas)
Optimização
12 / 218
Optimização
Importância da classificação
Não existe software que resolva todos os tipos de problemas.
O tipo de problema que se pretende resolver condiciona o software (solver)
a usar.
Um solver para optimização contínua não pode ser usado para resolver
problemas com variáveis discretas.
Um solver que use derivadas (ou as estime), aplicado a um problema que
envolva funções não diferenciáveis, pode convergir (se convergir!!!) para
um ponto de descontinuidade da derivada, apresentando-a como solução.
Optimização
13 / 218
Optimização
Tipo de problemas
Programação linear
min(max) cT x(+d)
s.a Ax = b
Ex ≤ (≥)f
Programação quadrática
min xT Qx + cT x
s.a Ax = b
Ex ≤ f
Optimização
14 / 218
Optimização
Tipo de problemas
Optimização não linear
min f (x)
s.a c(x) = 0
h(x) ≤ 0
Desde que na definição do problema seja usada uma função não linear.
f (x), c(x) e h(x) podem ser funções lineares.
Optimização
15 / 218
Optimização
Classificação das variáveis
Booleanas ou binárias (0 ou 1)
Inteiras (Por exemplo 1,2,3,4,5,6,. . . )
Discretas (Por exemplo preto, azul, verde, vermelho, etc...)
Contínuas (Por exemplo x ∈ [0, 2])
Optimização
16 / 218
Optimização
Classificação quanto à solução pretendida
Óptimo local (determinação de um minimizante local ou relativo)
Óptimo global (determinação de um minimizante global ou absoluto)
Optimização
17 / 218
Optimização
Classificação quanto à estrutura
Programação semi-definida (envolve matrizes semi-definidas)
Programação semi-infinita (uma função objectivo sujeita a uma
infinidade de restrições)
Programação estocástica ou robusta (envolve parâmetros incertos,
conhecendo-se um intervalo de variação)
Problemas de complementaridade (restrições em que se uma for
diferente de zero então a outra é necessariamente zero)
Problemas de controlo óptimo (determinar a melhor forma de
controlar um determinado sistema - frequentemente modelado com
equações diferenciais)
etc...
Optimização
18 / 218
Optimização
Classificação de algoritmos
Estocásticos (Procura da solução de forma aleatória, mas controlada)
Algoritmos genéticos
Colónias de formigas
Colónias de partículas
etc...
Grande parte das vezes sem convergência garantida.
Usados para a procura global (quando funcionam!!!).
Determinísticos
Dados os parâmetros iniciais (aproximação inicial e parâmetros do
algoritmo) executa sempre da mesma forma.
Grande parte das vezes com convergência garantida para um óptimo
local.
Híbridos
Uma mistura das duas abordagens
Optimização
19 / 218
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
20 / 218
Forma geral do problema
A formulação matemática de um problema de optimização, na sua forma
mais geral, é
min f (x)
x∈Rn
s.a ci (x) = 0, i = 1, . . . , m
cj (x) ≥ 0, j = m + 1, . . . , t
onde f (x) é a função objectivo, ci (x) = 0 são as restrições de igualdade e
cj (x) ≥ são as restrições de desigualdade.
Optimização
21 / 218
Equivalência entre problemas
O problema de optimização (maximização)
max g(x)
x∈Rn
s.a ci (x) = 0, i = 1, . . . , m
c̃j (x) ≤ 0, j = m + 1, . . . , t
é equivalente ao problema de optimização (minimização)
min f (x) ≡ −g(x)
x∈Rn
s.a ci (x) = 0, i = 1, . . . , m
cj (x) ≡ −c̃j (x) ≥ 0, j = m + 1, . . . , t
Optimização
22 / 218
Interpretação geométrica
6
4
2
f(x), −f(x)
f(x*)
0
x*
−2
−f(x*)
−4
−6
−1.5
−1
−0.5
0
0.5
x
1
1.5
2
2.5
f (x) = (x − 0.5)2 + 2
g(x) = −f (x) = −(x − 0.5)2 − 2
Optimização
23 / 218
Exemplo
Pretende-se determinar o volume máximo de uma lata (cilindro), fechada
nas duas extremidades, sabendo que a quantidade de chapa a usar é de
1000 cm2 . Sendo r o raio da tampa e h a altura da lata, uma possível
formulação do problema de optimização é
max πr2 h
(r,h)∈R2
s.a 2πr2 + 2πrh = 1000
que pode ser transformado no problema de minimização
min −πx21 x2
s.a
x∈R2
2πx21
+ 2πx1 x2 = 1000
Optimização
24 / 218
Optimização sem restrições
Apenas iremos considerar problemas de minimização e sem restrições. A
sua formulação é pois
minn f (x).
x∈R
Classificação dos problemas (mais usuais)
Problemas unidimensionais (n = 1, ou seja, x ∈ R);
Problemas multidimensionais (n > 1, ou seja, x = (x1 , . . . , xn )T ∈ Rn );
Problemas de programação linear (f (x) e c(x) são funções lineares, i.e.,
f (x) = Ax, c(x) = Ax − b);
Problemas de programação quadrática (f (x) é uma função quadrática, i.e.,
f (x) = 12 xT Gx + dT x, e c(x) são funções lineares);
Problemas com limites simples (restrições nas variáveis do tipo al ≤ xl ≤ bl ,
l = 1, . . . , n);
Problemas de programação não linear (pelo menos uma das funções
envolvidas, f (x), c(x) é não linear).
Optimização
25 / 218
Classificação de mínimos
x∗ é
minimizante local forte se ∃δ tal que f (x∗ ) < f (x̄), ∀x̄ ∈ Vδ (x∗ );
minimizante local fraco se ∃δ tal que f (x∗ ) ≤ f (x̄), ∀x̄ ∈ Vδ (x∗ );
minimizante global forte se f (x∗ ) < f (x̄), ∀x̄ ∈ Rn ;
minimizante global fraco se f (x∗ ) ≤ f (x̄), ∀x̄ ∈ Rn ;
Onde Vδ (x∗ ) é uma vizinhança de x∗ de raio δ (||x̄ − x∗ || < δ).
Optimização
26 / 218
Mínimo global
Mínimo global forte
Função ilimitada
f (x∗ ) < f (x̄)
∀x̄ ∈ R
Mínimo global fraco
f (x∗ ) ≤ f (x̄)
∀x̄ ∈ R
Optimização
27 / 218
Mínimo local
∃δ : f (x∗ ) < f (x̄), ∀x̄ ∈ Vδ (x∗ ).
∃δ : f (x∗ ) ≤ f (x̄), ∀x̄ ∈ Vδ (x∗ ).
Optimização
28 / 218
Conceitos
Máximo e maximizante;
Mínimo e minimizante;
Óptimo local ou global;
Convergência local e global de algoritmos. Um algoritmo diz-se global
se determina um minimizante (maximizante) dada uma qualquer
aproximação inicial. Um algoritmo diz-se local se determina um
minimizante partindo apenas de uma aproximação inicial
suficientemente perto do minimizante. (Não confundir com a
determinação de mínimos locais ou globais).
Optimização
29 / 218
Condições de optimalidade
Condições necessárias para a existência de um mínimo
f 0 (x∗ ) = 0;
f 00 (x∗ ) ≥ 0.
Condições suficientes para a existência de um mínimo
f 0 (x∗ ) = 0;
f 00 (x∗ ) > 0.
Optimização
30 / 218
Exemplos
f (x) = (x − 1.5)2
f 0 (1.5) = 2 × (1.5 − 1.5) = 0
f 00 (1.5) = 2 > 0
f (x) = sin(x)
f 0 ( π2 ) = cos( π2 ) = 0
f 00 ( π2 ) = − sin( π2 ) = −1 < 0
1.02
0.25
1
0.2
0.98
0.96
0.15
0.94
0.92
0.1
0.9
0.88
0.05
0.86
0
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
0.84
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2
Pelas condições necessária e suficiente
Optimização
31 / 218
Exemplos
f (x) = x4
f 0 (0) = 3 × (0)3 = 0
f 00 (0) = 12 × (0)2 = 0
f (x) = x3
f 0 (0) = 3 × (0)2 = 0
f 00 (0) = 6 × (0) = 0
1
1
0.9
0.8
0.8
0.6
0.7
0.4
0.6
0.2
0.5
0
0.4
−0.2
0.3
−0.4
0.2
−0.6
0.1
0
−1
−0.8
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
−1
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
Verifica-se a condição necessária, mas não a condição suficiente
Optimização
32 / 218
Alguma notação
Gradiente de f (x) : Rn → R, x = (x1 , . . . , xn )T , vector de dimensão n
 ∂f 
∂x
 ∂f1

∇f (x) = g(x) =  ∂x2
 ...
∂f
∂xn
 ∂f ∂f
∂f T

,
,...,
=
∂x1 ∂x2
∂xn

Matriz Hessiana, matriz de dimensão n × n
 ∂2f

∇2 f (x) = G(x) = 
∂2f
∂xn ∂x1

...
...
∂2f
∂2f


∂x21
∂x1 ∂xn
Optimização
...
...
∂x2n
33 / 218
Condições necessárias para a existência de um mínimo
g(x∗ ) = 0 (sistema não linear);
G(x∗ ) 0 (semi-definida positiva).
Condições suficientes para a existência de um mínimo
g(x∗ ) = 0 (sistema não linear);
G(x∗ ) 0 (definida positiva).
Optimização
34 / 218
Exemplo
Pretende-se determinar todos os pontos óptimos do seguinte problema de
optimização
min x21 + x32 + 2x1 x2 ≡ f (x)
x∈R2
Da condição de necessária e suficiente de primeira ordem temos que
g(x) = (2x1 + 2x2 , 3x22 + 2x1 )T = (0, 0)T ,
ou seja,
(
2x1 + 2x2 = 0
3x22 + 2x1 = 0
(
⇔
x1 = −x2
3x22 − 2x2 = 0
⇔

 x1 = −x2
 x2 = 0 ∨ x2 = 2
3
Os pontos x̄ = (0, 0)T e x̂ = (− 32 , 23 )T são pontos estacionários de f (x).
Optimização
35 / 218
Cont.
Para verificar as condições de segunda ordem temos que estudar G(x̄) e
G(x̂).
2 2
2 2
2 2
G(x) =
, G(x̄) =
, G(x̂) =
2 6x2
2 0
2 4
2 2
det(|2|) = 2, det 2 0
= −4, det 2 2
2 4
=4
e temos que G(x̄) é indefinida (x̄ é ponto sela - descanso) e G(x̂) é
definida positiva (x̂ é mínimo local forte).
Optimização
36 / 218
Representação gráfica/Curvas de nível
1.5
15
1
10
f(x)
5
0.5
0
0
−5
−10
2
−0.5
1
0
−1
x2
−2
−1.5
−1
−0.5
0
0.5
1.5
−1
−1.5
−1.5
x1
f (x) =
1
x21
+
x32
−1
−0.5
0
0.5
1
1.5
+ 2x1 x2
Optimização
37 / 218
Motivação para os métodos numéricos
Na determinação analítica dos pontos estacionários é necessário resolver
um sistema não linear, que é quase sempre de difícil resolução.
Exemplo
Considere-se a função f (x) = x1 ex2 − 2x1 x2 .
Os pontos estacionários de f (x) obtêm-se através da resolução do sistema
não linear
(
ex2 − 2x2 = 0
x1 ex2 − 2x1 = 0
Optimização
38 / 218
R - Introdução
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
39 / 218
R - Introdução
O que é o R?
R
R pode ser considerado como uma implementação da linguagem S
desenvolvida nos laboratorios da Bell por Rick Becker, John Chambers e
Allan Wilks.
O ambiente R (linguagem de programação, GUI, etc..) é usado por muitas
pessoas como um sistema estatístico. Embora seja usado para a estatística
o ambiente R pode ser visto como um sistema em que muitas das técnicas
modernas de estatística se encontram implementadas.
Algumas das técnicas são fornecidas com o sistema (built in) enquanto que
outras são fornecidas como pacotes adicionais (packages).
Optimização
40 / 218
R - Introdução
R - Conteúdo
O que aprender?
Neste caso apenas iremos introduzir os comandos básicos e a criação de
scripts necessários aos capítulos seguintes.
O R possui algumas funções para optimização disponíveis na versão base,
opcionais como pacotes e outras que se podem obter na Internet.
Funções na versão base
uniroot - Determinação de zeros de funções unidimensionais.
optimize - Optimização unidimensional sem restrições.
optim - Optimização multidimensional sem restrições.
nlm - Optimização multidimensional sem restrições com algoritmo do
tipo Newton.
constrOptim - optimização multidimensional com restrições lineares.
Optimização
41 / 218
R - Introdução
Pacotes necessários (usados).
Disponíveis na CRAN
linprog (solveLP - Programação linear). Instalação usando o Menu
Packages->Install package(s).
...
Na web
Rdonlp2 (donlp2 - Optimização multidimensional com restrições).
Obtém-se em arumat.net/Rdonlp2.
Algencan - Possui uma interface de ligação ao R, mas é necessário
compilar o código fornecido. Pode-se obter em
www.ime.usp.br/~egbirgin/tango/r.php
...
Carregar os pacotes
Não esquecer de fazer Packages->Load package.
Optimização
42 / 218
R - Introdução
Só existe o R?
Ferramentas pouco similares
Outros programas pouco similares são o MATLAB, Mathematica e o Maple
Ferramentas similares
Linguagem de programação Python.
Optimização
43 / 218
R - Introdução
Ambiente R (R GUI)
Optimização
44 / 218
R - Introdução
Operações básicas
Aritméticas
> 2+3*2-1.5*2^2
[1] 2
Variáveis built-in – constantes
> pi
[1] 3.141593
Expressões (com o recurso a funções matemáticas)
> a <- 2*sin(pi)^2+3*exp(1)+sqrt(2)+cosh(2)
> a
[1] 13.33125
Optimização
45 / 218
R - Introdução
Operações básicas
Ajuda
> help(’acos’)
É aberta uma nova janela com a ajuda referentes às funções
trigonométricas.
Optimização
46 / 218
R - Introdução
Operações básicas – Formatos
Precisão
O R por defeito imprime apenas 7 casa decimais, mas essa opção (entre
outras) pode ser modificada.
> options(digits=15)
> pi
[1] 3.14159265358979
> options()
$add.smooth [1] TRUE
$check.bounds [1] FALSE
$chmhelp [1] TRUE
...
Optimização
47 / 218
R - Introdução
Operações básicas com vectores
Vectores
> x <- c(10.4,
> x
[1] 10.4 5.6
> 1/x
[1] 0.09615385
> y <- c(x, 0,
> y
[1] 10.4 5.6
5.6, 3.1, 6.4, 21.7)
3.1
6.4 21.7
0.17857143 0.32258065 0.15625000 0.04608295
x)
3.1
6.4 21.7
0.0 10.4
5.6
3.1
6.4 21.7
Um vector é definido como a concatenação de vários escalares.
Optimização
48 / 218
R - Introdução
Operações básicas com vectores
Operações com vectores
> v <- 2*x + y + 1
Warning message: In 2 * x + y :
longer object length is not a multiple of shorter object leng
> v <- x*c(2, 3, 4, 5, 6)+1
> v
[1] 21.8 17.8 13.4 33.0 131.2
Optimização
49 / 218
R - Introdução
Operações básicas com arrays e matrizes
Operações com arrays
Um vector para ser considerado um array tem que ser definida a sua
dimensão.
> dim(v) <- c(1,5)
> v
[,1] [,2] [,3] [,4] [,5]
[1,] 21.8 17.8 13.4
33 131.2
> dim(v) <- c(5,1)
> v
[,1]
[1,] 21.8
[2,] 17.8
[3,] 13.4
[4,] 33.0
[5,] 131.2
Optimização
50 / 218
R - Introdução
Operações básicas com vectores e matrizes
Função para definição de arrays e matrizes
As funções matrix() e array() permitem uma forma mais rápida e natural
de definir matrizes e arrays.
> x <- array(1:20, dim=c(4,5))
> x
[,1] [,2] [,3] [,4] [,5]
[1,]
1
5
9
13
17
[2,]
2
6
10
14
18
[3,]
3
7
11
15
19
[4,]
4
8
12
16
20
> i <- array(c(1:3,3:1), dim=c(3,2))
> i
[,1] [,2]
[1,]
1
3
[2,]
2
2
[3,]
3
1
Optimização
51 / 218
R - Introdução
Visualização e atribuição
> x[i]
[1] 9 6 3
> x[i] <- 0
> x
[,1] [,2] [,3] [,4] [,5]
[1,]
1
5
0
13
17
[2,]
2
0
10
14
18
[3,]
0
7
11
15
19
[4,]
4
8
12
16
20
Optimização
52 / 218
R - Introdução
Repetição de valores
> Z <- array(0, c(3,4,2))
> Z
, , 1
[1,]
[2,]
[3,]
[,1] [,2] [,3] [,4]
0
0
0
0
0
0
0
0
0
0
0
0
, , 2
[1,]
[2,]
[3,]
[,1] [,2] [,3] [,4]
0
0
0
0
0
0
0
0
0
0
0
0
Optimização
53 / 218
R - Introdução
Operações com matrizes e vectores
>
>
>
>
I=matrix(1,2,2)
x=array(c(1,2),dim=c(2,1))
Ix <- I %*% x
Ix
[,1]
[1,]
3
[2,]
3
> I*x
Error in I * x : non-conformable arrays
Optimização
54 / 218
R - Introdução
Operações com vectores – Funções
> Ix
[,1]
[1,]
3
[2,]
3
> cos(Ix)
[,1]
[1,] -0.9899925
[2,] -0.9899925
> a=array(1:3,dim=c(1,3))
> b=array(4:6,dim=c(1,3))
> a+b
[,1] [,2] [,3]
[1,]
5
7
9
Optimização
55 / 218
R - Introdução
Operações elemento a elemento
> a*b
[,1] [,2] [,3]
[1,]
4
10
18
> 2*a+b^2
[,1] [,2] [,3]
[1,]
18
29
42
Optimização
56 / 218
R - Introdução
> a %*% b
Error in a %*% b : non-conformable arguments
> a %*% aperm(b)
[,1]
[1,]
32
> aperm(a) %*% b
[,1] [,2] [,3]
[1,]
4
5
6
[2,]
8
10
12
[3,]
12
15
18
Optimização
57 / 218
R - Introdução
Matriz
> A<-matrix(1:6,3,2)
> A
[,1] [,2]
[1,]
1
4
[2,]
2
5
[3,]
3
6
Matriz transposta
> aperm(A)
[,1] [,2] [,3]
[1,]
1
2
3
[2,]
4
5
6
Matriz 2 × 3.
Matriz 3 × 2. O R é case
sensitive, i.e., A é diferente de a.
Optimização
58 / 218
R - Introdução
Operações com matrizes
> B<-matrix(6:1,3,2)
> B
[,1] [,2]
[1,]
6
3
[2,]
5
2
[3,]
4
1
> A %*% aperm(B)
[,1] [,2] [,3]
[1,]
18
13
8
[2,]
27
20
13
[3,]
36
27
18
> aperm(A) %*% B
[,1] [,2]
[1,]
28
10
[2,]
73
28
Soma
> A+B
[,1] [,2]
[1,]
7
7
[2,]
7
7
[3,]
7
7
> A %+% B
Error: could not find
function "%+%"
Optimização
59 / 218
R - Introdução
Sistemas lineares
Um sistema linear pode ser representado na forma de matricial como
Ax = b, em que A é uma matriz (dos coeficientes), x é a solução do
sistemas e b é um vector (dos termos independentes).
Sistema


 x1 +2x2 +3x3 = 1
4x1 +5x2 +6x3 = 2
≡ 

7x1 +8x2 +9x3 = 3


1 2 3
i.e. A =  4 5 6 
7 8 9
Optimização

1 2 3
4 5 6 
7 8 9


x1
x =  x2 
x3
  
x1
1
x2  =  2 
3
x3
 
1
e b= 2 
3
60 / 218
R - Introdução
Resolução de Sistemas lineares
Um exemplo (diferente do anterior)
>
>
>
>
A<-matrix(c(1,2,3,5,6,7,3,4,7),3,3)
b<-array(1:3,dim=c(3,1))
x <- solve(A,b)
x
[,1]
[1,] 1.000000e+00
[2,] 4.163336e-17
[3,] -8.326673e-17
> A%*%x-b
[,1]
[1,]
0
[2,]
0
[3,]
0
Optimização
61 / 218
R - Introdução
Inversa de uma matriz
O exemplo anterior
> A<-matrix(c(1,2,3,5,6,7,3,4,7),3,3)
> solve(A)
[,1] [,2] [,3]
[1,] -1.75 1.75 -0.25
[2,] 0.25 0.25 -0.25
[3,] 0.50 -1.00 0.50
> A%*%solve(A)
[,1]
[,2]
[,3]
[1,] 1.000000e+00 2.220446e-16 1.110223e-16
[2,] 0.000000e+00 1.000000e+00 0.000000e+00
[3,] 3.330669e-16 2.220446e-16 1.000000e+00
Optimização
62 / 218
R - Introdução
Resolução de Sistemas lineares
Curiosidades
> absdetA <- prod(svd(A)$d)
> absdetA
[1] 8
> det(A)
[1] -8
svd - singular value decomposition - retorna uma lista em que d são os
elementos da diagonal.
Optimização
63 / 218
R - Introdução
Acesso a elementos de vectores e matrizes
Acesso a vectores
> x <- seq(-pi, pi, by=.5)
> x
[1] -3.1415927 -2.6415927 -2.1415927 -1.6415927 -1.1415927 -0.
[7] -0.1415927 0.3584073 0.8584073 1.3584073 1.8584073 2.
[13] 2.8584073
> y <- sin(x)
> y
[1] -1.224606e-16 -4.794255e-01 -8.414710e-01 -9.974950e-01 -9
[6] -5.984721e-01 -1.411200e-01 3.507832e-01 7.568025e-01 9
[11] 9.589243e-01 7.055403e-01 2.794155e-01
> y[2:3]
[1] -0.4794255 -0.8414710
Optimização
64 / 218
R - Introdução
Acesso a elementos de vectores e matrizes
Acesso a matrizes
> A <- matrix(seq(length=10, from=-5, by=.2),5,2)
> A
[,1] [,2]
[1,] -5.0 -4.0
[2,] -4.8 -3.8
[3,] -4.6 -3.6
[4,] -4.4 -3.4
[5,] -4.2 -3.2
> A[2:4,1]
[1] -4.8 -4.6 -4.4
Optimização
65 / 218
R - Introdução
Matrizes e vectores especiais
Zeros e uns
> matrix(0,2,2)
[,1] [,2]
[1,]
0
0
[2,]
0
0
> matrix(1,2,2)
[,1] [,2]
[1,]
1
1
[2,]
1
1
Identidade - Aleatórias
> diag(3)
[,1] [,2] [,3]
[1,]
1
0
0
[2,]
0
1
0
[3,]
0
0
1
> x <- rnorm(50)
> X <- matrix(rnorm(4),2,2)
> X
[,1]
[,2]
[1,] 0.9333478 -0.9596665
[2,] 1.2975969 1.1051097
> Y <- matrix(runif(4),2,2)
> Y
[,1]
[,2]
[1,] 0.8034793 0.9085925
[2,] 0.2916994 0.2851831
Optimização
66 / 218
R - Introdução
Modificação de elementos em vectores e matrizes
Atribuições
> A <- matrix(1,3,3)
> A[1:2,1] <- 2
> A
[,1] [,2] [,3]
[1,]
2
1
1
[2,]
2
1
1
[3,]
1
1
1
> A[3,c(1,3)]<-4
> A
[,1] [,2] [,3]
[1,]
2
1
1
[2,]
2
1
1
[3,]
4
1
4
Troca de valores
> A[c(1,2),1]<-2*A[c(1,2),1]
> A
[,1] [,2] [,3]
[1,]
4
1
1
[2,]
4
1
1
[3,]
4
1
4
> A[2:3,3]=A[3:2,3]
> A
[,1] [,2] [,3]
[1,]
4
1
1
[2,]
4
1
4
[3,]
4
1
1
Optimização
67 / 218
R - Introdução
Vectores lógicos
Vectores lógicos
> ages <- c(12, 11, 18, 19, 11, 60, 65, 71, 7, 10)
> adults <- ages >= 18
> old <- ages >=65
> adults
[1] FALSE FALSE TRUE TRUE FALSE TRUE TRUE TRUE FALSE FALSE
> old
[1] FALSE FALSE FALSE FALSE FALSE FALSE TRUE TRUE FALSE FALSE
> active <- adults & !old
> active
[1] FALSE FALSE TRUE TRUE FALSE TRUE FALSE FALSE FALSE FALSE
> totaladults <- sum(adults*ages)
> totaladults
[1] 233
Optimização
68 / 218
R - Introdução
Operadores lógicos
Operadores lógicos
Símbolo
>
<
!=
!
|
Representa
Maior que
Menor que
Diferente de
Negação
Ou
Símbolo
>=
<=
==
&
Representa
Maior ou igual que
Menor ou igual que
Igual a
E
Optimização
69 / 218
R - Introdução
Valores em falta
Not a Number (NaN) e infinito (Inf)
> x <- c(1, 2, NaN, 0)
> y <- c(1, 0, 2, 0)
> z <- x/y
> z
[1]
1 Inf NaN NaN
> is.na(z)
[1] FALSE FALSE TRUE TRUE
> is.nan(z)
[1] FALSE FALSE TRUE TRUE
> is.finite(z)
[1] TRUE FALSE FALSE FALSE
> is.infinite(z)
[1] FALSE TRUE FALSE FALSE
Optimização
70 / 218
R - Introdução
Funções básicas
Funções
Função
max
min
sum
mean
sd
Descrição
Elemento máximo de um vector
Elemento mínimo de um vector
Soma de todos os elementos
Média aritmética
Desvio padrão
Optimização
71 / 218
R - Introdução
Mensagens e display de variáveis
Conteúdo de exp.txt
Ficheiros
> i <- 1:3
1
2
3
4
5
> X <- matrix(1:10,ncol=5)
6
7
8
9
10
> write(X, file="exp.txt", sep = "\t") 1
2
> write(cbind(i,X[1,i]),
3
1
file="exp.txt", ncolumns=2,
3
5
append=TRUE, sep = "\t")
Optimização
72 / 218
R - Introdução
União de matrizes
União de matrizes
> i
[1] 1 2 3
> x
[,1] [,2] [,3] [,4] [,5]
[1,]
1
3
5
7
9
[2,]
2
4
6
8
10
> c(i,x[1,i])
[1] 1 2 3 1 3 5
> cbind(i,x[1,i])
i
[1,] 1 1
[2,] 2 3
[3,] 3 5
> rbind(i,x[1,i])
[,1] [,2] [,3]
i
1
2
3
1
3
5
Optimização
73 / 218
R - Introdução
Definição de funções
> fx <- function(x) x^2+3+cos(x)
> fx
function(x) x^2+3+cos(x)
> fx(2)
[1] 6.583853
Optimização
74 / 218
R - Introdução
Argumentos de funções
> fun1 <- function(data, data.frame, graph, limit) {
[corpo da função omitido]
}
A função pode então ser chamada de diversas formas equivalentes:
> ans <- fun1(d, df, TRUE, 20)
> ans <- fun1(d, df, graph=TRUE, limit=20)
> ans <- fun1(data=d, limit=20, graph=TRUE, data.frame=df)
Também podem ser definidos valores por defeito para determinados
parâmetros
> fun1 <- function(data, data.frame, graph=TRUE, limit=20) { ..
Podendo a função ser chamada das diversas formas:
> ans <- fun1(d, df)
> ans <- fun1(d, df, limit=10)
Optimização
75 / 218
R - Introdução
Scripts
Definição
Um script trata-se da execução de uma série de comandos. Os scripts são
guardados em ficheiros de extensão .r.
Ficheiro bioinf.r
i <- 1:3
X <- matrix(1:10,ncol=5)
Execução
> source("bioinf.r")
> X
[,1] [,2] [,3] [,4] [,5]
[1,]
1
3
5
7
9
[2,]
2
4
6
8
10
Optimização
76 / 218
R - Introdução
Desenho de gráficos 2D
Plot
> x <- seq(-pi,pi,0.1)
> plot(x,sin(x))
> plot(x,sin(x),’l’)
> plot(x,sin(x),’l’,ylab=’sin(x)’)
> title(main=’O meu primeiro gráfico’, xlab=’x’,
ylab=’sin(x)’)
Optimização
77 / 218
R - Introdução
0.0
-1.0
-0.5
sin(x)
0.5
1.0
O meu primeiro gráfico
-3
-2
-1
0
x
Optimização
1
2
3
78 / 218
R - Introdução
Sobreposição
> x<-seq(0,4*pi,0.1)
> plot(x,sin(x),’l’,ylab=’sin(x)+cos(x)’)
> par(new=TRUE)
> plot(x,cos(x),’l’,ylab=’’)
Optimização
79 / 218
R - Introdução
0.0
-1.0
-0.5
sin(x)+cos(x)
0.5
1.0
0
2
4
6
x
Optimização
8
10
12
80 / 218
R - Introdução
Usando marcas e tipos de linhas
> plot(x,cos(x),’l’,lty=2)
> par(lty=2)
> plot(x,cos(x),’l’)
Função par
A função par permite modificar diversos parâmetros.
Optimização
81 / 218
R - Introdução
0.0
-1.0
-0.5
cos(x)
0.5
1.0
0
2
4
6
x
Optimização
8
10
12
82 / 218
R - Introdução
Plot3
> x <- seq(-10, 10, length= 30)
> y <- x
> f <- function(x,y) { r <- sqrt(x^2+y^2); 10 * sin(r)/r }
> z <- outer(x, y, f)
> z[is.na(z)] <- 1
> op <- par(bg = "white")
> persp(x, y, z, theta = 30, phi = 30, expand = 0.5,
col = "lightblue")
Optimização
83 / 218
R - Introdução
y
z
x
Optimização
84 / 218
R - Introdução
Desenho de curvas de nível
Contour
> x=seq(-pi,pi,0.1)
> y=seq(0,pi,0.1)
> fx <- function(x,y) {sin(x^2)+2*sin(y)}
> z <- outer(x,y,fx)
> contour(x,y,z)
> contour(x,y,z,nlevel=50)
Optimização
85 / 218
R - Introdução
1
1
0
0.
5
0.5
2.5
1.5
1
1.5
0.5
0.5
1
0
1
-0
.5
.5
-0
3.0
2.5
1.5
2.0
2.5
2
2
2.5
2.5
1.0
2
1.5
0.5
0.5
0.5
1
0.5
0
0
0.0
0
-3
-0.5
-2
-1
0
Optimização
1
2
0.5
0.5
-0.
5
3
86 / 218
R - Introdução
0.3
1.6
0.7
1.8
2.7
1
2.2
0.
9
2.9
2
2.1
1.6
2.3
Optimização
1
11.1
0.7
0.2
0.1
0
-0.3
1.3
0.4
0.5
-0.7
1.3
0.9
0.4
0.5
2.1
0.8
1.8
7
0.5
1.0
0.4
0
-0
.7
0.10
-1
0.7
0.3
0.6
8
0.
1.2
0.3
0.10
0.5
00.5.
6
1.3
0.2
0.6
0.0
1.7
4
2.
2.1
1.2
0.3
-2
2.3
0.7
0.9
1.5
2.1
-0.3
2.6
1.9
-3
2.8
1.7
2.6
2.3
0.9
2.4
2.8
0.9
2
2
2
2.7
2.7
1.5
2.9
2.5
2.5
2.6
2.
7
1.8
0.
4
2.5
2.4
2.4
0.9
0.8
-0
.6
1.5
0.7
0
2.5
0.8
2.3
2.2
1.4
1.6
2.2
1
1
-0.1
0.3
2
0.0.
87
1.1
2.2
1.9
1.4
0.3
0.6
2.6
-0.2
1.4
2.5
0.8
1.9
0
1.5
2.0
0.4
0.6
1.2
.3
-0
0.9
0.2
0.5
0.7
8
0.
0.6
0.2
-0.6
1.1
3.0
3
87 / 218
R - Introdução
Funções R
>
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
open.account <- function(total) {
list(
deposit = function(amount) {
if(amount <= 0)
stop("Deposits must be positive!\n")
total <<- total + amount
cat(amount, "deposited. Your balance is", total, "\n\n")
},
withdraw = function(amount) {
if(amount > total)
stop("You donŠt have that much money!\n")
total <<- total - amount
cat(amount, "withdrawn. Your balance is", total, "\n\n")
},
balance = function() {
cat("Your balance is", total, "\n\n")
})}
Optimização
88 / 218
R - Introdução
Funções R
> ross <- open.account(100)
> robert <- open.account(200)
> ross$withdraw(30)
30 withdrawn. Your balance is 70
> ross$balance()
Your balance is 70
> robert$balance()
Your balance is 200
Optimização
89 / 218
R - Introdução
Funções R – O if
Função
> fx <- function(x) {
+ if(x>0) x else -x
+ }
> fx(2)
[1] 2
> fx(-2)
[1] 2
> fx(c(2,-2))
[1] 2 -2
Warning message:
In if (x > 0) x else -x :
the condition has length > 1 and only the first element will
be used
Optimização
90 / 218
R - Introdução
Funções R – O if
Função – Cont.
> x <- c(6:-4)
> sqrt(x)
[1] 2.449490 2.236068 2.000000 1.732051 1.414214 1.000000 0.000000
[9]
NaN
NaN
NaN
Warning message:
In sqrt(x) : NaNs produced
> sqrt(ifelse(x >= 0, x, NA))
[1] 2.449490 2.236068 2.000000 1.732051 1.414214 1.000000 0.000000
[9]
NA
NA
NA
> ifelse(x >= 0, x, NA)
[1] 6 5 4 3 2 1 0 NA NA NA NA
> ifelse(x >= 0, x, 0)
[1] 6 5 4 3 2 1 0 0 0 0 0
Optimização
91 / 218
R - Introdução
Funções R – O for
Execução
> for(i in 1:5) print(1:i)
[1] 1
[1] 1 2
[1] 1 2 3
[1] 1 2 3 4
[1] 1 2 3 4 5
Optimização
92 / 218
R - Introdução
Funções R – O for
Execução
> for(n in c(2,5,10,20,50)) {
+
x <- stats::rnorm(n)
+
cat(n,":", sum(x^2),"\n")
+ }
2 : 1.439276
5 : 2.110872
10 : 3.601880
20 : 16.54088
50 : 40.6597
Optimização
93 / 218
R - Introdução
Zeros de funções
A função uniroot
> f <- function (x) sin(x)+2*cos(x)
> xmin <- uniroot(f, c(0, pi), tol = 0.0001)
> xmin
$root
[1] 2.034445
$f.root
[1] -2.477787e-06
$iter
[1] 5
$estim.prec
[1] 5e-05
O intervalo tem que obedecer a f (lower) ∗ f (upper) ≤ 0.
Optimização
94 / 218
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
95 / 218
Forma geral do problema
A formulação matemática de um problema de optimização
multidimensional, sem restrições é
min f (x),
x∈Rn
com f (x) : Rn → R (n > 1) duas vezes diferenciável.
Optimização
96 / 218
Notação
Gradiente de f (x) : Rn → R, x = (x1 , . . . , xn )T , vector de dimensão n
 ∂f 
∂x
 ∂f1

∇f (x) = g(x) =  ∂x2
 ...
∂f
∂xn
 ∂f ∂f
∂f T

,
,...,
=
∂x1 ∂x2
∂xn

Matriz Hessiana, matriz de dimensão n × n
 ∂2f

∇2 f (x) = G(x) = 
∂2f
∂xn ∂x1

...
...
∂2f
∂2f


∂x21
∂x1 ∂xn
Optimização
...
...
∂x2n
97 / 218
Alguns conceitos
O vector gradiente ‘aponta’ no sentido de subida da função.
−g(x)
g(x)
100
10
0
5
−100
0
−200
−10
−5
−5
f (x) =
− x21 − x22 − 2x1 x2 + 10
0
5
10
g(x) =
−10
(−2x1 − 2x2 , −2x2 − 2x1 )T
g(1, 1) = (−4, −4)T
Optimização
98 / 218
Alguns conceitos - Cont.
A matrix Hessiana indica a concavidade (convexa ou côncava).
50
0
−50
−100
−150
10
−200
−10
5
0
−5
0
−5
5
10
−10
f (x) =
− x21 − x22 − 2x1 x2 + 10
−2 −2
G(x) =
−2 −2
Semi-definida negativa.
Optimização
99 / 218
Método de Newton
A função f (x), em x∗ = x + d pode ser aproximada por
1
f (x∗ ) ≈ f (x) + g(x)T d + dT G(x)d
2
(1)
que resulta da expansão em série de Taylor de f (x), com x∗
suficientemente perto de x.
A aproximação quadrática (1) pode ser usada para determinar o vector d
em que x é um vector fixo. Derivando em ordem a d e igualando a zero
obtemos
g(x) + G(x)d = 0 ⇔ G(x)d = −g(x)
(2)
Optimização
100 / 218
Cont.
Quando a função f (x) é quadrática obtém-se a solução resolvendo o
sistema linear (2). No caso em que f (x) não é quadrática, o novo ponto
x + d não é mínimo e o processo deve ser repetido iterativamente. As
equações iterativas do processo são
x(k+1) = x(k) + d(k)
G(x(k) )d(k) = −g(x(k) ), para k = 1, 2, . . .
Nota: O método de Newton possui terminação quadrática, i.e., se f (x) for
uma função quadrática convexa o método de Newton necessita no máximo
de n iterações para encontrar a solução exacta.
Optimização
101 / 218
Método de Newton - Falhas de convergência
O método de Newton pode falhar nas seguintes condições:
A matriz G(x(k) ) é singular e d(k) não é sequer definido.
O vector direcção d(k) é quase ortogonal a g(x(k) ) e não é possível
progredir ao longo de d(k) .
O vector direcção d(k) não aponta no sentido descendente de f e não
é possível garantir a descida do valor da função.
A matriz G(x(k) )−1 existe e é definida positiva, o vector direcção d(k)
é de descida, no entanto o comprimento é tal que
f (x(k+1) ) > f (x(k) ), e o novo ponto não é melhor que o anterior.
Optimização
102 / 218
Método de segurança de Newton
O método de segurança de Newton resolve as possíveis falhas do método
de Newton.
A matriz G(x(k) ) é singular e d(k) não é sequer definido. Neste caso
toma-se como direcção de procura a direcção de descida máxima
(d(k) = −g(x(k) )).
Como a direcção de descida máxima resolve os restantes problemas
(excepto o problema do comprimento da direcção) não e necessário
verificar a quase-ortogonalidade e a descida da função objectivo.
Optimização
103 / 218
Cont.
O vector direcção d(k) é quase ortogonal a g(x(k) ) e não é possível
progredir ao longo de d(k) .
6
4
−g(1,1)
2
0
g(1,1)
−2
−4
Quase ortogonal se
−6
|g(x(k) )T d(k) | ≤ ηkg(x(k) )kkd(k) k
−6
−4
−2
0
2
4
6
Se for quase ortogonal então
d(k) = −g(x(k) )
Optimização
104 / 218
Cont.
O vector direcção d(k) não aponta no sentido descendente de f e não é
possível garantir a descida do valor da função.
d(k) é direcção de descida se
g(x(k) )T d(k) ≤ ηkg(x(k) )kkd(k) k.
Caso d(k) não seja direcção de descida faz-se
d(k) = −d(k) .
Optimização
105 / 218
Cont.
A matriz G(x(k) )−1 existe e é definida positiva, o vector direcção d(k) é de
descida, no entanto o comprimento é tal que f (x(k+1) ) > f (x(k) ), e o novo
ponto não é melhor que o anterior.
O método de Newton tem convergência local, i.e., x(k) tem de ser
suficientemente próximo de x∗ para que o método funcione.
A convergência global obtém-se através da introdução da procura
unidimensional (regiões de confiança!!).
x(k+1) = x(k) + αd(k)
em que o α deve ser calculado para garantir que
f (x(k+1) ) < f (x(k) )
Decréscimo simples
Optimização
106 / 218
Procura unidimensional exacta
Na procura unidimensional exacta pretende-se determinar (exactamente)
qual o valor de α que minimiza a função
φ(α) = f (x(k+1) ) com x(k+1) = x(k) + αd(k) ,
usando as condições de optimalidade
φ0 (α) = 0 e φ00 (α) > 0.
No entanto a solução para o problema minα∈R φ(α) não é de fácil
resolução (difícil implementação e cálculos computacionais pesados).
Optimização
107 / 218
Procura unidimensional
Critério de Armijo e divisões sucessivas de α por dois.
Pressupondo que a direcção de procura é de descida, gera-se uma
sequência de valores,
{ω j α}, j = 0, 1, 2, . . . com α = 1 e ω =
1
2
até se encontrar um elemento que origine uma redução (significativa) no
valor de f
f (x(k) ) − f (x(k) + ω j αd(k) ) ≥ −µ1 ω j αg(x(k) )T d(k) .
O primeiro elemento encontrado é usado como o comprimento do passo na
iteração k (α(k) = ω j α).
Optimização
108 / 218
Critério de paragem
Considera-se as três condições para o critério de paragem
kx(k+1) − x(k) k
≤ 1
kx(k+1) k
|f (k+1) − f (k) |
≤ 2
|f (k+1) |
kg (k+1) k ≤ 3
Optimização
109 / 218
Exemplo
Considere-se o seguinte problema de optimização
min x41 + x22 − 3x1
x∈R2
partindo de x(1) = (0, 1)T e com = 0.5.
Temos que
g(x) = (4x31 − 3, 2x2 )T
e
G(x) =
12x21 0
0
2
Optimização
110 / 218
1a iteração
g
(1)
(1)
= g(x
T
) = (−3, 2)
G
0 0
3
0 2 −2
(1)
= G(x
(1)
)=
0 0
0 2
→ Impossível
Como a matriz G(x(1) ) é singular temos que d(1) = −g (1) = (3, −2)T .
Não é necessário verificar a quase ortogonalidade e passa-se para a procura
unidimensional.
Optimização
111 / 218
x(1) = (0, 1)T
α=1
f (1) = 1
g (1)T d(1) = −13
x̄ = x(1) + d(1) = (0, 1)T + 1(3, −2)T = (3, −1)T f (x̄) = 73
1 − 73 = f (x(1) ) − f (x̄) 10−3 × 1 × 13
α = 0.5
x̄ = (0, 1)T + 0.5(3, −2)T = (1.5, 0)T f (x̄) = 0.5625
1 − 0.5625 = f (x(1) ) − f (x̄) ≥ 10−3 × 0.5 × 13
Aceita-se α(1) = 0.5 e tem-se x(2) = (1.5, 0)T .
Optimização
112 / 218
kx(2) − x(1) k
=
kx(2) k
√
1.52 + 12
= 1.201 0.5
1.5
Logo passa-se à próxima iteração. As restantes condições seriam (neste
caso não é necessário verificar)
|f (2) − f (1) |
1 − 0.5625
=
= 0.7778 0.5
(2)
0.5625
|f |
e
kg (2) k = k(10.5, 0)T k = 10.5 0.5
Optimização
113 / 218
2a iteração x(2) = (1.5, 0)T
(2)
T
(2)
27 0
0 2
g = (10.5, 0) G =
27 0 −10.5
→ d(2) = (−0.3889, 0)T
0 2
0
d(2) é quase ortogonal com o gradiente?
kd(2) k = 0.3889 kg (2) k = 10.5
(g (2) )T d(2) = (10.5, 0)(−0.3889, 0)T = −4.0835
4.0835 = |(g (2) )T d(2) | 10−4 × 0.3889 × 10.5 = 4.0835 × 10−4 ,
logo d(2) não é quase ortogonal com o gradiente (se fosse d(2) = −g (2) ).
Optimização
114 / 218
2a iteração - Cont.
d(2) é direcção de descida?
kd(2) k = 0.3889 kg (2) k = 10.5
(g (2) )T d(2) = (10.5, 0)(−0.3889, 0)T = −4.0835
− 4.0835 = (g (2) )T d(2) ≤ 10−4 × 0.3889 × 10.5 = 4.0835 × 10−4 ,
logo d(2) é direcção de descida (se não fosse d(2) = −d(2) ).
Inicia-se a procura unidimensional.
Optimização
115 / 218
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
116 / 218
Método Quasi-Newton
O método Quasi-Newton usa uma matriz aproximação à matriz
Hessiana (ou à sua inversa) da função objectivo.
O uso de uma matriz aproximação evita o cálculo da matriz Hessiana
(segundas derivadas) que pode ser difícil de obter.
A aproximação à inversa da Hessiana, em vez da própria Hessiana,
substituí a resolução de um sistema linear em cada iteração, por um
produto matriz vector. (G(x)d = −g(d) → d = −G(x)−1 g(x)).
Optimização
117 / 218
Cont.
A matriz aproximação é actualizada em cada iteração usando a informação
das derivadas (gradiente) da iteração anterior.
A fórmula mais conhecida é devida a Broyden, Fletcher, Goldfarb e Shanno
(B.F.G.S.)
!
!
(k) s(k)T
(k) y (k)T
y
s(k) s(k)T
s
H (k+1) = I − (k)T (k) H (k) I − (k)T (k) + (k)T (k)
s
y
y
s
s
y
em que s(k) = α(k) d(k) = x(k+1) − x(k) e y (k) = g (k+1) − g (k) .
Quando s(k)T y (k) > 0 e H (k) é simétrica e definida positiva, a formula de
actualização garante que a matriz H (k+1) é simétrica e definida positiva.
A fórmula B.F.G.S. satisfaz a propriedade de terminação quadrática.
Optimização
118 / 218
Cont.
Na primeira iteração temos que H (1) = I (simétrica e definida positiva).
Quando se usa a técnica de recomeço a matriz H (k) = I sempre que
(k − 1) mod n = 0.
Como H (k) é simétrica e definida positiva não é necessário verificar a quase
ortogonalidade e se a direcção calculada é de descida para a função
objectivo.
Os problemas numéricos com a matriz H (k) , tais como
‘overflow’ na actualização de H (k) ,
um deslocamento ao longo da direcção de procura muito longo devido
à quase ortogonalidade da direcção com o gradiente,
podem ser ultrapassados usando a técnica do recomeço.
Optimização
119 / 218
Exemplo
Considere-se o seguinte problema de optimização (x(1) = (0, 1)T e = 0.5)
min x41 + x22 − 3x1
x∈R2
Temos que g(x) = (4x31 − 3, 2x2 )T .
1a iteração
g (1) = g(x(1) ) = (−3, 2)T H (1) = I d(1) = −Hg (1) = (3, −2)T .
. . . (ver exemplo do segurança de Newton)
Aceita-se α(1) = 0.5 e vem que x(2) = (1.5, 0)T .
Optimização
120 / 218
kx(2) − x(1) k
=
kx(2) k
√
1.52 + 12
= 1.201 0.5
1.5
Logo passa-se à próxima iteração.
2a iteração x(2) = (1.5, 0)T e g (2) = (10.5, 0)T
H (2) =
s(1) y (1)T
I − (1)T (1)
s
y
!
H (1)
y (1) s(1)T
I − (1)T (1)
y
s
!
+
s(1) s(1)T
s(1)T y (1)
s(1) = x(2) − x(1) = (1.5, 0)T − (0, 1)T = (1.5, −1)T
y (1) = g (2) − g (1) = (10.5, 0)T − (−3, 2)T = (13.5, −2)T
Optimização
121 / 218
Cont.
s
(1) (1)T
y
1.5
−1
=
20.25 −3
−13.5
2
(13.5, −2) =
s(1)T y (1) = (1.5, −1)(13.5, −2)T = 22.25
s(1) y (1)T
I − (1)T (1) =
s
y
1
0
(1) (1)T
s
H
(2)
=
s
0.0899
0.6067
0
1
−
=
0.1348
0.9101
H
1.5
−1
H
(2)
0.9101
−0.6067
(1.5, −1) =
(1)
=
−0.1348
0.0899
0.0899
0.1348
=
0.0899
0.6067
2.25 −1.5
−1.5
1
0.6067
0.9101
0.1274 0.1098
0.1098 1.2413
Optimização
+
0.1348
0.9101
0.1011
−0.0674
−0.0674
0.0449
122 / 218
Cont.
(2)
d
= −H
0.1274 0.1098
g =−
0.1098 0.8202
−1.3377
(2)
d =
−1.1529
(2) (2)
10.5
0
...
Optimização
123 / 218
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
124 / 218
Funções R (base)
O R fornece um conjunto de funções para optimização linear e não linear
das quais se destacam:
uniroot - Zero de funções unidimensionais;
optimize - Optimização de uma função unidimensional num intervalo.
nlm - Minimização usando um algoritmo do tipo Newton;
optim - Função genérica para optimização baseada nos algoritmos de
Nelder-Mead, quasi-Newton e gradientes conjugados;
Optimização
125 / 218
Zeros de funções
A função uniroot
> f <- function (x) sin(x)+2*cos(x)
> xmin <- uniroot(f, c(0, pi), tol = 0.0001)
> xmin
$root
[1] 2.034445
$f.root
[1] -2.477787e-06
$iter
[1] 5
$estim.prec
[1] 5e-05
O intervalo tem que obedecer a f (lower) ∗ f (upper) ≤ 0.
Optimização
126 / 218
Exemplo não linear unidimensional
Um navio encontra-se atracado num porto. A distância h, de um dado
ponto do casco do navio ao fundo do mar, varia com a maré. Admita que
h é dada, em função do tempo x, por
h(x) = 10 − 3 cos(2x).
Qual a distância desse ponto do casco ao fundo do mar no momento da
maré alta?
Formulação do problema
maxx∈R h(x)
≡ 10 − 3 cos(2x)
Sabendo que x >= 0.
Optimização
127 / 218
10
7
8
9
hx(x)
11
12
13
0
1
2
3
4
5
6
x
Optimização
128 / 218
Resolução
> hx <- function(x) 10-3*cos(2*x)
> x <- seq(0,6,0.1) # Para o plot
> plot(x,hx(x),’l’) # Plot
> optimize(hx,c(1,2),maximum=TRUE)
$maximum [1] 1.57078
$objective [1] 13
O algoritmo
O algoritmo usado é um algoritmo do tipo Secção Dourada com
interpolação quadrática.
Optimização
129 / 218
Exemplo não linear unidimensional - outra abordagem
Resolução
> hx <- function(x) 3*cos(2*x)-10
> optimize(hx,c(1,2))
$minimum [1] 1.57078
$objective [1] -13
Função simétrica
Atenção que o minimizante é o mesmo que o maximizante, mas os valores
das funções objectivo são o simétrico.
Optimização
130 / 218
Exemplo não linear
Considere que um montante xi é afectado ao projecto i, para i = 1, . . . , n,
sendo o retorno esperado desta carteira de projectos dado por
f (x1 , . . . , xn ) =
n
n−1
X
1
1X
(αi xi − βi x2i ) +
(xi xi+1 ) (n > 1).
2
2
i=1
i=1
Para n = 2, α1 = 1, α2 = 2, β1 = β2 = 1, pretende-se calcular x1 e x2 de
modo a maximizar o retorno esperado.
O problema é modelado como um problema de optimização sem restrições
x21
x22
x1 x2
max f (x1 , x2 ) ≡ x1 −
+ 2x2 −
+
2
2
2
Optimização
131 / 218
A resolução – Curvas de nível
Função e curvas de nível
> f <- function(x) {
+ (x[1]-x[1]^2/2)+(2*x[2]-x[2]^2/2)+x[1]*x[2]/2
+ }
> x1=seq(2,4,0.1)
> x2=seq(2,4,0.1)
> z<-matrix(0,length(x1),length(x2))
> for (i in 1:length(x1))
+ { for (j in 1:length(x2))
+ { z[i,j]<-f(c(x1[i],x2[j])) }
+ }
> contour(x1,x2,z,50)
Optimização
132 / 218
4.0
A resolução – Curvas de nível
4.3
5
4.4
35
4.
4.5
5
4.4
25
4.
4.65
4.5
3.5
4.5
1
4.
3.6
5
3.0
4.6
3.
45
5
4.3
4.25
4.3
3.9
4.05
2.0
5
3.8
2.5
5
3.7
3.3
5
3.5
3.5
3.0
Optimização
3.1
3.6
3.8
5
3.7
3.9
4.1
4
15
3.
3.4
4.15
4.2
2.0
3.
2
2.5
5
4.4
4.4
3.3
5
5
3.0
3
3.5
5
2.7
85
2.
2.5
9
2.
6
2.
55
2.
2
2.
4.0
133 / 218
Minimização de f (maximização de g)
> g <- function(x) { -f(x) } # problema de maximização
> nlm(g,c(2.6,3.3))
$minimum
[1] -4.666667
$estimate
[1] 2.666664 3.333330
$gradient
[1] 0.000000e+00 5.329075e-10
$code
[1] 1
$iterations
[1] 3
Optimização
134 / 218
Usando o gradiente
> g <- function(x) {
+ res <- (x[1]-x[1]^2/2)+(2*x[2]-x[2]^2/2)+x[1]*x[2]/2
+ attr(res, "gradient") <- -1.0*c((1-x[1])+x[2]/2,(2-x[2])+x[1]/2)
+ -res
+ }
> nlm(g,c(2.6,3.3))
$minimum
[1] -4.666667
$estimate
[1] 2.666667 3.333333
$gradient
[1] -2.220446e-16 2.220446e-16
$code
[1] 1
$iterations
[1] 3
Optimização
135 / 218
Usando o gradiente e a hessiana
>
+
+
+
+
+
g <- function(x) {
res <- (x[1]-x[1]^2/2)+(2*x[2]-x[2]^2/2)+x[1]*x[2]/2
attr(res, "gradient") <- -1.0*c((1-x[1])+x[2]/2,(2-x[2])+x[1]/2)
attr(res, "hessian") <- -1.0*matrix(c(-1.0, 0.5, 0.5, -1.0), 2, 2)
-res
}
Optimização
136 / 218
Usando o gradiente e a hessiana
> nlm(g,c(2.6,3.3),hessian=TRUE)
$minimum
[1] -4.666667
$estimate
[1] 2.666667 3.333333
$gradient
[1] -2.220446e-16 2.220446e-16
$hessian
[,1] [,2]
[1,] 1.0 -0.5
[2,] -0.5 1.0
$code
[1] 1
$iterations
[1] 1
Optimização
137 / 218
A resolução com optim (Nelder-Mead)
> fr <- function(x) (x[1]-x[1]^2/2)+(2*x[2]-x[2]^2/2)+x[1]*x[2]/2
> optim(c(2.6,3.3),fr,control=list(fnscale=-1.0))
$par
[1] 2.666414 3.333672
$value
[1] 4.666667
$counts
function gradient
39
NA
$convergence
[1] 0
$message
NULL
Optimização
138 / 218
A resolução com optim (quasi-Newton) sem gradiente
> optim(c(2.6,3.3),fr,method="BFGS",control=list(fnscale=-1.0))
$par
[1] 2.666667 3.333333
$value
[1] 4.666667
$counts
function gradient
6
4
$convergence
[1] 0
$message
NULL
Optimização
139 / 218
A resolução com optim (quasi-Newton) com gradiente
> gr <- function(x) c((1-x[1])+x[2]/2,(2-x[2])+x[1]/2)
> optim(c(2.6,3.3),fr,gr,method="BFGS",control=list(fnscale=-1.0))
$par
[1] 2.666667 3.333333
$value
[1] 4.666667
$counts
function gradient
5
4
$convergence
[1] 0
$message
NULL
Optimização
140 / 218
A resolução com optim (quasi-Newton) sem gradiente
> optim(c(2.6,3.3),fr,method="BFGS",
+
control=list(fnscale=-1.0,maxit=4))
$par
[1] 2.666667 3.333333
$value
[1] 4.666667
$counts
function gradient
4
4
$convergence
[1] 1
$message
NULL
Optimização
141 / 218
A solução do problema proposto
>
+
+
>
>
>
>
+
+
+
>
>
>
f <- function(x) {
(x[1]-x[1]^2/2)+(2*x[2]-x[2]^2/2)+x[1]*x[2]/2
}
x1=seq(2,4,0.1)
x2=seq(2,4,0.1)
z<-matrix(0,length(x1),length(x2))
for (i in 1:length(x1))
{ for (j in 1:length(x2))
{ z[i,j]<-f(c(x1[i],x2[j])) }
}
contour(x1,x2,z,50)
dim(sol$par) <- c(1,2)
points(sol$par,pch=24)
Optimização
142 / 218
4.0
Solução – Curvas de nível
4.3
5
4.4
35
4.
4.5
5
4.4
25
4.
4.65
4.5
3.5
4.5
1
4.
3.6
5
3.0
4.6
3.
45
5
4.3
4.25
4.3
3.9
4.05
2.0
5
3.8
2.5
5
3.7
3.3
5
3.5
3.5
3.0
Optimização
3.1
3.6
3.8
5
3.7
3.9
4.1
4
15
3.
3.4
4.15
4.2
2.0
3.
2
2.5
5
4.4
4.4
3.3
5
5
3.0
3
3.5
5
2.7
85
2.
2.5
9
2.
6
2.
55
2.
2
2.
4.0
143 / 218
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
144 / 218
Formulação geral
(3)
min f (x)
x∈Rn
s.a
c(x) = 0
em que f (x) e c(x) são funções não lineares em x.
f (x) : Rn → R
T
x = (x1 , x2 , . . . , xn )
c(x) : Rn → Rm
n é o número de variáveis do problema
m é o número de restrições de igualdade
c(x) = (c1 (x), c2 (x), . . . , cm (x))T
Vamos supor que f (x) e c(x) são funções duas vezes diferenciáveis.
Optimização
145 / 218
Exemplo
Exemplo 1
min ex1 x2 x3 x4 x5
x∈R5
s.a
x21 + x22 + x23 + x24 + x25 = 10
x2 x3 = 5x4 x5
x31 + x32 = −1
Optimização
146 / 218
Exemplo (cont.)
Temos então
f (x) = ex1 x2 x3 x4 x5
c1 (x) = x21 + x22 + x23 + x24 + x25 − 10
c2 (x) = x2 x3 − 5x4 x5
c3 (x) = x31 + x32 + 1
com n = 5 e m = 3.
Optimização
147 / 218
Notação
Gradiente de f (x) (vector de n elementos)
 ∂f 
∂x1

∇f (x) = 
..
.
∂f
∂xn


Hessiana de f (x) (matriz simétrica de n × n)
 ∂2f
...
∂x21

2
∇ f (x) =  . . .
∂2f
∂x1 ∂xn . . .
Optimização
∂2f
∂xn ∂x1

...


∂2f
∂x2n
148 / 218
Notação
Gradiente de c1 (x) (vector de n elementos)


∇c1 (x) = 
∂c1
∂x1
..
.
∂c1
∂xn



...
Gradiente de cm (x) (vector de n elementos)


∇cm (x) = 
∂cm
∂x1
..
.
∂cn
∂xn
Optimização



149 / 218
Notação
Matriz Jacobiano das restrições (matriz n × m)

∂c1
∂x1

∇c(x) =  ...
∂c1
∂xn
∂c2
∂x1
...
∂c2
∂xn
...
...
..
.
∂cm
∂x1
..
.
∂cm
∂xn



ou
∇c(x) = (∇c1 (x)∇c2 (x) . . . ∇cm (x))
Optimização
150 / 218
Notação
Hessiana de c1 (x) (matriz simétrica de n × n)


∇2 c1 (x) = 
∂ 2 c1
∂x21
...
...
∂ 2 c1
∂x1 ∂xn
...
...
∂ 2 c1
∂xn ∂x1

...


∂ 2 c1
∂x2n
Hessiana de cm (x) (matriz simétrica de n × n)


∇2 cm (x) = 
∂ 2 cm
∂x21
...
...
∂2c
m
∂x1 ∂xn
...
∂ 2 cm
∂xn ∂x1

...


∂2c
m
∂x2n
Existem m Hessianas das restrições (n × n).
Optimização
151 / 218
Seja λ um vector de m elementos (vector dos multiplicadores de Lagrange)
λ = (λ1 , λ2 , . . . , λm )T
A função Lagrangeana associada ao problema (3) é
L(x, λ) = f (x) − λT c(x)
m
X
= f (x) −
λi ci (x)
i=1
Optimização
152 / 218
Condição de regularidade
Seja x∗ uma solução do problema. Se os vectores ∇c1 (x∗ ), ∇c2 (x∗ ), . . . ,
∇cm (x∗ ) (gradientes das restrições, calculados na solução) forem
linearmente independentes, então x∗ é ponto regular.
Pergunta:
Como se verifica se um conjunto de vectores é linearmente independente
(em termos informáticos)?
Optimização
153 / 218
Condições necessárias e suficientes de 1a ordem
Seja x∗ uma solução do problema. Se x∗ é ponto regular, então existe um
λ∗ tal que
∇x L(x∗ , λ∗ ) = ∇f (x∗ ) − ∇c(x∗ )λ∗ = 0
n equações
e
∇λ L(x∗ , λ∗ ) = −c(x∗ ) = 0
m equações
Este sistema de n + m equações é não linear em x e define as condições
Kuhn-Tucker (KT).
O par (x∗ , λ∗ ) chama-se par KT.
Optimização
154 / 218
Interpretação das condições KT
∇λ L(x∗ , λ∗ ) = c(x∗ ) = 0
significa que o ponto verifica as restrições, ou seja, x∗ é ponto admissível.
∇x L(x∗ , λ∗ ) = ∇f (x∗ ) − ∇c(x∗ )λ∗ = 0
⇔ ∇f (x∗ ) = ∇c(x∗ )λ∗
m
X
⇔ ∇f (x∗ ) =
λ∗i ∇ci (x∗ )
i=1
significa que o gradiente de f (∇f ) é uma combinação linear dos
gradientes das restrições (das colunas de ∇c(x∗ )).
Pergunta:
Dado um x∗ como determinar os valores de λ∗ ?
Optimização
155 / 218
Exemplo
Exemplo 2
min f (x) ≡ x1 + x2
x∈R2
s.a
c(x) = x21 − x22 = 0
Considere x∗ = (1, −1)T e x̄ = (2, 2)T .
Tem-se que
1
2x1
∇f (x) =
e ∇c(x) =
1
−2x2
Optimização
156 / 218
Condições KT
Em x∗
Em x̄
∇f (x∗ )
=
1
1
2
2
2
2
1
1
4
−4
∇f (x̄) =
e
∇c(x∗ )
⇒
1
1
=
=
λ∗
∇c(x̄) =
∃ um λ∗ (λ∗ = 0.5)
⇒
1
1
= λ̄
4
−4
@ um λ̄
Optimização
157 / 218
Condição necessária de 2a ordem - Mínimo
Seja x∗ uma solução do problema. Se x∗ é ponto regular então para todos
os vectores s ∈ Rn que verificam ∇c(x∗ )T s = 0 (direcções tangentes às
curvas admissíveis), tem-se
sT ∇2xx L(x∗ , λ∗ )s ≥ 0.
Nota:
∇2xx L(x, λ)
2
= ∇ f (x) −
m
X
λi ∇2 ci (x)
i=1
Optimização
158 / 218
Condição suficiente de 2a ordem - Mínimo
Se (x∗ , λ∗ ) é um par KT, isto é, verifica as condições KT
∇x L(x∗ , λ∗ ) = 0
∇λ L(x∗ , λ∗ ) = 0
e se
sT ∇2xx L(x∗ , λ∗ )s > 0
para todo o s (s 6= 0) tal que
∇c(x∗ )T s = 0
então x∗ é minimizante local forte.
Optimização
159 / 218
O exemplo em x∗
∇2xx L(x∗ , λ∗ )
=
0 0
0 0
− 0.5
2 0
0 −2
=
−1 0
0 1
∇c(x∗ )T s = 0 ⇒ s1 = −s2
Como
T
s
∇2xx L(x∗ , λ∗ )s
= (−s2 , s2 )
−1 0
0 1
−s2
s2
=0
nada se pode concluir.
Problema:
Verificar as condições de optimalidade para o Exemplo 2 com x1 = (−1, 1),
x2 = (0, 0) e x3 = (−1, −1).
Optimização
160 / 218
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
161 / 218
Formulação geral:
(4)
min f (x)
x∈Rn
s.a
c(x) ≥ 0
em que f (x) e c(x) são funções não lineares em x.
f (x) : Rn → R
T
x = (x1 , x2 , . . . , xn )
c(x) : Rn → Rm
n é o número de variáveis do problema
m é o número de restrições de desigualdade
c(x) = (c1 (x), c2 (x), . . . , cm (x))T
Vamos supor que f (x) e c(x) são funções duas vezes diferenciáveis.
Optimização
162 / 218
Seja λ um vector de m elementos (vector dos multiplicadores de Lagrange)
λ = (λ1 , λ2 , . . . , λm )T
A função Lagrangeana associada ao problema (4) é
L(x, λ) = f (x) − λT c(x)
m
X
= f (x) −
λi ci (x)
i=1
Optimização
163 / 218
Restrições activas
Seja x̄ um ponto dado.
As restrições ci (x̄) ≥ 0, i ∈ A, dizem-se activas em x̄ se ci (x̄) = 0.
O conjunto A contém os índices das restrições activas.
Restrições activas
Poderíamos dizer que as restrições activas são aquelas que participam na
caracterização da solução. Enquanto que as não activas “não interessam”
para essa caracterização.
Optimização
164 / 218
Condição de regularidade
Seja x∗ uma solução do problema.
Se os vectores ∇ci (x∗ ), i ∈ A (gradientes das restrições activas, calculados
na solução) forem linearmente independentes, então x∗ é ponto regular.
Ponto regular
A definição é idêntica para o caso das restrições de igualdade, mas no caso
de problemas com restrições de desigualdade só as restrições activas é que
“contam”.
Optimização
165 / 218
Condições necessárias e suficientes de 1a ordem - Mínimo
Seja x∗ uma solução do problema. Se x∗ é ponto regular, então existe um
λ∗ tal que
∇x L(x∗ , λ∗ ) = ∇f (x∗ ) − ∇c(x∗ )λ∗ = 0
c(x∗ ) ≥ 0
ponto estacionário da Lag.
admissibilidade
λ∗ ≥ 0
“positiveness”
e
(λ∗ )T c(x∗ ) = 0
complementaridade
Optimização
166 / 218
A complementaridade ((λ∗ )T c(x∗ ) = 0) diz-nos que as restrições não
activas têm multiplicadores iguais a zero (ci (x∗ ) > 0 ⇒ λ∗i = 0, i ∈
/ A).
Para as restrições activas os multiplicadores de Lagrange correspondentes
podem ou não ser zero. Se forem zero estamos na presença de um
problema degenerado. No caso de não existirem multiplicadores iguais a
zero para as restrições activas diz-se que a complementaridade é estrita.
c(x∗ ) ≥ 0
significa que o ponto verifica as restrições, ou seja, x∗ é ponto admissível.
Optimização
167 / 218
∇x L(x∗ , λ∗ ) = ∇f (x∗ ) − ∇c(x∗ )λ∗ = 0
⇔ ∇f (x∗ ) = ∇c(x∗ )λ∗
m
X
⇔ ∇f (x∗ ) =
λ∗i ∇ci (x∗ )
i=1
significa que o gradiente de f (∇f ) é uma combinação linear dos
gradientes das restrições (das colunas de ∇c(x∗ ).
Nota:
As restrições inactivas não influenciam, uma vez que λ∗i = 0, i ∈
/ A.
Optimização
168 / 218
Exemplo (Nash&Sofer)
Exemplo
min f (x) ≡ x1
x∈R2
s.a
(x1 + 1)2 + x22 ≥ 1
x21 + x22 ≤ 2
√
Considere x1 = (0, 0)T , x2 = (−1, −1)T e x3 = (0, 2)T .
Tem-se que
(x1 + 1)2 + x22 − 1
L(x, λ) = x1 − (λ1 , λ2 )
2 − x21 − x22
= x1 − λ1 (x1 + 1)2 + x22 − 1 + λ2 x21 + x22 − 2
Optimização
169 / 218
Condições KT
Logo
∇x L(x, λ) =
1 − 2λ1 (x1 + 1) + 2λ2 x1
−2λ1 x2 + 2λ2 x2
Para x1 = (0, 0)T apenas a primeira restrição está activa, logo λ2 = 0.
Resolvendo ∇x L(x1 , λ) = 0 em ordem a λ1 vem
1
1 − 2λ1 = 0
⇒ λ1 =
0
=0
2
Optimização
170 / 218
Para x2 = (−1, −1)T ambas as restrições estão activas e resolvendo
∇x L(x2 , λ) = 0 em ordem aos multiplicadores de Lagrange obtemos
1
1 − 2λ2
=0
⇒ λ1 = λ2 =
2λ1 − 2λ2 = 0
2
√
Para x3 = (0, 2)T apenas a segunda restrição está activa e resolvendo
∇x L(x3 , λ) = 0 em ordem a λ2 (λ1 = 0) obtemos
1 +√
2λ2 (0) = 0
2λ2 2
=0
que é um sistema inconsistente e consequentemente x3 não satisfaz as
condições de optimalidade de primeira ordem.
Optimização
171 / 218
Condição necessária de 2a ordem - Mínimo
Seja x∗ uma solução do problema. Se x∗ é ponto regular então para todos
os vectores s ∈ Rn que verificam ∇C(x∗ )T s = 0, em que C(x∗ ) é uma
matriz formada pelas restrições activas em x∗ (direcções tangentes às
curvas admissíveis), tem-se
sT ∇2xx L(x∗ , λ∗ )s ≥ 0.
Nota
Condição idêntica à apresentada para os problemas com restrições de
igualdade, mas apenas se considera as restrições activas no caso das
desigualdades.
Optimização
172 / 218
Condição suficiente de 2a ordem - Mínimo
Se (x∗ , λ∗ ) é um par KT, isto é, verifica as condições KT
∇x L(x∗ , λ∗ ) = 0
∇λ L(x∗ , λ∗ ) = 0
e se
sT ∇2xx L(x∗ , λ∗ )s > 0
para todo o s (s 6= 0) tal que
∇C+ (x∗ )T s = 0
então x∗ é minimizante local forte.
C+ é uma matriz formada pelas restrições activas não degeneradas
(multiplicadores diferentes de zero).
Optimização
173 / 218
O exemplo em x1
∇2xx L(x, λ)
=
2(λ2 − λ1 )
0
0
2(λ2 − λ1 )
Logo para x1 = (0, 0)T e λ1 = ( 12 , 0)T temos que
∇2xx L(x, λ) =
−1 0
0 −1
1
Como ∇C(x1 ) = (2, 0)T temos s = (0, s2 )T e consequentemente
−1 0
0
(0, s2 )
= −s22 ≤ 0 (s2 6= 0)
0 −1
s2
Logo x1 não é mínimo local. Não é máximo local porque λ1 ≥ 0.
1
definida negativa
Optimização
174 / 218
O exemplo em x2
0 −2
Como
=
tem-se que @s 6= 0 : ∇C(x2 )T s = 0 e a
2 2
condição suficiente é verificada trivialmente.
∇C(x2 )
Nota
λ1 = λ2 =
1
2
Optimização
175 / 218
Conteúdo
1
Introdução
2
Optimização
3
4
R - Introdução
5
6
7
8
9
10
Optimização
176 / 218
Funções R
O R fornece um conjunto de funções para optimização linear e não linear
das quais se destacam:
solveLP - Optimização linear (Pacote linprog);
constrOptim - Optimização não linear com restrições lineares;
Rdonlp2 ou Rsolnp2 - Optimização não linear com restrições.
Optimização
177 / 218
Exemplo linear
Uma empresa procede à montagem de quatro produtos (1, 2, 3, 4) a partir de
componentes entregues. O lucro por unidade para cada produto (1, 2, 3, 4) é 10,
15, 22, 17 euros, respectivamente. O pedido máximo na próxima semana para
cada produto (1, 2, 3, 4) é 50, 60, 85 e 70 unidades, respectivamente.
Existem três estados (A, B, C) na montagem manual de cada produto e as
horas-homem necessárias para cada estado por unidade de produto são
Estado
A
B
C
1
2
2
3
Produto
2 3
2 1
4 1
6 1
4
1
2
5
O tempo disponível na próxima semana para a montagem em cada estado (A, B,
C) é 160, 200 e 80 homens-hora, respectivamente.
É possível variar os homens-hora que montam em cada estado tal que os
trabalhadores no estado B possam passar até 20% do seu tempo no estado A e os
trabalhadores do estado C possam passar até 30% do seu tempo no estado A.
Restrições de produção obrigam a que a razão (número de unidade do produto
1)/(número de unidades do produto 4) tem que estar entre 0.9 e 1.15.
Optimização
178 / 218
Exemplo linear – formulação
Variáveis: xi – quantidade do produto i = 1, 2, 3, 4 produzida, tBA –
quantidade de tempo transferido de B para A, tCA – quantidade de tempo
transferido de C para A.
Restrições de capacidade máxima: x1 ≤ 50, x2 ≤ 60, x3 ≤ 85, x4 ≤ 70
Restrição de razão: 0.9 <= (x1/x4) <= 1.15, i.e., 0.9x4 ≤ x1 e
x1 ≤ 1.15x4
Restrições do tempo de trabalho:
2x1 + 2x2 + x3 + x4 ≤ 160 + tBA + tCA ,
2x1 + 4x2 + x3 + 2x4 ≤ 200 − tBA , 3x1 + 6x2 + x3 + 5x4 ≤ 80 − tCA
Limites nas transferências: tBA ≤ 0.2(200), tC A ≤ 0.3(80)
Limites simples: xi ≥ 0, i = 1, 2, 3, 4
Função objectivo: max 10x1 + 15x2 + 22x3 + 17x4
Ignora-se o facto das variáveis xi , i = 1, 2, 3, 4 terem de ser inteiras.
Optimização
179 / 218
O problema linear
min
x∈R6
− 10x1 − 15x2 − 22x3 − 17x4
s.a 0 ≤ x1 ≤ 50
0 ≤ x2 ≤ 60
0 ≤ x3 ≤ 85
0 ≤ x4 ≤ 70
0 ≤ x5 ≤ 40
0 ≤ x6 ≤ 24
− x1 + 0.9x4 ≤ 0
x1 − 1.15x4 ≤ 0
2x1 + 2x2 + x3 + x4 − x5 − x6 ≤ 160
2x1 + 4x2 + x3 + 2x4 + x5 ≤ 200
3x1 + 6x2 + x3 + 5x4 + x6 ≤ 80
Optimização
180 / 218
O problema linear – Forma matricial
(−10, −15, −22, −17, 0, 0)x


 
50
0
 60 
 0 


 
 85 
 0 




s.a   ≤ x ≤ 

70
0


 
 40 
 0 
24
0



−1 0 0
0.9
0
0
 1 0 0 −1.15

0
0 



 2 2 1


1
−1
−1
x
≤



 2 4 1


2
1
0
3 6 1
5
0
1
min
x∈R6
Optimização
0
0
160
200
80






181 / 218
R solveLP
Load do pacote
Não esquecer de fazer load do pacote linprog
>
>
>
+
+
+
+
+
>
cvec <- c(-10, -15, -22, -17, 0, 0)
bvec <- c(50, 60, 85, 70, 40, 24, 0, 0, 160, 200, 80)
Amat <- rbind(diag(length(cvec)),
c(-1, 0, 0, 0.9, 0, 0),
c(1, 0, 0, -1.15, 0, 0),
c(2, 2, 1, 1, -1, -1),
c(2, 4, 1, 2, 1, 0),
c(3, 6, 1, 5, 0, 1))
solveLP( cvec, bvec, Amat, maximum=FALSE, maxiter=1000)
Optimização
182 / 218
R solveLP - Output
Results of Linear Programming / Linear Optimization
Objective function (Minimum):
[1] -1760
Iterations in phase 1: 0
Basic Variables
opt
3
80 # Variável != zero
S 1
50 # Variáveis de folga
S 2
60
S 3
5
S 4
70
S 5
40
S 6
24
S 7
0
S 8
0
S 9
80
S 10 120
Optimização
183 / 218
R solveLP - Output
Constraints
max actual diff dual price dual.reg
1
50
0
50
0
50
2
60
0
60
0
60
3
85
80
5
0
5
4
70
0
70
0
70
5
40
0
40
0
40
6
24
0
24
0
24
7
0
0
0
0
NA
8
0
0
0
0
NA
9 160
80
80
0
80
10 200
80 120
0
120
11 80
80
0
-22
80
Optimização
184 / 218
R solveLP - Output
All Variables (including slack variables)
opt
c
min c
max c marg. marg.reg.
1
0 -10 -66.0000
Inf
56
26.6667
2
0 -15 -132.0000
Inf
117
13.3333
3
80 -22
-Inf -3.400
NA
NA
4
0 -17 -110.0000
Inf
93
16.0000
5
0
0
0.0000
Inf
0
40.0000
6
0
0 -22.0000
Inf
22
24.0000
S 1
50
0
-Inf 56.000
0
50.0000
S 2
60
0
-Inf 117.000
0
60.0000
S 3
5
0 -18.6000
NA
0
5.0000
S 4
70
0
-Inf 93.000
0
70.0000
S 5
40
0
-Inf
Inf
0
40.0000
S 6
24
0
-Inf 22.000
0
24.0000
S 7
0
0 -56.0000 103.333
0
NA
S 8
0
0 -80.8696 56.000
0
NA
S 9
80
0 -11.0000
NA
0
80.0000
S 10 120
0 -22.0000
NA
0 120.0000
S 11
0
0
NA
NA
22
80.0000
Optimização
185 / 218
Interpretação geométrica de um problema
Suponhamos que um agricultor tem um pedaço de terra de área Akm2 ,
para ser semeado com trigo ou cevada ou uma combinação de ambas. O
fazendeiro tem uma quantidade limitada de fertilizante F permitido e de
insecticida P permitido que podem ser usados. Cada um deles sendo
necessários em quantidades diferentes por unidade de área para o trigo
(F1 , P1 ) e para a cevada (F2 , P2 ). Seja S1 o preço de venda do trigo, e S2
o da cevada. Se chamarmos à área plantada com trigo e cevada de x1 e
x2 , respectivamente, então o número óptimo de quilómetros quadrados de
plantação com trigo vs cevada pode ser formulado como o seguinte
problema de programação linear:
max S1 x1 + S2 x2
(lucro)
x1 + x2 ≤ A (limite da área total)
s.a
F1 x1 + F2 x2 ≤ F
(limite do fertilizante)
P1 x1 + P2 x2 ≤ P
(limite do insecticida)
x1 , x2 ≥ 0 (área não negativa)
Optimização
186 / 218
S1 = 2, S2 = 1.5, A = 10, F = 9, P = 45, (F1 , P1 ) = (0.5, 6),
(F2 , P2 ) = (1.7, 1)
> cvec=c(-2, -1.5)
> Amat=rbind(c(1,1), c(0.5, 1.7), c(6, 1))
> bvec=c(10, 9, 45)
> solveLP( cvec, bvec, Amat, maximum=FALSE, maxiter=1000)
Results of Linear Programming / Linear Optimization
Objective function (Minimum):
[1] -18.5
Basic Variables
opt
1
7.0
2
3.0
S 2 0.4
Optimização
187 / 218
Constraints
max actual diff dual price dual.reg
1 10
10.0 0.0
-1.4 2.50000
2
9
8.6 0.4
0.0 0.40000
3 45
45.0 0.0
-0.1 1.66667
All Variables (including slack variables)
opt
c
min c
max c marg. marg.reg.
1
7.0 -2.0 -9.00000 -1.500000
NA
NA
2
3.0 -1.5 -2.00000 -0.333333
NA
NA
S 1 0.0 0.0
NA
NA
1.4
2.50000
S 2 0.4 0.0 -0.72165 0.416667
0.0
0.40000
S 3 0.0 0.0
NA
NA
0.1
1.66667
Optimização
188 / 218
> f <- function(x) { sum(c(-2,-1.5)*x) }
> constrOptim(c(0,0), f, NULL, ui=-Amat, ci=-bvec)
$par
[1] 6.999975 3.000025
$value
[1] -18.49999
$counts
function gradient
169
NA
$convergence
[1] 0
$message
NULL
$outer.iterations
[1] 5
$barrier.value
[1] -0.006323227
Optimização
189 / 218
> g <- function(x) { c(-2,-1.5) }
> constrOptim(c(0,0), f, g, ui=-Amat, ci=-bvec)
$par
[1] 6.99999 3.00001
$value
[1] -18.49999
$counts
function gradient
18
1
$convergence
[1] 0
$message
NULL
$outer.iterations
[1] 10
$barrier.value
[1] -0.006323294
Optimização
190 / 218
>
>
>
>
>
>
>
>
x1 <- seq(0,10,0.1)
x2 <- seq(0,10,0.1)
z <- outer(x1,x2,f <- function(x1,x2) -x1-1.5*x2)
contour(x1,x2,z,20,method=’edge’)
lines(c(0,10),c(10,0),col=’red’,lwd=2)
lines(c(0,10),c(5.29,2.35),col=’red’,lwd=2)
lines(c(0,10),c(45,-15),col=’red’,lwd=2)
text(3,2,"Região admissível",cex=2,font=2,col=’blue’)
Optimização
191 / 218
10
-15
-16
-17
-18
-19
-20
-21
-22
-23
-24
-14
8
-13
-12
-11
6
-10
-9
4
x2
-8
-6
2
-5
-3
Região admissível
-2
-1
0
-4
0
2
-7
4
6
8
10
x1
Optimização
192 / 218
Exemplo de programação quadrática
Problema quadrático
min −x1 x3 − x2 x4
x∈[0,5]3
s.a
0 ≤ x1 + x2 − 2.5 ≤ 5.0
0 ≤ x1 + x3 − 2.5 ≤ 5.0
0 ≤ x1 + x4 − 2.5 ≤ 5.0
0 ≤ x2 + x3 − 2.0 ≤ 5.0
0 ≤ x2 + x4 − 2.0 ≤ 5.0
0 ≤ x3 + x4 − 1.5 ≤ 5.0
x1 + x2 + x3 + x4 − 5.0 ≥ 0
com x0 = (0, 0, 0)T .
Optimização
193 / 218
Exemplo de programação quadrática - AMPL (curiosidade)
var x{1..4} >= 0.0, <= 5.0, := 0.0;
minimize f:
(-x[1]*x[3]-x[2]*x[4]);
subject to cons1:
0 <= x[1]+x[2] -2.5 <= 5.0;
subject to cons2:
0 <= x[1]+x[3] -2.5 <= 5.0;
subject to cons3:
0 <= x[1]+x[4] -2.5 <= 5.0;
subject to cons4:
0 <= x[2]+x[3] -2.0 <= 5.0;
subject to cons5:
0 <= x[2]+x[4] -2.0 <= 5.0;
subject to cons6:
0 <= x[3]+x[4] -1.5 <= 5.0;
subject to cons7:
x[1]+x[2]+x[3]+x[4]-5.0 >= 0;
Optimização
194 / 218
Exemplo em R
>
>
+
>
>
>
>
>
f <- function(x) { -x[1]*x[3]-x[2]*x[4]}
A <- rbind(c(1, 1, 0, 0), c(1, 0, 1, 0), c(1, 0, 0, 1),
c(0, 1, 1, 0), c(0, 1, 0, 1), c(0, 0, 1, 1))
bl <- c(2.5, 2.5, 2.5, 2.0, 2.0, 1.5)
bu <- c(7.5, 7.5, 7.5, 7.0, 7.0, 6.5)
Amat <- rbind(A, -A, c(1, 1, 1, 1))
bvec <- c(bl, -bu, 5)
constrOptim(c(2.5, 0.1, 2, 2.5), f, NULL, Amat, bvec)
Optimização
195 / 218
Exemplo em R
$par
[1] 4.195106 3.304894 3.195810 3.304190
$value
[1] -24.32676
$counts
function gradient
219
NA
$convergence
[1] 0
$message
NULL
$outer.iterations
[1] 14
$barrier.value
[1] -0.005053065
Optimização
196 / 218
Exemplo em R com derivadas
> g <- function(x) { c(-x[3], -x[4], -x[1], -x[2]) }
> constrOptim(c(2.5, 0.1, 2, 2.5), f, g, Amat, bvec,
+ method=’BFGS’)
$par
[1] 4.012254 3.487746 3.487742 3.012258
$value
[1] -24.49970
$counts
function gradient
19
1
$convergence
[1] 0
$message
NULL
$outer.iterations
[1] 17
$barrier.value
[1] -0.0050707
Optimização
197 / 218
Exemplo não linear com restrições
Caixa
Pretende-se construir uma caixa cujo comprimento da base é 3 vezes a
largura da base. O material usado para construir o topo e base da caixa
custa 10e/m2 e o material usado para construir as paredes laterais custa
6e/m2 . Se a caixa tiver um volume de 50m3 determine as dimensões da
caixa que minimiza o custo total de construção da caixa.
Optimização
198 / 218
Formulação
Função objectivo
Pretende-se minimizar o custo da caixa, i.e.:
Custo da tampa e fundo: 10 × 2 × (3 × w × w) = 60w2 ;
custo lateral: 6 × (2 × h × 3 × w + 2 × h × w) = 48hw;
Custo total: 60w2 + 48hw;
Restrição
Volume da caixa igual a 50, i.e., 3w2 h = 50.
Todas as medidas devem ser positivas, i.e., w > 0, h > 0.
Optimização
199 / 218
Formulação
Formulação matemática do problema
Usando w → x1 , h → x2 ,
min 60x21 + 48x1 x2
s.a 3x21 x2 − 50 = 0
x1 , x2 ≥ 0
Optimização
200 / 218
O pacote Rdonlp2 e Rsolnp2
Localização do pacote
Os pacotes podem ser obtidos de
http://r-forge.r-project.org/R/?group_id=156. Consistem num
ficheiro zip (para Windows e Mac).
Instalação do pacote
Usar o menu Packages -> Install package(s) from local zip
files...
Usar o pacote
Usar o menu Packages -> Load package...
Optimização
201 / 218
Rdonlp2
A versão actual tem problemas de
compatibilidade com o R2.10
Optimização
202 / 218
Resolução - Sem derivadas
>
>
>
>
>
>
>
>
init <- c(3,1.85)
lb <- c(0,0)
ub <- c(Inf, Inf)
f <- function(x) {60*x[1]^2+48*x[1]*x[2]}
con <- list(c1 = function(x) {3*x[1]^2*x[2]})
clb <- 50
cub <- 50
donlp2(init, f, ub, lb, NULL, 0, 0, con, cub, clb)
1 fx=
8.064000e+02 upsi= 5.0e-02 b2n= 1.7e+02 umi= 0.0e+00
...
22 fx=
6.375956e+02 upsi= 2.0e-06 b2n= 2.2e-01 umi= 0.0e+00
n=
2
nlin=
0
nonlin=
1
epsx= 1.000e-05 sigsm= 1.490e-08
startvalue
3.0000000e+00
1.8500000e+00
eps= 2.22e-16 tol= 2.23e-308 del0= 1.00e+00 delm= 1.00e-06 tau
...
taubnd= 1.00e+00 epsfcn= 1.00e-16 difftype=3
Optimização
203 / 218
Resolução
termination reason:
KT-conditions satisfied, no further correction computed
evaluations of f
32
evaluations of grad f
23
evaluations of constraints
62
evaluations of grads of constraints
23
final scaling of objective
9.638171e-02
norm of grad(f)
4.606398e+02
lagrangian violation
3.457676e-03
feasibility violation
3.512710e-10
dual feasibility violation
0.000000e+00
optimizer runtime sec’s
1.200000e-02
optimal value of f =
optimal solution x =
1.88209881291260e+00
6.37595141635430e+02
4.70504637147189e+00
Optimização
204 / 218
Resolução
multipliers are relativ to scf=1
nr.
constraint
multiplier norm(grad) or 1
1
1.8820988e+00
0.0000000e+00
2
1.0000000e+20
0.0000000e+00
3
4.7050464e+00
0.0000000e+00
4
1.0000000e+20
0.0000000e+00
5 -3.5127101e-10
8.5012686e+00
5.4184486e+01
6
3.5127101e-10
0.0000000e+00
evaluations of restrictions and their gradients
(
62,
23)
last estimate of cond.nr. of active gradients
1.000e+00
last estimate of cond.nr. of approx.
Optimização
hessian
1.505e+01
205 / 218
Resolução - Com derivadas
init <- c(3,1.85)
lb <- c(0,0)
ub <- c(Inf, Inf)
f <- function(x) {60*x[1]^2+48*x[1]*x[2]}
fgr <- function(x) {c(120*x[1]+48*x[2], 48*x[1])}
attr(f, "gr") <- fgr
con <- function(x) {3*x[1]^2*x[2]}
congr <- function(x){c(6*x[1]*x[2],3*x[1]^2)}
attr(con, "gr") <- congr
clb <- 50
cub <- 50
cntl <- donlp2.control(del0=0.2, tau0=1.0, tau=0.1, taubnd=5e-6
donlp2(init, f, ub, lb, NULL, 0, 0, list(con), cub, clb,control
Optimização
206 / 218
Algumas notas
Notas
DONLP2 is a sequential quadratic programming method incorporating
the exact l1- merit function and a special BFGS quasi-Newton
approximation to the Hessian.
Se o problema anterior tiver como aproximação inicial (0, 0)T o
algoritmo não converge.
Cada algoritmo deve ser escolhido de de acordo com o problema a ser
resolvido.
Optimização
207 / 218
solnp2 - Resolução - Sem derivadas
> init <- c(1,1)
> lb <- c(0,0)
> ub <- c(Inf, Inf)
> f <- function(x) {60*x[1]^2+48*x[1]*x[2]}
> con <- function(x) {3*x[1]^2*x[2]}
> solnp(init, f, NULL, con, c(50), LB=lb, UB=ub)
Iter: 1 fn: 5202.2375
Pars: 9.22612 0.21442
Iter: 2 fn: 3974.6386
Pars: 8.03927 0.25097
Iter: 3 fn: 3363.3620
Pars: 7.36810 0.29978
Iter: 4 fn: 2554.2094
Pars: 6.37118 0.38812
Iter: 5 fn: 1317.6021
Pars: 4.43467 0.64653
Iter: 6 fn: 840.9256
Pars: 3.30216 1.17769
Iter: 7 fn: 576.7865
Pars: 2.33834 2.21593
Iter: 8 fn: 603.7913
Pars: 2.04109 3.61150
Iter: 9 fn: 622.3064
Pars: 1.86265 4.63207
Iter: 10 fn: 637.7800
Pars: 1.88243 4.70545
Iter: 11 fn: 637.5952
Pars: 1.88207 4.70518
Iter: 12 fn: 637.5951
Pars: 1.88207 4.70518
solnp--> Completed in 12 iterations
Optimização
208 / 218
Resolução - cont.
$pars
[1] 1.882072 4.705179
$convergence
[1] 0
$values
[1] 108.0000 5202.2375 3974.6386 3363.3620 2554.2094 1317.602
[8] 576.7865 603.7913 622.3064 637.7800 637.5952 637.595
$lagrange
[,1]
[1,] 8.501269
Optimização
209 / 218
Resolução - cont.
$hessian
[,1]
[,2]
[1,] 63.14883 -12.191559
[2,] -12.19156
7.478598
$ineqx0
NULL
$nfuneval
[1] 309
$outer.iter
[1] 12
$elapsed
Time difference of 0.1570001 secs
Optimização
210 / 218
Algumas notas
Notas
Nonlinear optimization using augmented lagrange method.
Se o problema anterior tiver como aproximação inicial (3, 1.85)T o
algoritmo não converge!!
Não faz o tratamento das restrições lineares de forma isolada.
Optimização
211 / 218
Interpretação geométrica do problema
7
6.5
Restrição de igualdade
6
5.5
Solução óptima
5
4.5
4
3.5
3
1
1.5
2
2.5
3
Optimização
3.5
4
4.5
5
212 / 218
E as dimensões da caixa?
Caixa
A base da caixa tem de dimensão 1.8821 × 5.6462.
A altura da caixa é 4.7052.
O seu custo é 637.5951e.
O volume é 1.8821 × 5.6462 × 4.7052 = 50.0000
Optimização
213 / 218
Resolução do problema com apenas restrições lineares
O problema
max 2x1 + 1.5x2
s.a x1 + x2 ≤ 10
0.5x1 + 1.7x2 ≤ 9
6x1 + x2 ≤ 45
x1 , x2 ≥ 0
Optimização
214 / 218
>
>
>
>
>
>
>
>
>
>
+
init <- c(0,0)
lb <- c(0,0)
f <- function(x) {2*x[1]+1.5*x[2]}
fgr <- function(x) {c(2, 1.5)}
attr(f, "gr") <- fgr
A <- rbind(c(1, 1), c(0.5, 1.7), c(6, 1))
ulb <- c(10, 9, 45)
llb <- c(-Inf, -Inf, -Inf)
cntl <- donlp2.control(fnscale=-1)
donlp2(par=init, fn=f, par.lower=lb, A=A,
lin.upper=ulb, lin.lower=llb,control=cntl)
Optimização
215 / 218
1 fx= -0.000000e+00 upsi= 0.0e+00 b2n= 0.0e+00 umi=
... 6 fx= -1.878866e+01 upsi= 2.1e-01 b2n= 2.5e-01 umi=
n=
2
nlin=
3
nonlin=
0
epsx= 1.000e-05 sigsm= 1.490e-08
startvalue
0.0000000e+00
0.0000000e+00
...
termination reason:
KT-conditions satisfied, no further correction computed
evaluations of f
9
evaluations of grad f
7
evaluations of constraints
42
evaluations of grads of constraints
0
final scaling of objective
1.000000e+00
norm of grad(f)
2.500000e+00
lagrangian violation
4.959246e-16
feasibility violation
0.000000e+00
dual feasibility violation
0.000000e+00
optimizer runtime sec’s
-8.000000e-03
Optimização
0.0e+00
0.0e+00
216 / 218
optimal value of f = -1.85000000000000e+01
optimal solution x =
7.00000000000000e+00 3.00000000000000e+00
multipliers are relativ to scf=1
nr.
constraint
multiplier norm(grad) or 1
1
7.0000000e+00
0.0000000e+00
2
1.0000000e+20
0.0000000e+00
3
3.0000000e+00
0.0000000e+00
4
1.0000000e+20
0.0000000e+00
5
1.0000000e+20
0.0000000e+00
1.4142136e+00
6
0.0000000e+00
1.4000000e+00
7
1.0000000e+20
0.0000000e+00
1.7720045e+00
8
4.0000000e-01
0.0000000e+00
9
1.0000000e+20
0.0000000e+00
6.0827625e+00
10
0.0000000e+00
1.0000000e-01
evaluations of restrictions and their gradients
(
14,
0) (
14,
0) (
14,
0)
last estimate of cond.nr. of active gradients
7.400e+00
last estimate of cond.nr. of approx. hessian
1.000e+00
Optimização
217 / 218
Fim
Fim
FIM
Optimização
218 / 218

Rascunho dos acetatos das aulas - norg

Transcrição

Documentos relacionados

para imprimir

Saiba mais - g3p Consultores de gestão, lda

anexo III - Areas funcionais.XLS

PORTUGAL E O PROCESSO DE HARMONIZAÇÃO

Resumo da Tese de Mestrado

Universidade do Minho

Versão para impressão deste case

Instalação do cliente vpnc versão 0.4.0 em Linux

BC1439 – Introdução à bioinformática

Nº 52 - Escola de Engenharia