Hispanopedia Wiki
Articulo de referencia

división de variables

En matemáticas aplicadas y ciencias de la computación , la división de variables es un método de descomposición que relaja un conjunto de restricciones . [ 1 ] Detalles Cuando l...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas aplicadas y ciencias de la computación , la división de variables es un método de descomposición que relaja un conjunto de restricciones . [ 1 ]

Detalles

Cuando la variableincógnita{\displaystyle x}aparece en dos conjuntos de restricciones, es posible sustituir las nuevas variables.incógnita1{\displaystyle x_{1}} en las primeras restricciones yincógnita2{\displaystyle x_{2}} en el segundo, y luego unir las dos variables con una nueva restricción de " enlace ", [ 2 ] que requiere que

incógnita1=incógnita2{\displaystyle x_{1}=x_{2}}

Esta nueva restricción de enlace puede relajarse con un multiplicador de Lagrange ; en muchas aplicaciones, un multiplicador de Lagrange puede interpretarse como el precio de la igualdad entreincógnita1{\displaystyle x_{1}} yincógnita2{\displaystyle x_{2}} en la nueva restricción.

Para muchos problemas, relajar la igualdad de las variables divididas permite descomponer el sistema, lo que posibilita la resolución de cada subsistema por separado. Esto reduce significativamente el tiempo de cálculo y el uso de memoria. Resolver el problema relajado con división de variables puede proporcionar una solución aproximada al problema inicial. Utilizar una solución aproximada como un "punto de partida" facilita la resolución iterativa del problema original con solo la variable.incógnita{\displaystyle x}.

Esto fue introducido por primera vez por Jörnsten, Näsberg y Smeds en 1985. [ 3 ] Al mismo tiempo, M. Guignard y S. Kim introdujeron la misma idea bajo el nombre de "Descomposición lagrangiana" (sus artículos aparecieron en 1987). [ 4 ]

Referencias

  1. ↑ Pipatsrisawat, Knot; Palyan, Akop; Chavira, Mark; Choi, Arthur; Darwiche, Adnan (2008). "Resolución de problemas Max-SAT ponderados en un espacio de búsqueda reducido: un análisis de rendimiento" . Journal on Satisfiability Boolean Modeling and Computation . 4(2008). UCLA: 4. Recuperado el 18 de abril de 2022 .
  2. ↑ Vanderbei (1991)
  3. ↑ Kurt O. Jörnsten, Mikael Näsberg, Per A. Smeds. (1985) "División de variables: un nuevo enfoque de relajación lagrangeana para algunos modelos de programación matemática" Volúmenes 84-85 de LiTH MAT R.: Matematiska Institutionen Publisher - Universidad de Linköping, Departamento de Matemáticas,
  4. ↑ Monique Guignard y Siwhan Kim. (1987) "Descomposición lagrangiana: un modelo que produce límites más fuertes", Autores Mathematical Programming, 39(2), pp. 215-228.

Bibliografía

  • Adlers, Mikael; Björck, Åke (2000). "Estiramiento de matrices para problemas de mínimos cuadrados dispersos". Álgebra lineal numérica con aplicaciones . 7 (2): 51– 65. doi : 10.1002/(sici)1099-1506(200003)7:2 < 51::aid-nla187 > 3.0.co ; 2-o . ISSN 1099-1506 . 
  • Alvarado, Fernando (1997). "Métodos de ampliación de matrices y su aplicación". BIT Numerical Mathematics . 37 (3): 473– 505. CiteSeerX 10.1.1.24.5976 . doi : 10.1007/BF02510237 . S2CID 120358431 .  
  • Grcar, Joseph (1990). Estiramiento de matrices para ecuaciones lineales (Informe técnico). Laboratorios Nacionales Sandia. arXiv : 1203.2377 . Bibcode : 2012arXiv1203.2377G . SAND90-8723.
  • Vanderbei, Robert J. (julio de 1991). "División de columnas densas en sistemas lineales dispersos" . Álgebra lineal y sus aplicaciones . 152 : 107–117 . doi : 10.1016/0024-3795(91)90269-3 . ISSN 0024-3795 . 
  • Jörnsten, Kurt O.; Näsberg, Mikael; Smeds, Per A. (1985). "Variable Splitting: A New Lagrangean Relaxation Approach to Some Mathematical Programming Models". LiTH MAT R . 84– 85. Universidad de Linköping, Departamento de Matemáticas: 1– 52.
  • Guignard, Monique; Kim, Siwhan (1987). "Descomposición lagrangiana: un modelo que produce límites más fuertes". Mathematical Programming . 39 (2): 215– 228. doi : 10.1007/BF02592948 . hdl : 2027.42/6740 .
Lecturas relacionadas
6 articulos
Matemáticas aplicadasMatemáticas aplicadasLas soluciones eficientes al problema de enrutamiento de vehículos requieren herramientas de optimización combinatoria y programación entera . Las ...Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...{\displaystyle A\mathbf {x} =\mathbf {b} }Descomposición matricialEn la disciplina matemática del álgebra lineal , una descomposición matricial o factorización matricial es una factorización de una matriz en un pr...Restricción (matemáticas)Restricción (matemáticas)En matemáticas , una restricción es una condición de un problema de optimización que la solución debe satisfacer. Existen varios tipos de restricci...{\displaystyle x\in \mathbb {R} ^{n}}relajación lagrangianaEn el campo de la optimización matemática , la relajación lagrangiana es un método que aproxima un problema complejo de optimización con restriccio...{\displaystyle {\mathcal {L}}(x,\lambda )\equiv f(x)+\langle \lambda ,g(x)\rangle }Multiplicador de LagrangeEn optimización matemática , el método de los multiplicadores de Lagrange es una estrategia para encontrar los máximos y mínimos locales de una fun...