Jump to content

Variable splitting

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Jmcgnh (talk | contribs) at 08:15, 17 June 2016 (Disambiguated: decomposition methoddecomposition method (constraint satisfaction)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In applied mathematics and computer science, variable splitting is a decomposition method that relaxes a set of constraints.

Details

When the variable x appears in two sets of constraints, it is possible to substitute the new variables x1 in the first constraints and x2 in the second, and then join the two variables with a new "linking" constraint,[1] which requires that

x1=x2.

This new linking constraint can be relaxed with a Lagrange multiplier; in many applications, a Lagrange multiplier can be interpreted as the price of equality between x1 and x2 in the new constraint.

For many problems, when the equality of the split variables is relaxed, then the system is decomposed, and each subsystem can be solved independently, at substantial reduction of computing time and memory storage. A solution to the relaxed problem (with variable splitting) provides an approximate solution to the original problem: further, the approximate solution to the relaxed problem provides a "warm start", a good initialization of an iterative method for solving the original problem (having only the x variable).[1][2][3]

Notes

  1. ^ a b Vanderbei (1991)
  2. ^ Alvarado (1990)
  3. ^ Adlers & Björck (2000) Reprinted as Appendix A, in Mikael Adlers, 2000, Topics in Sparse Least Squares Problems, Linkoping Studies in Science and Technology", Linkoping University, Sweden.

Bibliography

  • Adlers, Mikael; Björck, Åke (2000). "Matrix stretching for sparse least squares problems". Numerical Linear Algebra with Applications. 7 (2). John Wiley & Sons, Ltd.: 51–65. doi:10.1002/(SICI)1099-1506(200003)7:2. ISSN 1099-1506. {{cite journal}}: Invalid |ref=harv (help)
  • Alvarado, Fernando (1997). "Matrix enlarging methods and their application". BIT Numerical Mathematics. 37 (3): 473–505. doi:10.1007/BF02510237. {{cite journal}}: Invalid |ref=harv (help)
  • Grcar, Joseph (1990). Matrix stretching for linear equations (Technical report). Sandia National Laboratories. arXiv:1203.2377. SAND90-8723.
  • Vanderbei, Robert J. (July 1991). "Splitting dense columns in sparse linear systems". Linear Algebra and its Applications. 152: 107–117. doi:10.1016/0024-3795(91)90269-3. ISSN 0024-3795. {{cite journal}}: Invalid |ref=harv (help)