Details
When the variable ''x'' appears in two sets of constraints, it is possible to substitute the new variables ''x''1 in the first constraints and ''x''2 in the second, and then join the two variables with a new "''linking''" constraint, which requires that : ''x''1=''x''2. 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 ''x''1 and ''x''2 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). This was first introduced by Kurt O. Jörnsten, Mikael Näsberg, Per A. Smeds in 1985. At the same time, M. Guignard and S. Kim introduced the same idea under the name Lagrangean Decomposition (their papers appeared in 1987). The original references are (1) Variable Splitting: A New Lagrangean Relaxation Approach to Some Mathematical Programming Models Authors Kurt O. Jörnsten, Mikael Näsberg, Per A. Smeds Volumes 84-85 of LiTH MAT R.: Matematiska Institutionen Publisher - University of Linköping, Department of Mathematics, 1985 Length - 52 pages; and (2) Lagrangean Decomposition: A Model Yielding Stronger Bounds, Authors Monique Guignard and Siwhan Kim, Mathematical Programming, 39(2), 1987, pp. 215-228. Reprinted as Appendix A, in Mikael Adlers, 2000, ''Topics in Sparse Least Squares Problems'', Linkoping Studies in Science and Technology", Linkoping University, Sweden.References
Bibliography
* * * * {{cite journal, first=Robert J., last=Vanderbei, authorlink=Robert J. Vanderbei, title=Splitting dense columns in sparse linear systems, journal=Linear Algebra and Its Applications, volume=152, date=July 1991, pages=107–117, issn=0024-3795 , doi= 10.1016/0024-3795(91)90269-3 , doi-access=free Decomposition methods