슬랙 변수 - RosettaLens 번역

슬랙 변수

ko생성일: 2025. 12. 11.갱신일: 2025. 12. 11.

최적화 문제에서 부등식 제약을 등식 제약으로 바꾸기 위해 도입하는 슬랙 변수와 그 기하학적 의미를 설명한다.

슬랙 변수

위키백과, 우리 모두의 백과사전

최적화 문제에서 **슬랙 변수(slack variable)**는 부등식 제약식을 등식 제약식으로 바꾸기 위해 제약식에 추가하는 변수이다. 이때 슬랙 변수에 대해서도 0 이상이라는 비음수 제약을 함께 둔다.[1]: 131

슬랙 변수는 특히 선형 계획법에서 사용된다. 확장된 제약식에 포함되는 다른 변수들과 마찬가지로, 슬랙 변수는 음수가 될 수 없는데, 이는 심플렉스 알고리즘이 이들 변수가 0 이상(양수 또는 0)일 것을 요구하기 때문이다.[2]

어떤 제약식에 대응하는 슬랙 변수가 특정 후보 해에서 0이면, 그 지점에서 해당 제약식은 **구속적(binding)**이다. 이 경우 그 제약식이 그 지점에서의 가능한 변화 방향을 실제로 제한하고 있다는 뜻이다.
슬랙 변수가 특정 후보 해에서 양수이면, 그 지점에서 그 제약식은 **비구속적(non-binding)**이다. 이 경우 그 제약식은 그 지점에서의 가능한 변화 방향을 제한하지 않는다.
슬랙 변수가 어떤 점에서 음수라면, 그 점은 해당 제약식을 만족하지 못하므로 불능해(infeasible)이다(허용되지 않는 해).

슬랙 변수는 Big M 방법에서도 사용된다.

슬랙 변수 $Image 1: {\displaystyle \mathbf {s} \geq \mathbf {0} }$ 을 도입하면, 부등식 $Image 2: {\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$ 을 다음과 같은 등식으로 바꿀 수 있다. $Image 3: {\displaystyle \mathbf {A} \mathbf {x} +\mathbf {s} =\mathbf {b} }$

임의 정사분면으로의 매장

슬랙 변수들은 폴리토프를 표준 f-정사분면(orthant) $Image 4: {\displaystyle P\hookrightarrow (\mathbf {R} _{\geq 0})^{f}}$ 에 매장(embedding)하는 사상을 제공한다. 여기서 $Image 5: {\displaystyle f}$ 는 제약식(폴리토프의 면, facet)의 개수이다. 이 사상은 일대일(슬랙 변수가 유일하게 결정됨)이지만, 전사 사상은 아니다(모든 조합이 실제로 실현될 수 있는 것은 아니다). 그리고 이 사상은 제약식(선형 함수, 코벡터)의 관점에서 표현된다.

슬랙 변수는 일반화 바리센트릭 좌표에 대해 _쌍대적_이다. 일반화 바리센트릭 좌표들은 (하나의 점에 대해) 유일하지 않지만 모두 실현 가능한 반면, 슬랙 변수는 유일하게 결정되지만 그 모든 조합이 실현 가능한 것은 아니라는 점에서 대조적이다.

쌍대적으로, 일반화 바리센트릭 좌표는 (면에 쌍대인) 꼭짓점이 $Image 6: {\displaystyle n}$ 개인 폴리토프를, 차원과 상관없이, $Image 8: {\displaystyle n}$ 개의 꼭짓점을 갖는 표준 $Image 7: {\displaystyle (n-1)}$ -심플렉스의 _상(image)_로 표현한다. 즉, 이 사상은 전사이다: $Image 9: {\displaystyle \Delta ^{n-1}\twoheadrightarrow P,}$ 그리고 점들을 꼭짓점(점, 벡터)을 기준으로 표현한다. 이 사상이 일대일이 되는 것은 폴리토프가 심플렉스인 경우에 한하며, 이때 이 사상은 동형사상이 된다. 이는 한 점의 일반화 바리센트릭 좌표가 _유일하지 않다_는 사실에 대응한다.

각주

^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. 2011년 10월 15일에 확인함.
^ Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.: 42

외부 링크

슬랙 변수 튜토리얼 - 슬랙 변수 문제를 온라인으로 풀어보기

임의 정사분면으로의 매장

각주

^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. 2011년 10월 15일에 확인함.

^ Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.: 42

외부 링크

슬랙 변수 튜토리얼 - 슬랙 변수 문제를 온라인으로 풀어보기