LP·QP·SDP와 실제 인증서

문제의 구조를 읽는 세 가지 언어

선형계획 LP는 목적과 제약이 아핀인 문제다. 볼록 이차계획 QP는 양의 준정부호인 이차 목적함수를 허용한다. 반정부호계획 SDP는 변수에 아핀하게 의존하는 대칭행렬 전체에 양의 준정부호 조건을 건다. 이차식이라고 언제나 볼록한 것은 아니다. Hessian의 부호를 확인해야 한다.

실습은 세 작은 문제족을 정확히 푼다. 파란 경계는 가능집합, 주황 선은 최적 목적함수의 지지선 또는 투영 선분이다. 사용자가 움직이는 질의점은 최적점과 별개이며 가능집합 밖에 있을 수도 있다. 이때 목적값이 작다고 좋은 해가 되지는 않는다.

삼각형 위의 선형 목적함수

T를 x₁,x₂≥0, x₁+x₂≤1인 삼각형으로 두자. 모든 점이 세 꼭짓점의 볼록결합이므로 최솟값은 min(0,c₁,c₂)다. 꼭짓점 하나를 출력해도 최적해가 유일하다는 뜻은 아니다. c=(−1,−1)이면 x₁+x₂=1인 변 전체가 최적이다.

합 제약의 승수를 λ≥0, 비음수 제약의 승수를 μ≥0으로 두면

λ=max(0,−c₁,−c₂), μᵢ=cᵢ+λ를 택하면 쌍대 하한이 꼭짓점 최솟값과 일치한다. 촘촘히 찍은 그래프 대신 모든 가능점에 적용되는 최적성 인증을 얻는다.

이차 목적함수와 투영

QP 모드는 ‖x−c‖²/2를 같은 T 위에서 최소화한다. 엄격한 볼록성 때문에 투영은 유일하다. KKT로부터 xᵢ=max(cᵢ−λ,0)를 얻는다. 양의 부분들의 합이 1 이하면 λ=0이고, 넘으면 합이 정확히 1이 되는 λ를 찾는다. 물을 같은 높이만큼 빼는 water-filling 그림으로 생각할 수 있다.

c=(2,0.5)이면 최적점 (1,0), λ=1, μ=(0,0.5), 목적값 0.625다. r=λ(1,1)−μ로 쓰면 쌍대값 c·r−‖r‖²/2−λ도 0.625다. 거리 최소화이므로 목적값이 음수가 될 수 없다는 것도 독립 검산이다.

실제 행렬 제약을 가진 SDP

다음 모드는 원판을 단순히 SDP라고 부르는 대신 실제 행렬 제약을 표시한다.

아래 2×2 항등행렬의 Schur complement는 1−a²−b²다. 따라서 가능집합은 단위원판이다. 고유값으로도 1, 1±√(a²+b²)를 얻어 같은 조건을 확인한다. 비용 벡터가 0이 아니면 최적점은 −c/‖c‖, 값은 −‖c‖다.

u=c/‖c‖, v=(1,u₁,u₂)로 두면 Z=‖c‖vvᵀ/2가 양의 준정부호인 쌍대 행렬이다. 아핀 행렬 계수와의 trace 조건이 비용 c를 재현하고, 하한 −tr Z가 최솟값과 일치한다. 최적점에서 Fv=0이므로 상보성도 확인된다. 행렬 원소 각각의 부호와 양의 준정부호성은 다른 조건이다.

직접 풀기와 적용 범위

c=(1.2,1.6)이면 최적점 (−0.6,−0.8), 값 −2다. v=(1,0.6,0.8)로 Z=vvᵀ를 만들고 trace가 2인지 계산하자. 질의점 (1,1)의 최소 고유값은 1−√2<0이므로 이 점의 목적값은 가능해의 상한이 아니다.

비용을 모두 0으로 바꾸면 LP와 SDP에는 여러 최적해가 있지만 QP의 투영은 원점 하나다. 이 차이를 목적함수의 곡률로 설명하자. 실습은 표시된 유한 문제족의 닫힌 해를 사용한다. 일반 SDP 해결기나 모든 행렬 규모에 적용되는 알고리즘은 아니며, 큰 문제에서는 수치 잔차와 종료 조건도 점검해야 한다.

더 읽기: Boyd와 Vandenberghe, Convex Optimization.