라그랑주 쌍대성 (Lagrangian Duality)
쉽게 풀면
어떤 최적화 문제를 직접 풀기 어려울 때, 그 문제와 짝을 이루는 '거울상' 문제를 대신 풀어서 원래 문제의 답에 대한 힌트나 한계를 얻는 방법이다. 원문제가 최솟값을 찾는 문제라면, 쌍대문제는 그 최솟값보다 항상 작거나 같은 값 중 가장 큰 값을 찾는 문제가 된다. 볼록 최적화에서는 두 문제의 답이 정확히 일치하는 경우가 많아, 더 다루기 쉬운 쪽을 골라 풀 수 있다는 실용적 장점이 있다.
왜 중요한가
라그랑주 쌍대성은 직접 풀기 어려운 제약 최적화 문제를 더 다루기 쉬운 형태로 바꿔주기 때문에, 최적화 이론 자체뿐 아니라 그 이론을 응용하는 기계학습, 운용과학, 신호처리 등 여러 분야에서 계산상의 핵심 도구로 쓰입니다. 또한 쌍대문제의 최적값이 원문제 최적값의 한계를 알려준다는 점에서, 알고리즘이 실제로 얼마나 최적해에 가까운지를 평가하는 이론적 근거로도 활용됩니다. 이런 이유로 최적화를 다루는 논문의 이론적 배경 부분에서 자주 등장합니다.
논문에서는 이렇게 쓰입니다
서포트 벡터 머신 등 여러 머신러닝 알고리즘이 라그랑주 쌍대성을 통해 더 풀기 쉬운 형태로 재구성된다.
네트워크 자원 할당처럼 여러 제약이 얽힌 대규모 문제를 쌍대문제로 바꾸어 나누어 풀 수 있게 했다는 뜻이다.
운용과학의 조합최적화 연구에서 쌍대문제가 제공하는 한계값을 활용해 탐색 알고리즘의 효율을 높인 사례다.
조금 더 깊게 보면
원문제의 최적값과 쌍대문제의 최적값 사이에는 항상 일정한 간격(쌍대격차)이 존재할 수 있는데, 이 간격이 0인 경우를 강쌍대성이라 부르고 볼록 최적화 문제에서는 슬레이터 조건 같은 특정 조건이 만족될 때 이 강쌍대성이 성립함이 알려져 있습니다. 강쌍대성이 성립하지 않는 비볼록 문제에서도 쌍대문제의 값은 여전히 원문제 최적값의 하한을 제공하기 때문에, 알고리즘이 찾은 해가 최적해에서 얼마나 떨어져 있는지 가늠하는 용도로 유용하게 쓰입니다. 쌍대문제를 유도하는 과정에서 나타나는 KKT 조건은 원문제와 쌍대문제의 해가 만족해야 하는 연결 고리 역할을 합니다.
주의할 점
강쌍대성(원문제와 쌍대문제의 최적값이 정확히 일치하는 성질)은 특정 조건(예: 슬레이터 조건)이 만족될 때만 보장된다.