para imprimir

OPTIMIZAÇÃO NÃO LINEAR
Opção IV - LESI
Interface de ligação ao AMPL
2004/2005
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
1
Esquema de ligações
.nl file
.col file
.row file
Standard
Input
SIPAMPL
interface
routines
AMPL
interface
routines
AMPL
Files
(sipampl2.c and .m files)
.sol file
finite
solver
A. Ismael F. Vaz - Departamento de Produção e Sistemas
MATLAB to
SIPAMPL
interface routines
SIP
solver
MATLAB
solver
(NSIPS)
(fseminf)
Optimização não linear - Opção IV - LESI
Exemplo em AMPL - hs014.mod
var x {1..2};
minimize obj:
(x[1] - 2)^2 + (x[2]-1)^2;
subject to constr1: x[1]^2/4 + x[2]^2 <= 1;
subject to constr2: x[1] - 2*x[2] = -1;
let x[1] := 2;
let x[2] := 2;
A. Ismael F. Vaz - Departamento de Produção e Sistemas
2
Optimização não linear - Opção IV - LESI
#printf "optimal solution as starting point \n";
#let x[1] := 0.822876;
#let x[2] := 0.911438;
solve;
display x;
display obj;
display obj - 9 + 2.875*sqrt(7);
A. Ismael F. Vaz - Departamento de Produção e Sistemas
3
Optimização não linear - Opção IV - LESI
4
Comentários
Problema com n = 2, m = 2 (uma restrição de desigualdade e uma de
igualdade).
Aproximação inicial x = (2, 2)T .
Solução do problema como comentário.
O comando solve indica ao AMPL que se pretende resolver o problema.
O AMPL escreve um ficheiro temporário de extensão .nl e executa o
solver com os argumentos stub -AMPL. Como não se usou a opção
solver (por exemplo option solver loqo;) o AMPL executa o solver
por defeito (minos). O AMPL suspende a sua execução até que o solver
termine e produza um ficheiro de extensão .sol.
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
5
Obter o ficheiro .nl
O AMPL remove os ficheiros temporário.
Para obtermos o ficheiro usa-se a instrução write gstub;. Por exemplo,
depois de removido o comando solve do ficheiro hs014.mod faz-se:
ampl: model hs014.mod;
x [*] :=
1 2
2 2;
obj = 1
obj - 9 + 2.875*sqrt(7) = -0.393465
ampl: write ghs014;
Obtendo-se o ficheiro hs014.nl, colocado no directório corrente.
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
6
Interface do AMPL
A interface do AMPL (ligação entre o AMPL e o solver ) fornece um
conjunto de estruturas e subrotinas que permitem:
• carregar o problema para a memória (ler o ficheiro .nl);
• obter os dados relativos ao problema (n, m, limites simples, etc.)
• obter o valor da função objectivo, das restrições e das suas derivadas (1as
e 2as).
• guardar a solução encontrada (escrever o ficheiro .sol);
• carregar um conjunto externo de funções (biblioteca dinâmica).
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
A estrutura ASL (AMPL/Solver interface
Library)
A estrutura ASL contém grande parte dos dados relativos ao problema. A
inclusão do ficheiro de cabeçalho (header file) getstub.h inclui também o
ficheiro asl.h. O ficheiro asl.h fornece também uma lista de #defines
para facilitar o acesso ao apontador asl declarado.
A memória para o apontador asl é alocada com
asl = ASL alloc(ASL Type );
e o ficheiro aberto com
FILE *jac dim(ASL *asl, char *stub, int *m, int *n, int *no, int *nz,
int *mxr, int *mxc, (fint)strlen(stub));
A. Ismael F. Vaz - Departamento de Produção e Sistemas
7
Optimização não linear - Opção IV - LESI
Funções de carregamento
As possibilidades
Função reader
f read
fg read
fgh read
pfg read
pfgh read
para o ASL
ASL Type
ASL read
ASL read
ASL read
ASL read
Type são
informação
f
sem derivadas
fg
primeiras derivadas
fgh segundas derivadas
pfg primeiras derivadas
com estruturas de separação
ASL read pfgh segundas derivadas
com estruturas de separação
O protótipo das funções reader é
int reader (FILE *nl, int flags);
A. Ismael F. Vaz - Departamento de Produção e Sistemas
8
Optimização não linear - Opção IV - LESI
9
Componentes ASL
Componente
LUrhs
Tipo
real*
LUv
real*
Urhsx
Uvx
X0
havex0
real*
real*
real*
char*
n con
n obj
objtype
pi0
want deriv
int
int
char*
real*
int
Descrição
Array de limites inferiores (e se Urhsx nulo, superiores) nas restrições
Array de limites inferiores (e se Uvx nulo, superiores)
nas variáveis
Array de limites superiores nas restrições
Array de limites superiores nas variáveis
Aproximação inicial primal
Se não nulo havex0[i]!=0 significa que X[i] foi
especificado
Número de restrições
Número de funções objectivo
Tipo de função objectivo: 0 == min, 1 == max
Aproximação inicial dual
==0 não linear sem derivadas, ==1 não linear com
derivadas
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
Avaliação das funções não lineares
Função objectivo
real objval(int nobj, real *x, fint *nerror)
Gradiente da função objectivo
void objgrd(int nobj, real *x, real *g, fint *nerror)
Restrições
void conval(real *x, real *r, fint *nerror)
Jacobiano
void jacval(real *x, real *j, fint *ne)
Uma restrição
real conival(int ncon, real *x,fint *nerror)
A. Ismael F. Vaz - Departamento de Produção e Sistemas
10
Optimização não linear - Opção IV - LESI
11
Gradiente de uma restrição
void congrd(int ncon, real *x, real *g, fint *nerror)
Produto da Hessiana por um vector (último valor de x)
void hvcomp(real *hv, real *P, int nobj, real *ow, real
*y)
hv=WP em que

W = ∇2 
n obj−1
X
i=0
ow[i]fi + σ
n X
con−1

y[i]ci
i=0
σ é usualmente +1 (defeito) ou −1 e pode ser modificado com
void lagscale(real sigma, fint *nerror)
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
12
Calculo da Hessiana (matriz W)
fullhes(real *h, fint lh, int nobj, real *ow, real *y)
h[i + j ∗ lh] = Wi,j
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
13
Bibliografia
David M. Gay, Hooking Your Solver to AMPL, Technical report 97-4-06,
Bell Laboratories, 1997.
Disponível em www.ampl.com.
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
14
Um exemplo
#include "mlocpsoa.h"
static double objsign;
static fint NERROR = -1;
#define asl cur_ASL
char mlocpsoa_version[]="MLOCPSOA v1.1";
/* This struct member names must be in alphabetic order,
for binary search */
keyword keywds[] = {
KW("cognitial"
, mloc_opt_d, (Char*)&opt.mu,
"Cognitial parameter"),
KW("fweight"
, mloc_opt_d, (Char*)&opt.fweight,
"Final velocity weight"),
KW("halton"
, mloc_opt_i, (Char*)&opt.halton,
"Halton (=1) or uniform (=0) initial population"),
KW("iweight"
, mloc_opt_d, (Char*)&opt.iweight,
"Initial velocity weight"),
KW("maxiter"
, mloc_opt_i, (Char*)&opt.maxiter,
"Maximum iterations allowed"),
KW("maxvf"
, mloc_opt_d, (Char*)&opt.maxvfactor,
"Factor for maximum allowed velocity"),
KW("mlocal"
, mloc_opt_i, (Char*)&opt.mlocal,
A. Ismael F. Vaz - Departamento de Produção e Sistemas
Optimização não linear - Opção IV - LESI
"Multilocal (=1) or global (=0) optimization"),
KW("prog"
, mloc_opt_i, (Char*)&opt.prog,
"Number of allowed iteration without progress"),
KW("size"
, mloc_opt_i, (Char*)&opt.s,
"Swarm size"),
KW("social"
, mloc_opt_d, (char*)&opt.nu,
"Social factor (gradient factor)"),
KW("verb"
, mloc_opt_i, (char*)&opt.verb,
"Verbosity (0=quiet,1=short info,2=all info)"),
};
struct Option_Info Oinfo = { "mlocpsoa", "MLOCPSOA", "mlocpsoa_options",
keywds, nkeywds, 1, mlocpsoa_version, 0, NULL};
/**********************************************
Set options. String type
**********************************************/
char *mloc_opt_s(Option_Info *oi, keyword *kw, char *value)
{
char *s;
/* never echo options */
oi->option_echo &= ~ASL_OI_echo;
A. Ismael F. Vaz - Departamento de Produção e Sistemas
15
Optimização não linear - Opção IV - LESI
if(!strncmp("method", kw->name, 6)){
s=value;
while(*s!=’ ’ && *s!=0)
s++;
if(s<=value)
return value;
if(!strncmp("disc_hett", value, 9)){
*(int *)kw->info=0; /*DISC_METHOD;*/
printf("Discretization method selected Hettich version\n");
return s;
}
/* unknown method */
return value;
}
/* not implemented option */
return value;
}
/**********************************************
Set options. Integer type
**********************************************/
char *mloc_opt_i(Option_Info *oi, keyword *kw, char *value)
{
A. Ismael F. Vaz - Departamento de Produção e Sistemas
16
Optimização não linear - Opção IV - LESI
long optval;
char *s;
/* never echo options */
oi->option_echo &= ~ASL_OI_echo;
optval=strtol(value, &s, 10);
if(s > value){
/* existing integer number */
*(int *)kw->info=(int)optval;
if(opt.verb)
printf("\nDefault option %s=%d accepted\n", kw->name, *(int *)kw->info);
return s;
}
return value;
}
/**********************************************
Set options. Double type
**********************************************/
char *mloc_opt_d(Option_Info *oi, keyword *kw, char *value)
{
double optval;
char *s;
/* never echo options */
oi->option_echo &= ~ASL_OI_echo;
A. Ismael F. Vaz - Departamento de Produção e Sistemas
17
Optimização não linear - Opção IV - LESI
optval=strtod(value, &s);
if(s > value){
/* existing double number */
*(double *)kw->info=optval;
if(opt.verb)
printf("\nDefault option %s=%.6f accepted\n", kw->name, *(double *)kw->info);
return s;
}
return value;
}
static Jmp_buf Jb;
void catchfpe(int n)
{
report_where(asl);
printf("\nFloating point error.\n");
fflush(stdout);
longjmp(Jb.jb,1);
}
int main(int argc, char **argv)
{
char *stub;
A. Ismael F. Vaz - Departamento de Produção e Sistemas
18
Optimização não linear - Opção IV - LESI
ASL *asl;
FILE *nl;
fint m, n, no, nz, mxr, mxc;
int i,
double
double
double
exit_code, warnings=0;
*sol=NULL;
*f=NULL;
*lb, *ub, *lbt, *ubt, *tmp;
asl = ASL_alloc(ASL_read_fg);
stub = getstops(argv, &Oinfo);
nl=jac_dim_ASL(asl, stub, &m, &n, &no, &nz, &mxr, &mxc, (fint)strlen(stub));
if (!nl){
printf("Error: Can’t read problem\n");
exit(1);
}
if(m){
printf("\n\nWarning:\n");
printf("Warning: Problem has %d constraint",m);
if(m>1)printf("s\n");
else printf("\n");
printf("Warning: MLOCPSOA does not support constrained optimization problems\n", m);
printf("Warning: Constraints will be ignored\n", m);
printf("Warning:\n");
A. Ismael F. Vaz - Departamento de Produção e Sistemas
19
Optimização não linear - Opção IV - LESI
warnings++;
};
want_deriv = opt.mlocal; /* no derivs in the global case */
fg_read_ASL(asl, nl, 0);
if(n_obj<1){
printf("Error: At least one objective is requested\n");
exit(1);
}
if(n_obj>1){
printf("\nWarning: Current implentation only supports one objective function\n");
printf("\nWarning: Considering only the first objective\n");
warnings++;
}
dense_j();
objsign = objtype[0] ? 1. : -1.;
/* objsign = -1 minimization problem */
/* objsign = 1 maximization problem */
err_jmp1 = &Jb;
if (!setjmp(Jb.jb)){
A. Ismael F. Vaz - Departamento de Produção e Sistemas
20
Optimização não linear - Opção IV - LESI
signal(SIGFPE, catchfpe);
/* lower and upper bounds on variables */
lbt=lb=malloc(n*sizeof(double));
ubt=ub=malloc(n*sizeof(double));
if(!lb || !ub){
printf("Error: Unable to allocate memory for variable bounds\n");
exit(1);
}
tmp=LUv;
for(i=0;i<n;i++){
if(*tmp<-Inf){
printf("\nWarning: Lower bound on variable %d not set\n",i);
warnings++;
}
*lbt++=*tmp++;
if(*tmp>Inf){
printf("\nWarning: Upper bound on variable %d not set\n",i);
warnings++;
}
*ubt++=*tmp++;
}
exit_code=mlocpsoa(n, &objfun, lb, ub, &sol, f);
write_sol("Solution found by MLOCPSOA", sol, NULL, &Oinfo);
}
/* free allocated memory */
A. Ismael F. Vaz - Departamento de Produção e Sistemas
21
Optimização não linear - Opção IV - LESI
free(lb);
free(ub);
free(sol);
if(warnings){
if(warnings==1)printf("\nWarning: There was 1 warning\n");
else printf("\nWarning: There were %d warnings\n", warnings);
}
if(opt.verb)printf("\n%s\n", exit_codes[exit_code].msg);
return exit_code;
}
/*
Function to be passed to the mlocpsoa function.
args in:
n -> dimension
x -> point
mode -> 0: only objective
1: only gradient
2: objective and gradient
args out:
grd -> gradient of objective at x
*/
double objfun(int n, double *x, int mode, double *grd)
{
double *g;
A. Ismael F. Vaz - Departamento de Produção e Sistemas
22
Optimização não linear - Opção IV - LESI
if(mode && grd){
objgrd(0, x, grd, NULL);
if(objsign < 0)
for(g=grd+n-1;g>=grd;g--)
*g=-*g;
}
if(mode!=1)
return objsign*objval(0,x,NULL);
else
return 0.0;
}
A. Ismael F. Vaz - Departamento de Produção e Sistemas
23