190
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 2007/2008 A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 1 / 190

Bioinformática Avançada e Biologia de Sistemas -- Optimização · Bioinformática Avançada e Biologia de Sistemas – Optimização A. Ismael F. Vaz Departamento de Produção

Embed Size (px)

Citation preview

Bioinformática Avançada e Biologia de Sistemas –Optimização

A. Ismael F. Vaz

Departamento de Produção e SistemasEscola de Engenharia

Universidade do [email protected]

Mestrado em Bioinformática

Ano lectivo 2007/2008

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 1 / 190

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 2 / 190

Introdução

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 3 / 190

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 atendimentoMarcação por email.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 4 / 190

Introdução

Apresentação - Disciplina

Página da disciplina;

www.norg.uminho.pt/aivaz

Três fichas TPs para resolver ao longo desta parte do módulo (Notamí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 decálculo própria.

É obrigatória a presença em 2/3 das aulas efectivas (1/3 de faltas –atenção às justificações/estatutos).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 5 / 190

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 MATLAB + toolbox de Optimização (+ AMPL + Solver);

Fichas TPs e acetatos disponíveis na página;www.norg.uminho.pt/aivaz

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 6 / 190

Introdução

Motivação da disciplina

OptimizaçãoA optimização é uma área da matemática aplicada com inúmerasaplicaçõ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çãosemi-contínua (etanol, cerveja!!), etc... e astrofísica.

Engenharia

Está presente em todas as áreas da engenharia (sem excepção)...

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 7 / 190

Introdução

Controlo óptimo - Um exemplo

Problema de optimização do processo semi-contínuo de produção deEtanol.O problema de optimização é: (t0 = 0 e tf = 61.2 dias)

maxu(t)

J(tf ) ≡ x3(tf )x4(tf )

s.adx1

dt= g1x1 − u

x1

x4

dx2

dt= −10g1x1 + u

150− x2

x4

dx3

dt= g2x1 − u

x3

x4

dx4

dt= u

0 ≤ x4(tf ) ≤ 2000 ≤ u(t) ≤ 12∀t ∈ [t0, tf ]

com

g1 =(

0.4081 + x3/16

)(x2

0.22 + x2

)g2 =

(1

1 + x3/71.5

)(x2

0.44 + x2

)onde x1, x2 e x3 são as concentrações damassa celular, substrato e produto (g/L),e x4 é o volume (L). As condições iniciaissão:

x(t0) = (1, 150, 0, 10)T .

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 8 / 190

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;

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 9 / 190

Introdução

Programa detalhadoAula Matéria1 Grafos (Cláudio Alves)2 Optimização Combinatória (Cláudio Alves)3

Ficha de avaliação. Introdução ao MATLAB. Definição de vectorese matrizes. Codificação de funções matemáticas e operadores. Usode ficheiros M (M-Files).

4 Introdução à optimização não linear (sem restrições). Definições econdições de optimalidade.

5 Método de Newton e quasi-Newton. Modelação de casos em MA-TLAB (função fminsearch e fminunc).

6Ficha de Avaliação. Introdução à optimização não linear com res-trições. Tipos de problemas e suas características. Condições deoptimalidade. Tratamento de restrições lineares e não lineares.

7 Modelação de casos e uso de MATLAB (função fmincon).8 Modelação de casos e uso de MATLAB (função fmincon).9 Revisões.10 Revisões e Ficha de avaliação.A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 10 / 190

MATLAB

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 11 / 190

MATLAB

O que é o MATLAB?

MATLABComeçou como sendo um programa iterativo para cálculos com matrizes etransformou-se numa linguagem matemática de alto nível.O seu desenvolvimento permite agora, por exemplo, a resolução deequações diferenciais e o desenho de gráficos a duas e três dimensões.Possuindo o MATLAB uma linguagem de programação poder-se-ia dizerque qualquer algoritmo pode ser implementado em MATLAB.

O que aprender?Neste caso apenas iremos introduzir os comandos básicos e a criação descripts necessários aos capítulos seguintes.O MATLAB possui uma toolbox (entre outras) que fornece um conjunto dealgoritmos para optimização.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 12 / 190

MATLAB

Só existe o MATLAB?

Ferramentas similaresOutros programas similares são o Mathematica e o Maple

MathematicaMais vocacionado para manipulação simbólica, embora o MATLABtambém já incorpore algumas destas funcionalidades.

Maple – ExemploResolver a equação diferencial com condições iniciais

d2y

dx2(x)− 3y(x) = x, y(0) = 1

dy

dx(0) = 2

dsolve( diff(y(x),x,x) - 3*y(x) = x, y(0)=1, D(y)(0)=2, y(x) );

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 13 / 190

MATLAB

Ambiente MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 14 / 190

MATLAB

Operações básicas

Aritméticas>> 2+3*2-1.5*2^2ans =

2

ans é uma variável built-in que é criada sempre que um resultado não éatribuído.

Variáveis built-in – constantes>> pians =

3.1416

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 15 / 190

MATLAB

Operações básicas

Funções>> a=2*sin(pi)^2+3*exp(1)+sqrt(2)+cosh(2)a =

13.3313

Ajuda>> help acosACOS Inverse cosine.

ACOS(X) is the arccosine of the elements of X. Complexresults are obtained if ABS(x) > 1.0 for some element.

See also cos, acosd....

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 16 / 190

MATLAB

Operações básicas – Formatos

PrecisãoO MATLAB usa sempre aritmética com precisão de 15 algarismossignificativos, no entanto, por defeito apenas mostra 4.

>> format long>> aa =

13.33125473883387>> format short>> aa =

13.3313>> format short e>> aa =

1.3331e+001A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 17 / 190

MATLAB

Operações básicas com escalares

O ;Os comandos que terminam com o ; não são impressos no ecrã.

>> a=log(2)+log10(2)+log2(2);>> aa =

1.9942>> a=log(2)+log10(2)+log2(2)a =

1.9942

Útil quando se pretende efectuar vários comandos seguidos (scripts) e nãose pretende ver determinados resultados.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 18 / 190

MATLAB

Operações básicas com vectores e matrizes

Vectores linha>> a=[1 2 3]a =

1 2 3>> a=[1,2,3]a =

1 2 3

Vectores coluna>> a=[1;2;3]a =

123

O(A) transposto(a)

>> a=[1;2;3]’a =

1 2 3

O(A) transposto(a)

>> a=[1,2,3]’a =

123

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 19 / 190

MATLAB

Operações básicas com vectores e matrizes

Operações com vectores – Funções>> aa =

1 2 3>> b=sin(a)b =

0.8415 0.9093 0.1411

Operações com vectores>> a+bans =

1.8415 2.9093 3.1411>> a^2??? Error using ==> mpowerMatrix must be square.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 20 / 190

MATLAB

Operações básicas com vectores e matrizes

Operações elemento a elemento>> a.^2ans =

1 4 9>> (a+b).^2ans =

3.3910 8.4640 9.8666>> a.*bans =

0.8415 1.8186 0.4234

Operações com vectores>> 2*a+b.^2ans =

2.7081 4.8268 6.0199

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 21 / 190

MATLAB

Operações básicas com vectores e matrizes

Operações elemento a elemento>> a*b??? Error using ==> mtimesInner matrix dimensions must agree.>> a*b’ans =

3.0834

Operações com vectores>> a’*bans =

0.8415 0.9093 0.14111.6829 1.8186 0.28222.5244 2.7279 0.4234

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 22 / 190

MATLAB

Operações básicas com vectores e matrizes

Matriz>> A=[ 1 2 3; 4 5 6]

A =

1 2 34 5 6

Matriz 2× 3. O MATLAB é casesensitive, i.e., A é diferente de a.

Matriz transposta>> A=[ 1 2 3; 4 5 6]’

A =

1 42 53 6

Matriz 3× 2.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 23 / 190

MATLAB

Operações básicas com vectores e matrizes

Definição>> A+Bans =

3 55 77 9

>> A’+B’ans =

3 5 75 7 9

>> (A+B)’ans =

3 5 75 7 9

Soma>> A=[2 3; 3 4; 4 5]A =

2 33 44 5

>> B=[1 2; 2 3; 3 4]B =

1 22 33 4

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 24 / 190

MATLAB

Operações básicas com vectores e matrizes

Produto>> A*B??? Error using ==> mtimesInner matrix dimensions ...>> A*B’ans =

8 13 1811 18 2514 23 32

O número de colunas da primeiramatriz tem de ser igual aonúmero de linhas da segundamatriz.

Produto elemento a elemento>> A.*Bans =

2 66 12

12 20>> A^2??? Error using ==> mpowerMatrix must be square.>> A.^2ans =

4 99 16

16 25

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 25 / 190

MATLAB

Sistemas lineares

Um sistema linear pode ser representado na forma de matricial comoAx = b, em que A é uma matriz (dos coeficientes), x é a solução dosistemas e b é um vector (dos termos independentes).

Sistema

x1 +2x2 +3x3 = 14x1 +5x2 +6x3 = 27x1 +8x2 +9x3 = 3

1 2 34 5 67 8 9

x1

x2

x3

=

123

i.e. A =

1 2 34 5 67 8 9

x =

x1

x2

x3

e b =

123

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 26 / 190

MATLAB

Resolução de Sistemas lineares

O exemplo anterior>> A=[1 2 3; 4 5 6; 7 8 9]; b=[1 2 3]’;>> x=A\bWarning: Matrix is close to singular or badly scaled.

Results may be inaccurate. RCOND = 2.203039e-018.x =

-0.33330.6667

0>> A*x-bans =

1.0e-015 *0

-0.22200

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 27 / 190

MATLAB

Resolução de Sistemas lineares

Curiosidades>> det(A)ans =

0>> [L,U]=lu(A)L =

0.1429 1.0000 00.5714 0.5000 1.00001.0000 0 0

U =7.0000 8.0000 9.0000

0 0.8571 1.71430 0 -0.0000

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 28 / 190

MATLAB

Resolução de Sistemas lineares

Não fazer – Porquê?>> x=inv(A)*bWarning: Matrix is close to singular or badly scaled.

Results may be inaccurate. RCOND = 2.203039e-018.x =

000

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 29 / 190

MATLAB

Acesso a elementos de vectores e matrizesAcesso a vectores>> b=sin(b);>> b(1)ans =

0.8415>> b(2:3)ans =

0.90930.1411

>> b(:)ans =

0.84150.90930.1411

Acesso a matrizes>> A(2,2)ans =

5>> A(2,:)ans =

4 5 6>> A(:,1)ans =

147

>> A(1:2,2:3)ans =

2 35 6

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 30 / 190

MATLAB

Matrizes e vectores especiaisZeros e uns>> zeros(2,3)ans =

0 0 00 0 0

>> ones(2,1)ans =

11

>> t=1:1:3t =

1 2 3>> t=1.1:0.1:1.2t =

1.1000 1.2000

Identidade>> eye(3)ans =

1 0 00 1 00 0 1

>> rand(3,2)ans =

0.6068 0.76210.4860 0.45650.8913 0.0185

>> randn(2,2)ans =

1.1892 0.3273-0.0376 0.1746

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 31 / 190

MATLAB

Modificação de elementos em vectores e matrizes

Atribuições>> A=ones(3,3);>> A(1:2,1)=3A =

3 1 13 1 11 1 1

>> A(3,1:2:3)=4A =

3 1 13 1 14 1 4

Troca de valores>> A([1 2],1)=2*A([1 2],1)A =

6 1 16 1 14 1 4

>> A([1 3],1)=A([3 1],1)A =

4 1 16 1 16 1 4

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 32 / 190

MATLAB

Operadores lógicos e o find

find>> v=[0.1 0.4 0.12 0.13]v =

0.1000 0.4000 0.1200 0.1300>> i=find(v>0.12)i =

2 4>> a=v(i)a =

0.4000 0.1300>> i=find(v==0.1)i =

1>> i=find(v~=0.1)i =

2 3 4A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 33 / 190

MATLAB

Operadores lógicos e o find

Operadores lógicos

Símbolo Representa Símbolo Representa> Maior que >= Maior ou igual que< Menor que <= Menor ou igual que∼= Diferente de == Igual a∼ Negação & E| Ou

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 34 / 190

MATLAB

Funções básicas

Funções

Função Descriçãomax Elemento máximo de um vectormin Elemento mínimo de um vectorsum Soma de todos os elementosmean Média aritméticastdev Desvio padrão

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 35 / 190

MATLAB

Mensagens e display de variáveis

Ficheiros>> x = 0:.1:1; y = [x; exp(x)];>> fid = fopen(’exp.txt’,’w’)fid =

3>> fprintf(fid,’%6.2f %12.8f\n’,y);>> fclose(fid);

Conteúdo de exp.txt0.00 1.000000000.10 1.105170920.20 1.221402760.30 1.34985881

...

0.90 2.459603111.00 2.71828183

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 36 / 190

MATLAB

Mensagens e display de variáveis

Terminal>> x=1;y=2;>> fprintf(’Duas variáveis: %5.1f %6.2f\n’,x,y);Duas variáveis: 1.0 2.00>> x=[1 2];y=[3 4];>> fprintf(’Dois vectores: %5.1f %6.2f\n’,x,y);Dois vectores: 1.0 2.00Dois vectores: 3.0 4.00

Terminal>> xx =

1 2>> disp(x)

1 2

Terminal>> x=1.23;>> s=sprintf(’Uma string %4.2f’,x)s =Uma string 1.23

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 37 / 190

MATLAB

Scripts

DefiniçãoUm script trata-se da execução de uma série de comandos. Os scripts sãoguardados em ficheiros de extensão .m e por isso designámos por M-Files(ficheiros M).

Ficheiro bioinf.mx = 0:.1:1;y = exp(x);fprintf(’%4.2f %8.4f\n’,x,y);

Execução>> bioinf0.00 0.10000.20 0.3000...2.01 2.22552.46 2.7183

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 38 / 190

MATLAB

Desenho de gráficos 2D

Plot>> x=0:0.05:4*pi;>> plot(x,sin(x).^2+2*exp(x/(4*pi)));>> xlabel(’x’);>> ylabel(’sin^2(x)+2e^{x/(4\pi)}’);>> title(’O meu primeiro plot’);>> axis([0 4*pi 1 7]);

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 39 / 190

MATLAB

Desenho de gráficos 2D

0 2 4 6 8 10 121

2

3

4

5

6

7

x

sin2 (x

)+2e

x/(4

π)

O meu primeiro plot

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 40 / 190

MATLAB

Desenho de gráficos 2D

Sobreposição>> x=0:0.05:4*pi;>> plot(x,sin(x).^2+2*exp(x/(4*pi)));>> hold on;>> plot(x,-sin(x).^2+2*exp(x/(4*pi)));>> hold off;>> x=0:0.05:4*pi;>> y1=sin(x).^2+2*exp(x/(4*pi));>> y2=-sin(x).^2+2*exp(x/(4*pi));>> plot(x,y1,x,y2);

Dois gráficos quase idênticos (atenção às cores).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 41 / 190

MATLAB

Desenho de gráficos 2D

0 2 4 6 8 10 12 141

1.5

2

2.5

3

3.5

4

4.5

5

5.5

6

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 42 / 190

MATLAB

Desenho de gráficos 2D

Usando marcas e tipos de linhas>> x=0:0.05:4*pi;>> y=0:1:4*pi;>> plot(x,sin(x).^2+2*exp(x/(4*pi)),’--r’,1,3,’ok’,...3,4,’*g’,y,-sin(y).^2+2*exp(y/(4*pi)),’+k’);

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 43 / 190

MATLAB

Desenho de gráficos 2D

0 2 4 6 8 10 12 141

1.5

2

2.5

3

3.5

4

4.5

5

5.5

6

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 44 / 190

MATLAB

Desenho de gráficos 3D

Plot3>> t = 0:pi/50:10*pi;>> plot3(sin(t),cos(t),t);>> [x,y]=meshgrid(0:0.1:4*pi,0:0.1:pi);>> plot3(x,y,sin(x).*cos(y));>> surf(x,y,sin(x).*cos(y));

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 45 / 190

MATLAB

Desenho de gráficos 3D

−1−0.5

00.5

1

−1

−0.5

0

0.5

10

10

20

30

40

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 46 / 190

MATLAB

Desenho de gráficos 3D

0 2 4 6 8 10 12 14

0

1

2

3

4

−1

−0.5

0

0.5

1

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 47 / 190

MATLAB

Desenho de gráficos 3D

02

46

810

1214

0

1

2

3

4−1

−0.5

0

0.5

1

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 48 / 190

MATLAB

Desenho de curvas de nível

Contour>> [x,y]=meshgrid(0:0.1:4*pi,0:0.1:pi);>> contour(x,y,sin(x).*cos(y));>> contour(x,y,sin(x).*cos(y),50);

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 49 / 190

MATLAB

Desenho de curvas de nível

0 2 4 6 8 10 120

0.5

1

1.5

2

2.5

3

0 2 4 6 8 10 120

0.5

1

1.5

2

2.5

3

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 50 / 190

MATLAB

Funções MATLAB

As funções em MATLAB são escritas em ficheiros M. O nome do ficheirodeve corresponder ao nome da função

Execução>> simples(2)ans =

4>> a=simples([1 2])a =

1 4>> b=simples([1 2; 2 3])b =

1 44 9

simples.m

function f = simples(x)% O quadrado de x

% .^ para ...f=x.^2;

Help>> help simples

O quadrado de x

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 51 / 190

MATLAB

Funções MATLAB – O if

myfun.mfunction [a, b] = myfun(x,y)%% Argumentos de entrada:% x - O meu primeiro argumento% y - O meu segundo argumento%% Argumentos de saída:% a - O meu primeiro argumento de saída% b - O meu segundo argumento de saída

% Isto já não aparece no Help

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 52 / 190

MATLAB

Funções MATLAB – O ifmyfun.m – Cont.% Verificar os argumentos de entrada[d1,d2]=size(x);if d2 ~= 1

error(’Só aceito vectores coluna’);else

if nargin < 2y=ones(d1,1); % Valor por defeito para o y

else[d3,d4]=size(y);if d4 ~= 1

error(’Só aceito vectores coluna’);endif d3 ~= d1

error(’Dimensões de x e y não são iguais’);end

endend

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 53 / 190

MATLAB

Funções MATLAB – O if

myfun.m – Cont.if nargout < 1

error(’Pelo menos um argumento de saída’);end

a=2*x+y;

if nargout > 1b=3*x+2*y;

end

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 54 / 190

MATLAB

Funções MATLAB – O if

Execução>> myfun([1 2])??? Error using ==> myfunSó aceito vectores coluna>> myfun([1 2]’)??? Error using ==> myfunPelo menos um argumento de saída>> f=myfun([1 2]’)f =

35

>> f=myfun([1 2]’,[1 2 3])??? Error using ==> myfunSó aceito vectores coluna

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 55 / 190

MATLAB

Funções MATLAB – O if

Execução>> f=myfun([1 2]’,[1 2 3]’)??? Error using ==> myfunDimensões de x e y não são iguais>> [f1,f2]=myfun([1 2]’,[1 2]’)f1 =

36

f2 =5

10

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 56 / 190

MATLAB

Funções MATLAB – O for

Execução>> for i=1:2fprintf(’%d --> %d\n’,i,2*i);end1 --> 22 --> 4

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 57 / 190

MATLAB

Funções MATLAB – O inline

Execução>> g=inline(’sin(x)’);>> g(1)ans =

0.8415>> g=inline(’sin(x)*a’,’x’,’a’);>> g(1,2)ans =

1.6829

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 58 / 190

MATLAB

Zeros de funções

A função fzero>> g=inline(’cos(x)’);>> fzero(g,1.1)ans =

1.5708

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 59 / 190

Optimização

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 60 / 190

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 semderivadas)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 61 / 190

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 resolverproblemas com variáveis discretas.

Um solver que use derivadas (ou as estime), aplicado a um problema queenvolva funções não diferenciáveis, pode convergir (se convergir!!!) paraum ponto de descontinuidade da derivada, apresentando-a como solução.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 62 / 190

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

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 63 / 190

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.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 64 / 190

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])

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 65 / 190

Optimização

Classificação quanto à solução pretendida

Óptimo local (determinação de um minimizante local ou relativo)Óptimo global (determinação de uma minimizante global ou absoluto)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 66 / 190

Optimização

Classificação quanto à estrutura

Programação semi-definida (envolve matrizes semi-definidas)Programação semi-infinita (uma função objectivo sujeita a umainfinidade 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 fordiferente de zero então a outra é necessariamente zero)Problemas de controlo óptimo (determinar a melhor forma decontrolar um determinado sistema - frequentemente modelado comequações diferenciais)etc...

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 67 / 190

Optimização

Classificação de algoritmos

Estocásticos (Procura da solução de forma aleatória, mas controlada)Algoritmos genéticosColónias de formigasColónias de partículasetc...

Grande parte das vezes sem convergência garantida.Usados para a procura global (quando funcionam!!!).DeterminísticosDados os parâmetros iniciais (aproximação inicial e parâmetros doalgoritmo) executa sempre da mesma forma.Grande parte das vezes com convergência garantida para um óptimolocal.HíbridosUma mistura das duas abordagens

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 68 / 190

Optimização não linear sem restrições

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 69 / 190

Optimização não linear sem restrições

Forma geral do problema

A formulação matemática de um problema de optimização, na sua formamais geral, é

minx∈Rn

f(x)

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 ecj(x) ≥ são as restrições de desigualdade.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 70 / 190

Optimização não linear sem restrições

Equivalência entre problemas

O problema de optimização (maximização)

maxx∈Rn

g(x)

s.a ci(x) = 0, i = 1, . . . ,m

c̃j(x) ≤ 0, j = m + 1, . . . , t

é equivalente ao problema de optimização (minimização)

minx∈Rn

f(x) ≡ −g(x)

s.a ci(x) = 0, i = 1, . . . ,m

cj(x) ≡ −c̃j(x) ≥ 0, j = m + 1, . . . , t

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 71 / 190

Optimização não linear sem restrições

Interpretação geométrica

−1.5 −1 −0.5 0 0.5 1 1.5 2 2.5−6

−4

−2

0

2

4

6

x

f(x)

, −f(

x)

x*

f(x*)

−f(x*)

f(x) = (x− 0.5)2 + 2g(x) = −f(x) = −(x− 0.5)2 − 2

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 72 / 190

Optimização não linear sem restrições

Exemplo

Pretende-se determinar o volume máximo de uma lata (cilindro), fechadanas duas extremidades, sabendo que a quantidade de chapa a usar é de1000 cm2. Sendo r o raio da tampa e h a altura da lata, uma possívelformulação do problema de optimização é

max(r,h)∈R2

πr2h

s.a 2πr2 + 2πrh = 1000

que pode ser transformado no problema de minimização

minx∈R2

−πx21x2

s.a 2πx21 + 2πx1x2 = 1000

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 73 / 190

Optimização não linear sem restrições

Optimização sem restrições

Apenas iremos considerar problemas de minimização e sem restrições. Asua formulação é pois

minx∈Rn

f(x).

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) = 1

2xT 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çõesenvolvidas, f(x), c(x) é não linear).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 74 / 190

Optimização não linear sem restrições

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∗|| < δ).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 75 / 190

Optimização não linear sem restrições

Mínimo global

Mínimo global forte Função ilimitada Mínimo global fraco

f(x∗) < f(x̄) f(x∗) ≤ f(x̄)∀x̄ ∈ R ∀x̄ ∈ R

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 76 / 190

Optimização não linear sem restrições

Mínimo local

∃δ : f(x∗) < f(x̄), ∀x̄ ∈ Vδ(x∗).∃δ : f(x∗) ≤ f(x̄), ∀x̄ ∈ Vδ(x∗).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 77 / 190

Optimização não linear sem restrições

Conceitos

Máximo e maximizante;Mínimo e minimizante;Óptimo local ou global;Convergência local e global de algoritmos. Um algoritmo diz-se globalse determina um minimizante (maximizante) dada uma qualqueraproximação inicial. Um algoritmo diz-se local se determina umminimizante partindo apenas de uma aproximação inicialsuficientemente perto do minimizante. (Não confundir com adeterminação de mínimos locais ou globais).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 78 / 190

Optimização não linear sem restrições

Condições de optimalidade

Condições necessárias para a existência de um mínimof ′(x∗) = 0;f ′′(x∗) ≥ 0.

Condições suficientes para a existência de um mínimof ′(x∗) = 0;f ′′(x∗) > 0.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 79 / 190

Optimização não linear sem restrições

Exemplos

f(x) = (x− 1.5)2 f(x) = sin(x)f ′(1.5) = 2× (1.5− 1.5) = 0 f ′(π

2 ) = cos(π2 ) = 0

f ′′(1.5) = 2 > 0 f ′′(π2 ) = − sin(π

2 ) = −1 < 0

1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 20

0.05

0.1

0.15

0.2

0.25

1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 20.84

0.86

0.88

0.9

0.92

0.94

0.96

0.98

1

1.02

Pelas condições necessária e suficiente

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 80 / 190

Optimização não linear sem restrições

Exemplos

f(x) = x4 f(x) = x3

f ′(0) = 3× (0)3 = 0 f ′(0) = 3× (0)2 = 0f ′′(0) = 12× (0)2 = 0 f ′′(0) = 6× (0) = 0

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 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

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 81 / 190

Optimização não linear sem restrições

Alguma notação

Gradiente de f(x) : Rn → R, x = (x1, . . . , xn)T , vector de dimensão n

∇f(x) = g(x) =

∂f∂x1∂f∂x2

. . .∂f∂xn

=(

∂f

∂x1,

∂f

∂x2, . . . ,

∂f

∂xn

)T

Matriz Hessiana, matriz de dimensão n× n

∇2f(x) = G(x) =

∂2f∂x2

1. . . ∂2f

∂xn∂x1

. . . . . .∂2f

∂x1∂xn. . . ∂2f

∂x2n

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 82 / 190

Optimização não linear sem restrições

Condições de optimalidade

Condições necessárias para a existência de um mínimog(x∗) = 0 (sistema não linear);G(x∗) � 0 (semi-definida positiva).

Condições suficientes para a existência de um mínimog(x∗) = 0 (sistema não linear);G(x∗) � 0 (definida positiva).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 83 / 190

Optimização não linear sem restrições

Exemplo

Pretende-se determinar todos os pontos óptimos do seguinte problema deoptimização

minx∈R2

x21 + x3

2 + 2x1x2 ≡ f(x)

Da condição de necessária e suficiente de primeira ordem temos queg(x) = (2x1 + 2x2, 3x2

2 + 2x1)T = (0, 0)T ,

ou seja,{2x1 + 2x2 = 0

3x22 + 2x1 = 0

{x1 = −x2

3x22 − 2x2 = 0

x1 = −x2

x2 = 0 ∨ x2 =23

Os pontos x̄ = (0, 0)T e x̂ = (−23 , 2

3)T são pontos estacionários de f(x).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 84 / 190

Optimização não linear sem restrições

Cont.

Para verificar as condições de segunda ordem temos que estudar G(x̄) eG(x̂).

G(x) =(

2 22 6x2

), G(x̄) =

(2 22 0

), G(x̂) =

(2 22 4

)

det(|2|) = 2, det

(∣∣∣∣ 2 22 0

∣∣∣∣) = −4, det

(∣∣∣∣ 2 22 4

∣∣∣∣) = 4

e temos que G(x̄) é indefinida (x̄ é ponto sela - descanso) e G(x̂) édefinida positiva (x̂ é mínimo local forte).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 85 / 190

Optimização não linear sem restrições

Representação gráfica/Curvas de nível

−1.5−1

−0.50

0.51

1.5

−2

−1

0

1

2−10

−5

0

5

10

15

x1x2

f(x)

−1.5 −1 −0.5 0 0.5 1 1.5−1.5

−1

−0.5

0

0.5

1

1.5

f(x) = x21 + x3

2 + 2x1x2

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 86 / 190

Optimização não linear sem restrições

Motivação para os métodos numéricos

Na determinação analítica dos pontos estacionários é necessário resolverum sistema não linear, que é quase sempre de difícil resolução.

ExemploConsidere-se a função f(x) = x1e

x2 − 2x1x2.Os pontos estacionários de f(x) obtêm-se através da resolução do sistemanão linear {

ex2 − 2x2 = 0x1e

x2 − 2x1 = 0

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 87 / 190

Método de Segurança de Newton

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 88 / 190

Método de Segurança de Newton

Forma geral do problema

A formulação matemática de um problema de optimizaçãomultidimensional, sem restrições é

minx∈Rn

f(x),

com f(x) : Rn → R (n > 1) duas vezes diferenciável.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 89 / 190

Método de Segurança de Newton

Notação

Gradiente de f(x) : Rn → R, x = (x1, . . . , xn)T , vector de dimensão n

∇f(x) = g(x) =

∂f∂x1∂f∂x2

. . .∂f∂xn

=(

∂f

∂x1,

∂f

∂x2, . . . ,

∂f

∂xn

)T

Matriz Hessiana, matriz de dimensão n× n

∇2f(x) = G(x) =

∂2f∂x2

1. . . ∂2f

∂xn∂x1

. . . . . .∂2f

∂x1∂xn. . . ∂2f

∂x2n

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 90 / 190

Método de Segurança de Newton

Alguns conceitos

O vector gradiente ‘aponta’ no sentido de subida da função.

−10−5

05

10 −10

−5

0

5

10

−200

−100

0

100g(x)

−g(x)

f(x) =

− x21 − x2

2 − 2x1x2 + 10g(x) =

(−2x1 − 2x2,−2x2 − 2x1)T

g(1, 1) = (−4,−4)T

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 91 / 190

Método de Segurança de Newton

Alguns conceitos - Cont.

A matrix Hessiana indica a concavidade (convexa ou côncava).

−10−5

05

10 −10

−5

0

5

10−200

−150

−100

−50

0

50

f(x) =

− x21 − x2

2 − 2x1x2 + 10

G(x) =(−2 −2−2 −2

)Semi-definida negativa.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 92 / 190

Método de Segurança de Newton

Método de Newton

A função f(x), em x∗ = x + d pode ser aproximada por

f(x∗) ≈ f(x) + g(x)T d +12dT G(x)d (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 dem que x é um vector fixo. Derivando em ordem a d e igualando a zeroobtemos

g(x) + G(x)d = 0 ⇔ G(x)d = −g(x) (2)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 93 / 190

Método de Segurança de Newton

Cont.

Quando a função f(x) é quadrática obtém-se a solução resolvendo osistema linear (2). No caso em que f(x) não é quadrática, o novo pontox + d não é mínimo e o processo deve ser repetido iterativamente. Asequaçõ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) foruma função quadrática convexa o método de Newton necessita no máximode n iterações para encontrar a solução exacta.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 94 / 190

Método de Segurança de Newton

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ívelprogredir 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 quef(x(k+1)) > f(x(k)), e o novo ponto não é melhor que o anterior.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 95 / 190

Método de Segurança de Newton

Método de segurança de Newton

O método de segurança de Newton resolve as possíveis falhas do métodode Newton.

A matriz G(x(k)) é singular e d(k) não é sequer definido. Neste casotoma-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árioverificar a quase-ortogonalidade e a descida da função objectivo.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 96 / 190

Método de Segurança de Newton

Cont.

O vector direcção d(k) é quase ortogonal a g(x(k)) e não é possívelprogredir ao longo de d(k).

−6 −4 −2 0 2 4 6

−6

−4

−2

0

2

4

6

−g(1,1)

g(1,1)

Quase ortogonal se

|g(x(k))T d(k)| ≤ η‖g(x(k))‖‖d(k)‖Se for quase ortogonal então

d(k) = −g(x(k))

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 97 / 190

Método de Segurança de Newton

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) ≤ η‖g(x(k))‖‖d(k)‖.

Caso d(k) não seja direcção de descida faz-se

d(k) = −d(k).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 98 / 190

Método de Segurança de Newton

Cont.

A matriz G(x(k))−1 existe e é definida positiva, o vector direcção d(k) é dedescida, no entanto o comprimento é tal que f(x(k+1)) > f(x(k)), e o novoponto não é melhor que o anterior.

O método de Newton tem convergência local, i.e., x(k) tem de sersuficientemente próximo de x∗ para que o método funcione.

A convergência global obtém-se através da introdução da procuraunidimensional (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

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 99 / 190

Método de Segurança de Newton

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 e φ′′(α) > 0.

No entanto a solução para o problema minα∈R φ(α) não é de fácilresolução (difícil implementação e cálculos computacionais pesados).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 100 / 190

Método de Segurança de Newton

Procura unidimensional

Critério de Armijo e divisões sucessivas de α por dois.

Pressupondo que a direcção de procura é de descida, gera-se umasequência de valores,

{ωjα}, j = 0, 1, 2, . . . com α = 1 e ω =12

até se encontrar um elemento que origine uma redução (significativa) novalor 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 naiteração k (α(k) = ωjα).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 101 / 190

Método de Segurança de Newton

Critério de paragem

Considera-se as três condições para o critério de paragem

‖x(k+1) − x(k)‖‖x(k+1)‖

≤ ε1

|f (k+1) − f (k)||f (k+1)|

≤ ε2

‖g(k+1)‖ ≤ ε3

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 102 / 190

Método de Segurança de Newton

Exemplo

Considere-se o seguinte problema de optimização

minx∈R2

x41 + x2

2 − 3x1

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

)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 103 / 190

Método de Segurança de Newton

1a iteração

g(1) = g(x(1)) = (−3, 2)T G(1) = G(x(1)) =(

0 00 2

)(

0 0 30 2 −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 procuraunidimensional.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 104 / 190

Método de Segurança de Newton

Procura unidimensional

x(1) = (0, 1)T f (1) = 1 g(1)T d(1) = −13

α = 1 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 .

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 105 / 190

Método de Segurança de Newton

Critério de paragem

‖x(2) − x(1)‖‖x(2)‖

=√

1.52 + 12

1.5= 1.201 � 0.5

Logo passa-se à próxima iteração. As restantes condições seriam (nestecaso não é necessário verificar)

|f (2) − f (1)||f (2)|

=1− 0.5625

0.5625= 0.7778 � 0.5

e‖g(2)‖ = ‖(10.5, 0)T ‖ = 10.5 � 0.5

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 106 / 190

Método de Segurança de Newton

2a iteração x(2) = (1.5, 0)T

g(2) = (10.5, 0)T G(2) =(

27 00 2

)(

27 0 −10.50 2 0

)→ d(2) = (−0.3889, 0)T

d(2) é quase ortogonal com o gradiente?

‖d(2)‖ = 0.3889 ‖g(2)‖ = 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)).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 107 / 190

Método de Segurança de Newton

2a iteração - Cont.

d(2) é direcção de descida?

‖d(2)‖ = 0.3889 ‖g(2)‖ = 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.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 108 / 190

Método quasi-Newton

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 109 / 190

Método quasi-Newton

Método Quasi-Newton

O método Quasi-Newton usa uma matriz aproximação à matrizHessiana (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 umproduto matriz vector. (G(x)d = −g(d) → d = −G(x)−1g(x)).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 110 / 190

Método quasi-Newton

Cont.

A matriz aproximação é actualizada em cada iteração usando a informaçãodas derivadas (gradiente) da iteração anterior.

A fórmula mais conhecida é devida a Broyden, Fletcher, Goldfarb e Shanno(B.F.G.S.)

H(k+1) =

(I − s(k)y(k)T

s(k)T y(k)

)H(k)

(I − y(k)s(k)T

y(k)T s(k)

)+

s(k)s(k)T

s(k)T y(k)

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 deactualizaçã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.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 111 / 190

Método quasi-Newton

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 quaseortogonalidade e se a direcção calculada é de descida para a funçãoobjectivo.

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.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 112 / 190

Método quasi-Newton

Exemplo

Considere-se o seguinte problema de optimização (x(1) = (0, 1)T e ε = 0.5)

minx∈R2

x41 + x2

2 − 3x1

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 .

Procura unidimensional

. . . (ver exemplo do segurança de Newton)

Aceita-se α(1) = 0.5 e vem que x(2) = (1.5, 0)T .

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 113 / 190

Método quasi-Newton

Critério de paragem

‖x(2) − x(1)‖‖x(2)‖

=√

1.52 + 12

1.5= 1.201 � 0.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) =

(I − s(1)y(1)T

s(1)T y(1)

)H(1)

(I − y(1)s(1)T

y(1)T s(1)

)+

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

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 114 / 190

Método quasi-Newton

Cont.

s(1)y(1)T =(

1.5−1

)(13.5,−2) =

(20.25 −3−13.5 2

)s(1)T y(1) = (1.5,−1)(13.5,−2)T = 22.25

I − s(1)y(1)T

s(1)T y(1)=(

1 00 1

)−(

0.9101 −0.1348−0.6067 0.0899

)=(

0.0899 0.13480.6067 0.9101

)

s(1)s(1)T =(

1.5−1

)(1.5,−1) =

(2.25 −1.5−1.5 2

)H(2) =

(0.0899 0.13480.6067 0.9101

)H(1)

(0.0899 0.60670.1348 0.9101

)+(

0.1011 −0.0674−0.0674 0.0899

)

H(2) =(

0.1274 0.10980.1098 0.8202

)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 115 / 190

Método quasi-Newton

Cont.

d(2) = −H(2)g(2) = −(

0.1274 0.10980.1098 0.8202

)(10.5

0

)d(2) =

(−1.3377−1.1529

)Procura unidimensional. . .

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 116 / 190

Optimização sem restrições com o MATLAB

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 117 / 190

Optimização sem restrições com o MATLAB

Funções MATLAB

O MATLAB fornece um conjunto de funções para optimização linear e nãolinear das quais se destacam:

fzero - Zero de funções unidimensionais (Scalar functions);fminbound - Optimização não linear com limites simples de funçõesunidimensionais (escalares).fminsearch - Optimização não linear sem restrições e derivadas;fminunc - Optimização não linear sem restrições

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 118 / 190

Optimização sem restrições com o MATLAB

As opções para os algoritmos

Um dos argumentos aceite por determinados algoritmos é o OPTIONS. Esseargumento é uma estrutura com diversos parâmetros que podem sermodificados pelo utilizador para controlar o algoritmo.A estrutura OPTIONS pode ser criada/actualizada através da funçãoOPTIMSET.

>> optimsetDisplay: [ off | on | iter | notify | final ]

MaxFunEvals: [ positive scalar ]MaxIter: [ positive scalar ]TolFun: [ positive scalar ]

TolX: [ positive scalar ]...

GradObj: [ on | {off} ]Hessian: [ on | {off} ]

...Jacobian: [ on | {off} ]

...A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 119 / 190

Optimização sem restrições com o MATLAB

As opções para os algoritmos

>> opt=optimset(’display’,’iter’);>> fzero(g,1.1,opt)Search for an interval around 1.1 containing a sign change:Func-count a f(a) b f(b) Procedure

1 1.1 0.453596 1.1 0.453596 initial interval3 1.06889 0.4811 1.13111 0.425653 search

...17 0.748 0.733051 1.452 0.118517 search19 0.602197 0.824093 1.5978 -0.0270036 search

Search for a zero in the interval [0.6022, 1.5978]:Func-count x f(x) Procedure

19 1.5978 -0.0270036 initial...

24 1.5708 6.12323e-017 interpolationZero found in the interval [0.602197, 1.5978]ans =

1.5708

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 120 / 190

Optimização sem restrições com o MATLAB

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∑

i=1

(αixi −12βix

2i ) +

12

n−1∑i=1

(xixi+1) (n > 1).

Para n = 2, α1 = 1, α2 = 2, β1 = β2 = 1, pretende-se calcular x1 e x2 demodo a maximizar o retorno esperado.O problema é modelado como um problema de optimização sem restrições

max f(x1, x2) ≡(

x1 −x2

1

2

)+(

2x2 −x2

2

2

)+

x1x2

2

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 121 / 190

Optimização sem restrições com o MATLAB

A resolução – Simples

fminsearch>> g=inline(’-(x(1)-x(1)^2/2+2*x(2)-x(2)^2/2+x(1)*x(2)/2)’);>> fminsearch(g,[1 1])ans =

2.6666 3.3333

2 2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 42

2.2

2.4

2.6

2.8

3

3.2

3.4

3.6

3.8

4

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 122 / 190

Optimização sem restrições com o MATLAB

Sintaxe

A função fminsearch usa o algoritmo de Nelder-Mead. A sintaxecompleta da função é:

[X,FVAL,EXITFLAG,OUTPUT] = FMINSEARCH(FUN,X0,OPTIONS)

X - A solução encontrada.FVAL - O valor da função em X.EXITFLAG - 1 se o algoritmo convergiu, 0 se atingiu o número máximode iterações e -1 em caso de erro.OUTPUT - retorna uma estrutura com o número de iterações emOUTPUT.iterations, o número de cálculos da função objectivo emOUTPUT.funcCount, o nome do algoritmo em OUTPUT.algorithm e amensagem de saída em OUTPUT.message.FUN - Nome da função a minimizar.X0 - Aproximação inicial.OPTIONS - Estrutura com opções para o algoritmo.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 123 / 190

Optimização sem restrições com o MATLAB

A resolução – Mais elaborada

>> g=inline(’-(x(1)-x(1)^2/2+2*x(2)-x(2)^2/2+x(1)*x(2)/2)’);>> opt=optimset(’display’,’iter’);>> [x,fval,e,o]=fminsearch(g,[1 1],opt)Iteration Func-count min f(x) Procedure

0 1 -2.51 3 -2.57375 initial simplex2 5 -2.64719 expand

...25 49 -4.66665 contract outside26 51 -4.66665 contract inside27 52 -4.66665 reflect

...45 86 -4.66667 contract inside

Optimization terminated:the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-004and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-004

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 124 / 190

Optimização sem restrições com o MATLAB

A resolução – Mais elaborada

x =2.6666 3.3333

fval =-4.6667

e =1

o =iterations: 45funcCount: 86algorithm: ’Nelder-Mead simplex direct search’

message: [1x196 char]

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 125 / 190

Optimização sem restrições com o MATLAB

A resolução com fminunc

>> [x,fval,e,o,g,H]=fminunc(g,[1 1],opt)Warning: Gradient must be provided for trust-region method;

using line-search method instead.> In fminunc at 241

Gradient’sIteration Func-count f(x) Step-size infinity-norm

0 3 -2.5 1.51 6 -3.77778 0.666667 0.6672 9 -4.65765 1 0.1323 12 -4.66664 1 0.006584 15 -4.66667 1 0.0001655 18 -4.66667 1 1.34e-006

Optimization terminated: relative infinity-norm of gradient lessthan options.TolFun.

Computing finite-difference Hessian using user-supplied objectivefunction.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 126 / 190

Optimização sem restrições com o MATLAB

A solução com fminunc

x =2.6667 3.3333

o =iterations: 5funcCount: 18stepsize: 1

firstorderopt: 1.3411e-006algorithm: ’medium-scale: Quasi-Newton line search’

message: [1x85 char]g =

1.0e-005 *0.13410.0966

H =1.0000 -0.5000

-0.5000 1.0000

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 127 / 190

Optimização sem restrições com o MATLAB

A resolução com fminunc usando o gradiente

retorno.mfunction [f,g] = retorno(x)

f=-x(1)+x(1)^2/2-2*x(2)+x(2)^2/2-x(1)*x(2)/2;

if nargout > 1 % gradienteg(1)=-1+x(1)-x(2)/2;g(2)=-2+x(2)-x(1)/2;

end

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 128 / 190

Optimização sem restrições com o MATLAB

A resolução com fminunc usando o gradiente

>> opt=optimset(’display’,’iter’,’GradObj’,’on’);>> [x,fval,e,o,g,H]=fminunc(’retorno’,[1 1],opt)

Norm of First-orderIteration f(x) step optimality CG-iterations

0 -2.5 1.51 -4.28571 2.25877 0.857 12 -4.59969 0.695006 0.264 13 -4.65489 0.397146 0.151 14 -4.6646 0.122199 0.0464 15 -4.6663 0.0698279 0.0265 16 -4.6666 0.0214855 0.00815 17 -4.66666 0.0122774 0.00466 18 -4.66666 0.00377767 0.00143 19 -4.66667 0.00215867 0.000819 1

Optimization terminated: Relative function value changing by lessthan OPTIONS.TolFun.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 129 / 190

Optimização sem restrições com o MATLAB

A solução com fminunc usando o gradientex =

2.6658 3.3332o =

iterations: 9funcCount: 10

cgiterations: 9firstorderopt: 8.1916e-004

algorithm: ’large-scale: trust-region Newton’message: [1x86 char]

g =1.0e-003 *-0.81920.2731

H =(1,1) 1.0000(2,1) -0.5000(1,2) -0.5000(2,2) 1.0000

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 130 / 190

Optimização sem restrições com o MATLAB

A resolução com fminunc usando o gradiente e hessiana

retorno.mfunction [f,g,h] = retorno(x)

f=-x(1)+x(1)^2/2-2*x(2)+x(2)^2/2-x(1)*x(2)/2;if nargout > 1 % gradiente

g(1)=-1+x(1)-x(2)/2;g(2)=-2+x(2)-x(1)/2;

endif nargout > 2 % hessiana

h(1,1)=1;h(2,1)=-0.5;h(1,2)=h(2,1);h(2,2)=1;

end

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 131 / 190

Optimização sem restrições com o MATLAB

A resolução com fminunc usando o gradiente e hessiana

>> opt=optimset(’GradObj’,’on’,’Hessian’,’on’);>> [x,fval,e,o,g,H]=fminunc(’retorno’,[1 1],opt);>> o =

iterations: 9funcCount: 10

cgiterations: 9firstorderopt: 8.1916e-004

algorithm: ’large-scale: trust-region Newton’message: [1x86 char]

>> xx =

2.6658 3.3332

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 132 / 190

Optimização não linear com restrições de igualdade

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 133 / 190

Optimização não linear com restrições de igualdade

Formulação geral

minx∈Rn

f(x) (3)

s.ac(x) = 0

em que f(x) e c(x) são funções não lineares em x.

x = (x1, x2, . . . , xn)Tf(x) : Rn → R

c(x) : Rn → Rm

n é o número de variáveis do problemam é 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.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 134 / 190

Optimização não linear com restrições de igualdade

Exemplo

Exemplo 1

minx∈R5

ex1x2x3x4x5

s.ax2

1 + x22 + x2

3 + x24 + x2

5 = 10

x2x3 = 5x4x5

x31 + x3

2 = −1

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 135 / 190

Optimização não linear com restrições de igualdade

Exemplo (cont.)

Temos então

f(x) = ex1x2x3x4x5

c1(x) = x21 + x2

2 + x23 + x2

4 + x25 − 10

c2(x) = x2x3 − 5x4x5

c3(x) = x31 + x3

2 + 1

com n = 5 e m = 3.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 136 / 190

Optimização não linear com restrições de igualdade

Notação

Gradiente de f(x) (vector de n elementos)

∇f(x) =

∂f∂x1...

∂f∂xn

Hessiana de f(x) (matriz simétrica de n× n)

∇2f(x) =

∂2f∂x2

1. . . ∂2f

∂xn∂x1

. . . . . .∂2f

∂x1∂xn. . . ∂2f

∂x2n

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 137 / 190

Optimização não linear com restrições de igualdade

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

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 138 / 190

Optimização não linear com restrições de igualdade

Notação

Matriz Jacobiano das restrições (matriz n×m)

∇c(x) =

∂c1∂x1

∂c2∂x1

. . . ∂cm∂x1

...... . . .

...∂c1∂xn

∂c2∂xn

. . . ∂cm∂xn

ou

∇c(x) = (∇c1(x)∇c2(x) . . .∇cm(x))

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 139 / 190

Optimização não linear com restrições de igualdade

Notação

Hessiana de c1(x) (matriz simétrica de n× n)

∇2c1(x) =

∂2c1∂x2

1. . . ∂2c1

∂xn∂x1

. . . . . .∂2c1

∂x1∂xn. . . ∂2c1

∂x2n

. . .

Hessiana de cm(x) (matriz simétrica de n× n)

∇2cm(x) =

∂2cm

∂x21

. . . ∂2cm∂xn∂x1

. . . . . .∂2cm

∂x1∂xn. . . ∂2cm

∂x2n

Existem m Hessianas das restrições (n× n).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 140 / 190

Optimização não linear com restrições de igualdade

Condições de optimalidade

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)

= f(x)−m∑

i=1

λici(x)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 141 / 190

Optimização não linear com restrições de igualdade

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) foremlinearmente independentes, então x∗ é ponto regular.

Pergunta:Como se verifica se um conjunto de vectores é linearmente independente(em termos informáticos)?

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 142 / 190

Optimização não linear com restrições de igualdade

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

∇xL(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çõesKuhn-Tucker (KT).O par (x∗, λ∗) chama-se par KT.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 143 / 190

Optimização não linear com restrições de igualdade

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.

∇xL(x∗, λ∗) = ∇f(x∗)−∇c(x∗)λ∗ = 0⇔ ∇f(x∗) = ∇c(x∗)λ∗

⇔ ∇f(x∗) =m∑

i=1

λ∗i∇ci(x∗)

significa que o gradiente de f (∇f) é uma combinação linear dosgradientes das restrições (das colunas de ∇c(x∗).

Pergunta:Dado um x∗ como determinar os valores de λ∗?

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 144 / 190

Optimização não linear com restrições de igualdade

Exemplo

Exemplo 2

minx∈R2

f(x) ≡ x1 + x2

s.ac(x) = x2

1 − x22 = 0

Considere x∗ = (1,−1)T e x̄ = (2, 2)T .Tem-se que

∇f(x) =(

11

)e ∇c(x) =

(2x1

−2x2

)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 145 / 190

Optimização não linear com restrições de igualdade

Condições KT

Em x∗ Em x̄

∇f(x∗) =(

11

)∇f(x̄) =

(11

)e

∇c(x∗) =(

22

)∇c(x̄) =

(4−4

)⇒ ⇒(

11

)= λ∗

(22

) (11

)= λ̄

(4−4

)∃ um λ∗ (λ∗ = 0.5) @ um λ̄

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 146 / 190

Optimização não linear com restrições de igualdade

Condição necessária de 2a ordem - Mínimo

Seja x∗ uma solução do problema. Se x∗ é ponto regular então para todosos vectores s ∈ Rn que verificam ∇c(x∗)T s = 0 (direcções tangentes àscurvas admissíveis), tem-se

sT∇2xxL(x∗, λ∗)s ≥ 0.

Nota:

∇2xxL(x, λ) = ∇2f(x)−

m∑i=1

λi∇2ci(x)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 147 / 190

Optimização não linear com restrições de igualdade

Condição suficiente de 2a ordem - Mínimo

Se (x∗, λ∗) é um par KT, isto é, verifica as condições KT{∇xL(x∗, λ∗) = 0∇λL(x∗, λ∗) = 0

e sesT∇2

xxL(x∗, λ∗)s > 0

para todo o s (s 6= 0) tal que

∇c(x∗)T s = 0

então x∗ é minimizante local forte.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 148 / 190

Optimização não linear com restrições de igualdade

O exemplo em x∗

∇2xxL(x∗, λ∗) =

(0 00 0

)− 0.5

(2 00 −2

)=(−1 00 1

)∇c(x∗)T s = 0 ⇒ s1 = −s2

Como

sT∇2xxL(x∗, λ∗)s = (−s2, s2)

(−1 00 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).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 149 / 190

Optimização não linear com restrições de desigualdade

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 150 / 190

Optimização não linear com restrições de desigualdade

Formulação geral:

minx∈Rn

f(x) (4)

s.ac(x) ≥ 0

em que f(x) e c(x) são funções não lineares em x.

x = (x1, x2, . . . , xn)Tf(x) : Rn → R

c(x) : Rn → Rm

n é o número de variáveis do problemam é 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.A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 151 / 190

Optimização não linear com restrições de desigualdade

Condições de optimalidade

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)

= f(x)−m∑

i=1

λici(x)

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 152 / 190

Optimização não linear com restrições de desigualdade

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 activasPoderíamos dizer que as restrições activas são aquelas que participam nacaracterização da solução. Enquanto que as não activas “não interessam”para essa caracterização.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 153 / 190

Optimização não linear com restrições de desigualdade

Condição de regularidade

Seja x∗ uma solução do problema.

Se os vectores ∇ci(x∗), i ∈ A (gradientes das restrições activas, calculadosna solução) forem linearmente independentes, então x∗ é ponto regular.

Ponto regularA definição é idêntica para o caso das restrições de igualdade, mas no casode problemas com restrições de desigualdade só as restrições activas é que“contam”.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 154 / 190

Optimização não linear com restrições de desigualdade

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

∇xL(x∗, λ∗) = ∇f(x∗)−∇c(x∗)λ∗ = 0 ponto estacionário da Lag.

c(x∗) ≥ 0 admissibilidade

λ∗ ≥ 0 “positiveness”

e(λ∗)T c(x∗) = 0 complementaridade

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 155 / 190

Optimização não linear com restrições de desigualdade

Interpretação das condições KT

A complementaridade ((λ∗)T c(x∗) = 0) diz-nos que as restrições nãoactivas têm multiplicadores iguais a zero (ci(x∗) > 0 ⇒ λ∗i = 0, i /∈ A).

Para as restrições activas os multiplicadores de Lagrange correspondentespodem ou não ser zero. Se forem zero estamos na presença de umproblema degenerado. No caso de não existirem multiplicadores iguais azero 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.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 156 / 190

Optimização não linear com restrições de desigualdade

Interpretação das condições KT

∇xL(x∗, λ∗) = ∇f(x∗)−∇c(x∗)λ∗ = 0⇔ ∇f(x∗) = ∇c(x∗)λ∗

⇔ ∇f(x∗) =m∑

i=1

λ∗i∇ci(x∗)

significa que o gradiente de f (∇f) é uma combinação linear dosgradientes das restrições (das colunas de ∇c(x∗).

Nota:As restrições inactivas não influenciam, uma vez que λ∗i = 0, i /∈ A.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 157 / 190

Optimização não linear com restrições de desigualdade

Exemplo (Nash&Sofer)

Exemplo

minx∈R2

f(x) ≡ x1

s.a(x1 + 1)2 + x2

2 ≥ 1

x21 + x2

2 ≤ 2

Considere x1 = (0, 0)T , x2 = (−1,−1)T e x3 = (0,√

2)T .Tem-se que

L(x, λ) = x1 − (λ1, λ2)(

(x1 + 1)2 + x22 − 1

2− x21 − x2

2

)= x1 − λ1

((x1 + 1)2 + x2

2 − 1)

+ λ2

(x2

1 + x22 − 2

)A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 158 / 190

Optimização não linear com restrições de desigualdade

Condições KT

Logo

∇xL(x, λ) =(

1− 2λ1(x1 + 1) + 2λ2x1

−2λ1x2 + 2λ2x2

)Para x1 = (0, 0)T apenas a primeira restrição está activa, logo λ2 = 0.Resolvendo ∇xL(x1, λ) = 0 em ordem a λ1 vem{

1− 2λ1 = 00 = 0

⇒ λ1 =12

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 159 / 190

Optimização não linear com restrições de desigualdade

Para x2 = (−1,−1)T ambas as restrições estão activas e resolvendo∇xL(x2, λ) = 0 em ordem aos multiplicadores de Lagrange obtemos{

1− 2λ2 = 02λ1 − 2λ2 = 0

⇒ λ1 = λ2 =12

Para x3 = (0,√

2)T apenas a segunda restrição está activa e resolvendo∇xL(x3, λ) = 0 em ordem a λ2 (λ1 = 0) obtemos{

1 + 2λ2(0) = 02λ2

√2 = 0

que é um sistema inconsistente e consequentemente x3 não satisfaz ascondições de optimalidade de primeira ordem.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 160 / 190

Optimização não linear com restrições de desigualdade

Condição necessária de 2a ordem - Mínimo

Seja x∗ uma solução do problema. Se x∗ é ponto regular então para todosos vectores s ∈ Rn que verificam ∇C(x∗)T s = 0, em que C(x∗) é umamatriz formada pelas restrições activas em x∗ (direcções tangentes àscurvas admissíveis), tem-se

sT∇2xxL(x∗, λ∗)s ≥ 0.

NotaCondição idêntica à apresentada para os problemas com restrições deigualdade, mas apenas se considera as restrições activas no caso dasdesigualdades.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 161 / 190

Optimização não linear com restrições de desigualdade

Condição suficiente de 2a ordem - Mínimo

Se (x∗, λ∗) é um par KT, isto é, verifica as condições KT{∇xL(x∗, λ∗) = 0∇λL(x∗, λ∗) = 0

e sesT∇2

xxL(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).

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 162 / 190

Optimização não linear com restrições de desigualdade

O exemplo em x1

∇2xxL(x, λ) =

(2(λ2 − λ1) 0

0 2(λ2 − λ1)

)Logo para x1 = (0, 0)T e λ1 = (1

2 , 0)T temos que

∇2xxL(x, λ) =

(−1 00 −1

)1

Como ∇C(x1) = (2, 0)T temos s = (0, s2)T e consequentemente

(0, s2)(−1 00 −1

)(0s2

)= −s2

2 ≤ 0 (s2 6= 0)

Logo x1 não é mínimo local. Não é máximo local porque λ1 ≥ 0.

1definida negativaA. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 163 / 190

Optimização não linear com restrições de desigualdade

O exemplo em x2

Como ∇C(x2) =(

0 −22 2

)tem-se que @s 6= 0 : ∇C(x2)T s = 0 e a

condição suficiente é verificada trivialmente.

Nota

λ1 = λ2 = 12

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 164 / 190

Optimização com restrições com o MATLAB

Conteúdo

1 Introdução

2 MATLAB

3 Optimização

4 Optimização não linear sem restrições

5 Método de Segurança de Newton

6 Método quasi-Newton

7 Optimização sem restrições com o MATLAB

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 MATLAB

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 165 / 190

Optimização com restrições com o MATLAB

Funções MATLAB

O MATLAB fornece um conjunto de funções para optimização linear e nãolinear das quais se destacam:

linprog - Optimização linear;fmincon - Optimização não linear com restrições;

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 166 / 190

Optimização com restrições com o MATLAB

Exemplo linearUma empresa procede à montagem de quatro produtos (1, 2, 3, 4) a partir decomponentes 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 paracada 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 ashoras-homem necessárias para cada estado por unidade de produto são

Produto1 2 3 4

Estado A 2 2 1 1B 2 4 1 2C 3 6 1 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 ostrabalhadores no estado B possam passar até 20% do seu tempo no estado A e ostrabalhadores 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 produto1)/(número de unidades do produto 4) tem que estar entre 0.9 e 1.15.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 167 / 190

Optimização com restrições com o MATLAB

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 tempotransferido de C para A.Restrições de capacidade máxima: x1 ≤ 50, x2 ≤ 60, x3 ≤ 85, x4 ≤ 70Restrição de razão: 0.9 <= (x1/x4) <= 1.15, i.e., 0.9x4 ≤ x1 ex1 ≤ 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), tCA ≤ 0.3(80)Limites simples: xi ≥ 0, i = 1, 2, 3, 4Função objectivo: max 10x1 + 15x2 + 22x3 + 17x4

Ignora-se o facto das variáveis xi, i = 1, 2, 3, 4 terem de ser inteiras.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 168 / 190

Optimização com restrições com o MATLAB

O problema linear

minx∈R6

− 10x1 − 15x2 − 22x3 − 17x4

s.a 0 ≤ x1 ≤ 500 ≤ x2 ≤ 600 ≤ x3 ≤ 850 ≤ x4 ≤ 700 ≤ x5 ≤ 400 ≤ x6 ≤ 24− x1 + 0.9x4 ≤ 0x1 − 1.15x4 ≤ 02x1 + 2x2 + x3 + x4 − x5 − x6 ≤ 1602x1 + 4x2 + x3 + 2x4 + x5 ≤ 2003x1 + 6x2 + x3 + 5x4 + x6 ≤ 80

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 169 / 190

Optimização com restrições com o MATLAB

O problema linear – Forma matricial

minx∈R6

(−10,−15,−22,−17, 0, 0)x

s.a

000000

≤ x ≤

506085704024

−1 0 0 0.9 0 0

1 0 0 −1.15 0 02 2 1 1 −1 −12 4 1 2 1 03 6 1 5 0 1

x ≤

00

16020080

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 170 / 190

Optimização com restrições com o MATLAB

MATLAB LINPROG

A sintaxe da função para programação linear é:[X,FVAL,EXITFLAG,OUTPUT,LAMBDA]=

LINPROG(f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

X - A solução encontrada.

FVAL - O valor da função em X (f’*X).

EXITFLAG - 1 se o algoritmo convergiu, 0 se atingiu o número máximo deiterações e negativo em caso de erro.

OUTPUT - retorna uma estrutura com o número de iterações emOUTPUT.iterations, o número de iterações de gradientes conjugados (seusado) em OUTPUT.cgiterations, o nome do algoritmo emOUTPUT.algorithm e a mensagem de saída em OUTPUT.message.

LAMBDA - Estrutura com os multiplicadores de Lagrange na solução.LAMBDA.ineqlin para as desigualdades lineares A, LAMBDA.eqlin para asigualdades lineares Aeq, LAMBDA.lower para os limites inferiores LB, eLAMBDA.upper para UB.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 171 / 190

Optimização com restrições com o MATLAB

MATLAB LINPROG

A sintaxe da função para programação linear é:[X,FVAL,EXITFLAG,OUTPUT,LAMBDA]=

LINPROG(f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

f – Vector dos coeficientes da função objectivo.

A e Aeq - Matriz dos coeficientes das restrições de desigualdade (Ax<=b) eigualdade, respectivamente.

b e beq - Vector dos termos independentes das restrições de desigualdade eigualdade, respectivamente.

LB e UB - Vector dos limites simples (inferior e superior, respectivamente)nas variáveis.

X0 - Aproximação inicial.

OPTIONS - Estrutura com opções para o algoritmo.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 172 / 190

Optimização com restrições com o MATLAB

Resolução

>> f=[-10; -15; -22; -17; 0; 0];>> A=[-1 0 0 0.9 0 0; 1 0 0 -1.15 0 0;...2 2 1 1 -1 -1; 2 4 1 2 1 0; 3 6 1 5 0 1]A =

-1.0000 0 0 0.9000 0 01.0000 0 0 -1.1500 0 02.0000 2.0000 1.0000 1.0000 -1.0000 -1.00002.0000 4.0000 1.0000 2.0000 1.0000 03.0000 6.0000 1.0000 5.0000 0 1.0000

>> b=[0; 0; 160; 200; 80];>> LB=[0; 0; 0; 0; 0; 0];>> UB=[50; 60; 85; 70; 40; 24];>> opt=optimset(’display’,’iter’);

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 173 / 190

Optimização com restrições com o MATLAB

Resolução

>> [x, fval, e, o, l]=linprog(f,A,b,[],[],LB,UB,[],opt);

Residuals: Primal Dual Upper Duality TotalInfeas Infeas Bounds Gap RelA*x-b A’*y+z-w-f {x}+s-ub x’*z+s’*w Error

-------------------------------------------------------------Iter 0: 1.89e+003 3.15e+001 3.59e+002 3.27e+004 7.04e+000Iter 1: 2.37e+002 2.62e+000 4.51e+001 5.41e+003 8.85e-001Iter 2: 1.45e+001 1.51e-001 2.76e+000 6.14e+002 2.16e-001Iter 3: 3.13e+000 1.50e-013 5.94e-001 9.40e+001 2.85e-002Iter 4: 1.31e-002 4.07e-014 2.48e-003 1.46e+001 8.12e-003Iter 5: 8.69e-007 1.64e-014 1.65e-007 8.67e-004 4.82e-007Iter 6: 8.49e-013 7.75e-014 1.65e-013 8.67e-010 4.88e-013

Optimization terminated.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 174 / 190

Optimização com restrições com o MATLAB

Resultados

>> x’ans =

0.0000 0.0000 80.0000 0.0000 17.6906 0.0000>> l.ineqlin’ans =

23.1663 21.0229 0.0000 0.0000 22.0000>> l.lower’ans =

53.8566 117.0000 0.0000 89.6734 0.0000 22.0000>> oo =

iterations: 6algorithm: ’large-scale: interior point’

cgiterations: 0message: ’Optimization terminated.’

>> fvalfval =-1.7600e+003A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 175 / 190

Optimização com restrições com o MATLAB

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. Ofazendeiro tem uma quantidade limitada de fertilizante F permitido e deinsecticida P permitido que podem ser usados. Cada um deles sendonecessá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 ex2, respectivamente, então o número óptimo de quilómetros quadrados deplantação com trigo vs cevada pode ser formulado como o seguinteproblema de programação linear:

max S1x1 + S2x2 (lucro)s.a x1 + x2 ≤ A (limite da área total)

F1x1 + F2x2 ≤ F (limite do fertilizante)P1x1 + P2x2 ≤ P (limite do insecticida)

x1, x2 ≥ 0 (área não negativa)A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 176 / 190

Optimização com restrições com o MATLAB

Interpretação geométrica de um problema

S1 = 2, S2 = 1.5, A = 10, F = 9, P = 45, (F1, P1) = (0.5, 6),(F2, P2) = (1.7, 1)

>> f=[-2 -1.5];>> A=[1 1; 0.5 1.7; 6 1];>> b=[10 9 45];>> opt=optimset(’simplex’,’on’,’Largescale’,’off’);>> [x, fval, e, o, l]=...linprog(f,A,b,[],[],[0 0], [], [6 6], opt);

>> x’ans =

7 3>> l.ineqlin’ans =

1.4000 -0.0000 0.1000

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 177 / 190

Optimização com restrições com o MATLAB

Interpretação geométrica de um problema

Simplex

x1

x 2

0 1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7

8

9

10

Região Admissível

Solução

Inicial

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 178 / 190

Optimização com restrições com o MATLAB

Interpretação geométrica de um problema

Pontos Interiores

x1

x 2

0 1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7

8

9

10

Região Admissível

Solução

Inicial (x1)

x2

x3

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 179 / 190

Optimização com restrições com o MATLAB

MATLAB FMINCONA sintaxe da função para programação não linear é:[X,FVAL,EXITFLAG,OUTPUT,LAMBDA,GRAD]=

FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)

X e FVAL - A solução encontrada e valor da função objectivo.

EXITFLAG - Razão da terminação do algoritmo.

OUTPUT - retorna uma estrutura com o número de iterações emOUTPUT.iterations, o número de cálculos da função objectivo emOUTPUT.funcCount, o número de iterações de gradientes conjugados (seusado) em OUTPUT.cgiterations, a optimalidade de primeira ordem (seusado) em OUTPUT.firstorderopt e a mensagem de saída emOUTPUT.message.

LAMBDA - Estrutura com os multiplicadores de Lagrange na solução.LAMBDA.ineqlin para as desigualdades lineares A, LAMBDA.eqlin para asigualdades lineares Aeq, LAMBDA.ineqnonlin para as desigualdade nãolineares, LAMBDA.eqnonlin para as igualdades não lineares, LAMBDA.lowerpara os limites inferiores LB, e LAMBDA.upper para UB.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 180 / 190

Optimização com restrições com o MATLAB

MATLAB FMINCON

A sintaxe da função para programação não linear é:[X,FVAL,EXITFLAG,OUTPUT,LAMBDA,GRAD]=

FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)

FUN - Função objectivo.

X0 - Aproximação inicial.

A e Aeq - Matriz dos coeficientes das restrições de desigualdade (Ax<=b) eigualdade, respectivamente.

b e beq - Vector dos termos independentes das restrições de desigualdade eigualdade, respectivamente.

LB e UB - Vector dos limites simples (inferior e superior, respectivamente)nas variáveis.

NONLCON - Função das restrições não lineares (C<=0 e Ceq=0).

OPTIONS - Estrutura com opções para o algoritmo.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 181 / 190

Optimização com restrições com o MATLAB

A função FUN

FUN no caso mais geral com Gradiente e Hessianafunction [f,g,H] = myfun(x)f = ... % Compute the objective function value at xif nargout > 1 % fun called with two output arguments

g = ... % Gradient of the function evaluated at xif nargout > 2

H = ... % Hessian evaluated at xend

end

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 182 / 190

Optimização com restrições com o MATLAB

A função NONLCON

NONLCON no caso mais geral com Jacobianofunction [c,ceq,GC,GCeq] = mycon(x)c = ... % Nonlinear inequalities at xceq = ... % Nonlinear equalities at xif nargout > 2 % nonlcon called with 4 outputs

GC = ... % Gradients of the inequalitiesGCeq = ... % Gradients of the equalities

end

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 183 / 190

Optimização com restrições com o MATLAB

Exemplo não linear com restrições

CaixaPretende-se construir uma caixa cujo comprimento da base é 3 vezes alargura da base. O material usado para construir o topo e base da caixacusta 10e/m2 e o material usado para construir as paredes laterais custa6e/m2. Se a caixa tiver um volume de 50m3 determine as dimensões dacaixa que minimiza o custo total de construção da caixa.

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 184 / 190

Optimização com restrições com o MATLAB

Formulação

Função objectivoPretende-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., 3w2h = 50.

O problema w → x1, h → x2

min 60x21 + 48x1x2

s.a 3x21x2 − 50 = 0

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 185 / 190

Optimização com restrições com o MATLAB

Resolução

caixa_f.mfunction f=caixa_f(x)f=60*x(1)^2+48*x(1)*x(2);

caixa_con.mfunction [c,ceq] = caixa_con(x)ceq(1)=3*x(1)^2*x(2)-50;c=[];

Execução>> [x,fval,e,o,l,g]=...fmincon(’caixa_f’,[1 1],[],[],[],[],[],[],’caixa_con’);Warning: Large-scale (trust region) method does not currently solve this type of problem,switching to medium-scale (line search).

> In fmincon at 260Optimization terminated: magnitude of search direction less than 2*options.TolXand maximum constraint violation is less than options.TolCon.

>> xx =

1.8821 4.7052

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 186 / 190

Optimização com restrições com o MATLAB

Resolução

Inspecção>> fvalfval =

637.5951>> oo =

iterations: 17funcCount: 74stepsize: 1

algorithm: ’medium-scale: SQP, Quasi-Newton, line-search’firstorderopt: 1.8268e-006cgiterations: []

message: [1x142 char]

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 187 / 190

Optimização com restrições com o MATLAB

Resolução

Inspecção>> ll =

lower: [2x1 double]upper: [2x1 double]eqlin: [1x0 double]

eqnonlin: -8.5013ineqlin: [1x0 double]

ineqnonlin: [1x0 double]>> gg =

451.697390.3395

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 188 / 190

Optimização com restrições com o MATLAB

Interpretação geométrica do problema

x1

x 2

1 1.5 2 2.5 3 3.5 4 4.5 53

3.5

4

4.5

5

5.5

6

6.5

7

Solução encontrada

Região admissível

Região nãoadmissível

Restriçao

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 189 / 190

Optimização com restrições com o MATLAB

E as dimensões da caixa?

CaixaA 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

A. Ismael F. Vaz (UMinho) Optimização Bioinformática 07/08 190 / 190