변수 분할

Variable splitting

응용 수학과 컴퓨터 과학에서 변수 분할은 일련의 [1]제약을 완화하는 분해 방법입니다.

세부 사항

변수 x가 두 가지 제약조건으로 나타나는 경우 첫 번째 제약조건에서 새로운 변수 x1을 대체하고 두 번째 제약조건에서 새로운 변수 x2를 대체할 수 있으며 두 변수를 새로운 "링크" [2]제약조건으로 결합할 수 있습니다.이 경우 다음과 같은 조건이 필요합니다.

x1=x2.

이 새로운 링크 제약은 라그랑주 승수로 완화될 수 있다; 많은 애플리케이션에서, 라그랑주 승수는 새로운 제약 조건에서의 x1과 x2 사이의 등가 가격으로 해석될 수 있다.

많은 문제에서 분할 변수의 동일성이 완화되면 시스템이 분해되고 컴퓨팅 시간과 메모리 저장 공간을 대폭 줄여서 각 서브시스템을 독립적으로 해결할 수 있습니다.완화된 문제에 대한 해결책(변수 분할 포함)은 원래 문제에 대한 대략적인 해결책을 제공합니다.완화된 문제에 대한 대략적인 해결책은 원래 문제를 해결하기 위한 반복적인 방법(x 변수만 있음)의 적절한 초기화인 "웜 스타트"를 제공합니다.

1985년 Kurt O. Jörnsten, Mikael Nésberg, Per A. Smeds에 의해 처음 소개되었습니다.동시에, M. Guignard와 S. Kim은 Lagrangean Dispolidation이라는 이름으로 같은 아이디어를 도입했다.원래 참고 자료는 (1) 변수 분할: 일부 수학 프로그래밍 모델 저자에 대한 새로운 라그랑주 완화 접근법 Kurt O. Jörnsten, Mikael Nésberg, Per A. Smeds Volume 84-85 of LiTH MAT R: Matematis - Institute - incitution이다.분해:더 강한 한계를 낳는 모델, 저자인 모니크 기냐르 및 김시환, 수학 프로그래밍, 39(2), 1987, 페이지 215-228.[2][3][4]

레퍼런스

  1. ^ Pipatsrisawat, Knot; Palyan, Akop; Chavira, Mark; Choi, Arthur; Darwiche, Adnan (2008). "Solving Weighted Max-SAT Problems in a Reduced Search Space: A Performance Analysis". Journal on Satisfiability Boolean Modeling and Computation (JSAT). UCLA. 4(2008): 4. Retrieved 18 April 2022.
  2. ^ a b 반데르베이(1991)
  3. ^ 알바라도 (1990년)
  4. ^ Adlers & Björck(2000) 부록 A로 전재, Mikael Adlers, 2000, Sparse Lest Square Problems, Linkoping Studies in Science and Technology, 스웨덴 Linkoping University.

참고 문헌