Optimización Avanzada
Taller de Trabajo
el problema del caballo
R. Meziat + Estudiantes
motivación:
inteligencia artificial




encontrar el camino
para llegar de una
esquina a otra del
tablero
eludir el ataque de
una o más torres
modelo como control
discreto
relajación como
programa convexo:
PSD
OBJETIVO:
ALCANZAR LA META EVADIENDO EL ATAQUE DE LA TORRE
MODELO COMO PROBLEMA DE
CONTROL DISCRETO










Variables de estado: x e y,
Posición en el tablero.
Condiciones iniciales: x=0, y=0.
Variables de control: u y v,
Avance en cada jugada.
Número de jugadas: N
Variable temporal: t=1,…,N.
Número de torres: m.
Posiciones de las torres: (xj,yj),j=1,…,m.
Posición de la meta: (XF,YF)=(8,8).
Modelo de Optimización
otros parámetros

PX : posiciones de las
torres en x

Py : posiciones de las
torres en y

MC: movimientos del
caballo
Problema de optimización








Función objetivo cuadrática
Restricciones lineales
Variables discretas
Restricciones discretas
Relajación convexa
Programa semidefinido
Métodos de punto interior
Problema polinomial
Relajación en Medidas





Dominio X
Distribuciones de
probabilidad P(X)
Relajación exacta
Para todo programa
matemático
Relajación con forma
lineal y conjunto
factible convexo
m in f  x 
s .a .
x X
m in f , 
s .a .
  P(X )
manejo de las restricciones no
lineales



Dominio
G={gk=0,k=1,…,K}
Relajación exacta
Premisas gk no
negativas
m in
m in f
s .a .
gk
f ,
 0, k  1, ..., K
  P(X )
x
x X
s .a .
gk , 
x
 0, k  1, ..., K
Problemas polinomiales

Transformación en forma lineal
en momentos
n
f 
ct
i
i
 c f  1, t ,
i0
n
f , 
cm
i
i0
i
 cf m
,t
n

Relajaciones exactas en momentos
m in
f ,
s .a .
g k ,   0, k  1, ..., K
  P(X )
m in c f  m
s .a .
c g k  m  0, k  1, ..., K
m  M (X )
PROGRAMA MATEMÁTICO CON ESTRUCTURA LINEAL Y CONVEXA
IMPLICACIONES:
CARACTERIZACIÓN DE VARIBALES COMO MOMENTOS
DESIGUALDADES MATRICIALES Y PROGRAMAS
SEMIDEFINIDOS
Problemas de Momentos




Problemas abiertos en álgebra
Casos escalares: condiciones necesarias y
suficientes-relajaciones exactas
Casos multidimensionales: condiciones
necesarias-cotas inferiores
Ejemplo en R
• Matrices de Hankel Semidefinidas Positivas

Ejemplo en [0,2P]
• Matrices de Toeplitz Semidefinidas Positivas
Resultados de Algebra

Un polinomio de grado 2n es no
negativo en la recta real si y sólo si
se puede expresar como la suma de
los cuadrados de dos polinomios de
grado hasta n.
otro resultado de álgebra
P o lin o m io trig o n o m étrico d e g ra d o m
f : [  ,  ]  R
f  0 si y só lo si f  
m
    ke
k 0
2
ik 
Caracterización de momentos

Hasta una clausura
topológica,
tenemos que: m 0 , m 1 , ..., m 2 n
so n m o m en to s d e u n a
m ed id a p o sitiva en la recta rea l R
si y só lo si fo rm a n u n a m a triz d e
H a n kel sem id efin id a p o sitiva
 m0

m1

H 


 mn
m1
m2
m n 1
mn 

m n 1



m2n 
Caracterización de momentos

Hasta una clausura
topológica,
tenemos que:
m  n , m  n  1 , ..., m n son m om entos trigonom étricos
de una m edida positiva en (   ,  ]
si y sólo si form an una m atriz de
T oeplitz sem idefinida positiva
 m0

m1

T 


 mn
m 1
m0
m n 1
mn 

m  n 1



m0 
Desarrollo del
Problema
modelo original
función objetivo polinomial
variables de diseño

Estado

Control
restricciones lineales de igualdad
Ecuaciones de evolución
restricciones discretas
No lineales, no convexas
Representación polinomial
x  {a1 ,
, ak }  R
si y sólo si
f  x   0 donde
k
f  x     x  ai 
i 1
2
Representación en medidas
  P{a1 ,
, ak }  P ( R )
si y sólo si
f ,   0 donde
P ( X ) es la familia de distribuciones
de probabilidad en X .
Representación en momentos
m  M {a1 ,
, ak }  M ( R )
si y sólo si
c f  m  0 donde
M ( X ) es la familia de vectores de
momentos de distribuciones de
probabilidad en X .
representación convexa
x  {a1 ,
, ak }
si y sólo si
c f  m  0 donde
el vector m es un vector de momentos
de distribuciones de probabilidad en {a1 ,
, ak }
y c f es el vector del los coeficientes del polinmio
k
f  x     x  ai  .
i 1
2
representación convexa
x m
variable discreta - medida de probabilidad - momentos
Puntos
{a1 ,
Distribuciones
, ak }  P{a1 ,
Cuerpo convexo
, ak }  M {a1 ,
, ak }
aplicación en el problema
2
(1, xt , xt ,
2
(1, yt , yt ,
m 0 1
t
 0 1
t
, xt
2 nx
, yt
)  m  (m 0 ,
, m 2 nx )
)    ( 0 ,
,
2 ny
t
t
t
t
t
t
2ny
)
restricciones adicionales
Ht   m i j 
nx
0
ny
0
t
Kt   
t
i j

i , j 0
i , j 0
m 0 1
t

t
0
1
Desigualdades lineales matriciales
manejo de los controles
Simetría radial
representación polar-compleja
CAMBIO DE VARIABLES
u
5 cos  
5
2
v
5sen  
5i
2
e
 i
e
 i
e
e
i
i


5
2
1 
5i
2
1 
5
2
1
5i
2
1
MOMENTOS
TRIGONOMÉTRICOS
(e
 ki
 i
,
i
, e ,1, e ,

 j   e d   
ij

j  k ,
,k
  P(0, 2 )
, e )   k ,
ki
,1 ,0 ,1 ,
, k 
restricciones en el ángulo
  {1 ,
, 8 }
si y sólo si
g    0 con :
g    z  z1
donde z  e
i
2
z  z8
y zj  e
i j
Restricciones polinomiales
2
, con j  1,
8.
representación en momentos
g    0
si y sólo si
cg   0
donde cg son los coeficientes de g   .
nueva función objetivo
nuevas variables de diseño


Momentos
algebraicos de los
Estados
Momentos
trigonométricos del
control
nuevas restricciones lineales de
igualdad
Ecuaciones de evolución
Forma convexa de las
restricciones discretas
caracterización de momentos
desigualdades matriciales


Polinomiales en x
Polinomiales en y
Ht   m i j 
nx
0
ny
0
t
i , j 0
Kt    i  j 
t
i , j 0

Trigonométricos en 
T  i  j
t

i , j 0
n
0
relajación convexa
programa semidefinido
teoría
Proponemos una forma alternativa
para resolver problemas de control
óptimo discreto no lineal:
Min

1
Min
f ( x, u , t ) dt
0
s.a.

s.a.
x  g ( x, u , t )
u  u1 , u2 ,
x(0)  x0
, un 
x(1)  x f
Caso I: Control discreto,
sistema continuo.
 f  x ,u ,t 
i
i
i
xi 1  g ( xi , ui , ti )
u  u1 , u2 ,
x0  a
, un 
xN  b
Caso II: Control discreto,
sistema discreto.
Introducción
Técnicas clásicas: Análisis por espacio de estados, Control
BIG-BANG, Optimización dinámica
Dificultades de
linealidad:
NO LINEAL:
Integración
Inestabilidad
Caos
Singularidades
Dificultades de convexidad:
NO CONVEXO :
No aplica la teoría clásica
para
establecer
existencia
de
la
solución.
Análisis del problema
Supongamos el caso donde el control solo toma dos
valores:
Min
s.a.
 f  x ,u ,t 
i
i
i
xi 1  g ( xi , ui , ti )
u  u1
x0  a
xN  b
EL PROBLEMA ES NO
LINEAL EN EL CONTROL
!!!!!
Min
EL PROBLEMA PUEDE
NO SER CONVEXO!!!!
h(u) ES COERCIVO!
s.a.
 f  x ,u ,t 
i
i
i
xi 1  g ( xi , ui , ti )
h  u    u  u1  u  u1  u  0
2
x0  a
xN  b
2
2
Análisis del problema
Para abordar el problema de no linealidad y el
de no convexidad, utilizamos una relajación en
medidas de probabilidad.
1
Min
  f  x ,  , t  d     dt
i
i
i
0
s.t.
xi 1   g ( xi , i , ti ) d  ( )
 h(i )d  ( )  0
Espacio de control
  P()
f


co()
fd 
Obtenemos un problema definido
en la envoltura convexa del
espacio de control.
(Lineal – Convexo en
medidas de probabilidad)
Análisis del problema
La
convexificación
se
realiza
mediante
distribuciones de probabilidad, y a su vez se
discretizan por los momentos algebraicos.
N
f (u )   ci i (u )
0
N
 f (u )d   c m
i
0
mi: Momentos
i
  (mi )

co()
Análisis del problema
CARACTERIZACIÓN DE
MOMENTOS:
 m0

 m1
H m    m2

 

 mN
m1
m2

m2
m3

m3





mN 1


mN 

mN 1 
 0

 

m2 N 
Hankel Semidefinida Positiva
n
min
m
  c  x t  m  t dt
i
i, i
i
i
0
M
s.t.
xi 1   d i  x, t  mi  ti 
0
pi mi  ti   0
x0  a
xN  b
Problema de control óptimo con forma lineal para el control con
una familia convexa de controles m  co()
Casos de aplicación
Planificación de
trayectorias.
Posibilidades de movimiento:
1. Arriba
2. Abajo
3. Quieto
Punto meta
Casos de aplicación
Formulación:
N
min
N
min
x
i 0
s.t.
xi 1  xi  ui
ui  1, 0
xi  yi
2
i
i 0
2
i
x
s.t.
xi 1  xi  m1,i
m6,i  2m2,i  0
 1

m
 1,i
 m2,i

 m3,i
xi  yi
m1,i
m2,i
m2,i
m3,i
m3,i
m4,i
m4,i
m5,i
m3,i 

m4,i
0
m5,i 

m6,i 
Casos de aplicación
Trayectoria
Control
Casos de aplicación
Casos de aplicación
Control de un motor DC.
R: Resistencia eléctrica del
motor.
I: Momento de Inercia
L: Inductancia
K: Torque
i: Corriente
w: Velocidad Angular
Solo acepta tres voltajes a la
entrada (+5, -5, 0)
Casos de aplicación
Formulación I:
2
min
 i
   Vin
2
2
2
 dt
2
s.t. i  
R
i
L
0
s.t. i  
R
1
i
L

   m2  t   dt
2
0
2
min
 i
K
L
Vin
i
L
u  1, 0
i  0   i0
  0   0
 
K
1
L
m1
i
L
m6  2m2  0
1

m
 1
 m2

 m3
m1
m2
m2
m3
m3
m4
m4
m5
m3 

m4
0
m5 

m6 
Casos de aplicación
Corriente
Velocidad angular
Control
Casos de aplicación
Formulación II:
2
min
2
0
2
min
  m  t   dt
 V  dt
2
s.t. i  
in
s.t. i  
1
i
L

K
L
Vin
i
L
u  5, 0
i  0   i0
i
L
0
R
R
  0   0
 
K
1
L
m1
i
L
m6  25m2  0
1

m
 1
 m2

 m3
m1
m2
m2
m3
m3
m4
m4
m5
m3 

m4
0
m5 

m6 
Casos de aplicación
Control
Velocidad angular
Corriente
fin
Descargar

Document