Autor Tema: KKT, Lagrange y Binario

0 Usuarios y 2 Visitantes están viendo este tema.

22 Noviembre, 2016, 04:23 pm
Leído 1811 veces

Lagu

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 14
  • Karma: +0/-0
  • Sexo: Masculino
Saludos!

Bueno antes que nada se que hay otras formas de resolver este ejercicio, pero tengo interes en saber que estoy realizando mal plis...

EL problema es inventado solo de ejemplo para plantear esto, basicamente transformar restricciones binarias a ecuaciones y utilizarlas dentro de Lagrange tratando de evadir otros algoritmos.

\(
Min: -x - y
 \)
\(
y + 2*x -5 <= 0
 \)
\(
x, y\in{\left\{{0, 1}\right\}}
 \)

Bueno, como sabemos podriamos probar todas las combinaciones ya que son 4 pero no es la idea, para convertir este ejercicio lo que intento es relajar la naturaleza de las variables a irrestricta y compensar con una condicion la cual fuerza a x e y a ser 0 o 1:

\(
Min: -x - y
 \)
\(
y + 2*x -5 <= 0
 \)
\(
x*(x-1)=0
 \)
\(
y*(y-1)=0
 \)

Ahora x e y son siempre 0 o 1, seguidamente resuelvo el problema con KKT y Lagrange de forma normal:

\(
G = -x - y + L*(y + 2*x - 5) + u_1*(x*(x-1)) + u_2*(y*(y-1))
 \)

\(
\frac{dG}{dx} = -1 + 2*L + 2*u_1*x - u_1 = 0
 \)
\(
\frac{dG}{dy} = -1 + L + 2*u_2*y - u_2 = 0
 \)
\(
L*(y + 2*x - 5) = 0
 \)
\(
u_1*(x*(x-1)) = 0
 \)
\(
u_2*(y*(y-1)) = 0
 \)
\(
L >= 0
 \)

Ahora se resuelve el sistema de ecuaciones, aunque le dejo el trabajo a wolframalpha:

https://www.wolframalpha.com/input/?i=solve+-1+%2B+2*L+%2B+2*u1*x-u1%3D0;-1+%2B+L+%2B+2*u2*y-u2%3D0;L*(y+%2B+2*x+-+5)%3D0;u1*x*(x-1)%3D0;u2*y*(y-1)%3D0;L%3E%3D0

Pero como vemos el sistema nos arroja todas las combinaciones de x e y (junto con algunas soluciones infactibles)............
Aunque claramente la solución es (1, 1)...

Nota, no uso mucho el lenguaje matematico, por lo que me pude haber equivocado al representar algo, cualquier error diganme plis.

Muchas Gracias!

22 Noviembre, 2016, 06:13 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Saludos!

Bueno antes que nada se que hay otras formas de resolver este ejercicio, pero tengo interes en saber que estoy realizando mal plis...

EL problema es inventado solo de ejemplo para plantear esto, basicamente transformar restricciones binarias a ecuaciones y utilizarlas dentro de Lagrange tratando de evadir otros algoritmos.

\(
Min: -x - y
 \)
\(
y + 2*x -5 <= 0
 \)
\(
x, y\in{\left\{{0, 1}\right\}}
 \)

Bueno, como sabemos podriamos probar todas las combinaciones ya que son 4 pero no es la idea, para convertir este ejercicio lo que intento es relajar la naturaleza de las variables a irrestricta y compensar con una condicion la cual fuerza a x e y a ser 0 o 1:

\(
Min: -x - y
 \)
\(
y + 2*x -5 <= 0
 \)
\(
x*(x-1)=0
 \)
\(
y*(y-1)=0
 \)

Ahora x e y son siempre 0 o 1, seguidamente resuelvo el problema con KKT y Lagrange de forma normal:

\(
G = -x - y + L*(y + 2*x - 5) + u_1*(x*(x-1)) + u_2*(y*(y-1))
 \)

\(
\frac{dG}{dx} = -1 + 2*L + 2*u_1*x - u_1 = 0
 \)
\(
\frac{dG}{dy} = -1 + L + 2*u_2*y - u_2 = 0
 \)
\(
L*(y + 2*x - 5) = 0
 \)
\(
u_1*(x*(x-1)) = 0
 \)
\(
u_2*(y*(y-1)) = 0
 \)
\(
L >= 0
 \)

Ahora se resuelve el sistema de ecuaciones, aunque le dejo el trabajo a wolframalpha:

https://www.wolframalpha.com/input/?i=solve+-1+%2B+2*L+%2B+2*u1*x-u1%3D0;-1+%2B+L+%2B+2*u2*y-u2%3D0;L*(y+%2B+2*x+-+5)%3D0;u1*x*(x-1)%3D0;u2*y*(y-1)%3D0;L%3E%3D0

Pero como vemos el sistema nos arroja todas las combinaciones de x e y (junto con algunas soluciones infactibles)............
Aunque claramente la solución es (1, 1)...

Nota, no uso mucho el lenguaje matematico, por lo que me pude haber equivocado al representar algo, cualquier error diganme plis.

Muchas Gracias!

No he revisado en detalle tus cuentas.

Pero imponer condiciones del tipo \( x(x-1)=0 \) y aplicar Lagrange hace que al analizar la nulidad de las parciales y buscar puntos críticos te quede la ecuación \( x(x-1)=0 \) cuyas soluciones \( x=0 \) ó \( x=1 \). Lo mismo para \( y \). Dicho de otra manera no escapas de tener que analizar las combinaciones de esos dos pares de soluciones.

Saludos.

22 Noviembre, 2016, 06:45 pm
Respuesta #2

Lagu

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 14
  • Karma: +0/-0
  • Sexo: Masculino
Saludos, gracias por la respuesta, la verdad es que me pierdo un poco, es verdad que queda ese tipo de condicion, y que tendra dos soluciones siempre, pero sus parciales son otra cosa:
\(
\frac{{\partial f}}{{\partial x}} = 2x + 1
 \)

Como tal a pesar de tener valores relativamente definidos sus parciales siguen existiendo (excepto en y).

Solo como extra, si las condiciones se anulan debido a este efecto por que no desaparecen los multiplicadores de Lagrange si desde un principio sabemos que van a ser 0 los productos?

\(
G = f + \displaystyle\sum_{i=1}^n{u_i*K}
 \)

Donde K son las restricciones, pero debido al teorema de dualidad al aplicar esto se crean las restricciónes:

\(
u_i*K = 0
 \)

Como tal se anularia la sumatoria de la funcion de Lagrange, lo unico que se me ocurre es que aunque pase este caso no puede ser simplificable.

Siento un poco de colision de conceptos.

Muchas Gracias.

22 Noviembre, 2016, 11:16 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Saludos, gracias por la respuesta, la verdad es que me pierdo un poco, es verdad que queda ese tipo de condicion, y que tendra dos soluciones siempre, pero sus parciales son otra cosa:
\(
\frac{{\partial f}}{{\partial x}} = 2x + 1
 \)

Como tal a pesar de tener valores relativamente definidos sus parciales siguen existiendo (excepto en y).

Solo como extra, si las condiciones se anulan debido a este efecto por que no desaparecen los multiplicadores de Lagrange si desde un principio sabemos que van a ser 0 los productos?

\(
G = f + \displaystyle\sum_{i=1}^n{u_i*K}
 \)

Donde K son las restricciones, pero debido al teorema de dualidad al aplicar esto se crean las restricciónes:

\(
u_i*K = 0
 \)

Como tal se anularia la sumatoria de la funcion de Lagrange, lo unico que se me ocurre es que aunque pase este caso no puede ser simplificable.

Siento un poco de colision de conceptos

Para ser sincero me cuesta entender exactamente qué quieres decir.

Insisto en lo que te dije antes: lo que resulta de enfocar el problema con Lagrange tal como lo has hecho es que los cuatro posibles pares de valores de \( (x,y) \) son puntos críticos. Es decir no nos soluciona nada. Es razonable teniendo en cuenta que Lagrange localiza extremos locales, y en un conjunto discreto todos los puntos son aislados, son puntos extremos en un entorno de ellos mismos, ya que de hecho son el único punto de ese entorno.

Saludos.

23 Noviembre, 2016, 02:53 am
Respuesta #4

Lagu

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 14
  • Karma: +0/-0
  • Sexo: Masculino
:O, Muchas gracias, lo que no tenia claro es que Lagrange solo funcionaba con locales, ahora tiene sentido.

¿existe alguna extension o algun otro metodo para globales?

Saludos!

23 Noviembre, 2016, 10:45 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

:O, Muchas gracias, lo que no tenia claro es que Lagrange solo funcionaba con locales, ahora tiene sentido.

¿existe alguna extension o algun otro metodo para globales?

En optimización continua, Lagrange permite reducir el problema de buscar extremos globales, a estudiar que ocurre en unos pocos puntos (los extremos locales).

Pero tu quieres solucionar un problema de optimización en un conjunto discreto de puntos. Hay toda una teoría sobre esto:

http://wwwhome.math.utwente.nl/~kernw/lectures/DO/DO_script.pdf

Saludos.