요약:

Convex 최적화에서 **라그랑지안(Lagrangian)**은 **원문제(primal problem)**의 제약조건을 목적함수에 통합한 표현이며, **듀얼 문제(dual problem)**는 이 라그랑지안을 기반으로 정의된다. 즉, 듀얼 문제는 라그랑지안의 **라그랑지안 쌍대함수(Lagrange dual function)**를 최소화 문제로부터 유도한 상계(maximization) 문제이다.

1. 라그랑지안 정의

제약이 있는 convex optimization 문제를 생각하자:

원문제(primal):

minimize f₀(x)
subject to fᵢ(x) ≤ 0, i = 1, …, m
hⱼ(x) = 0, j = 1, …, p

라그랑지안은 다음과 같이 정의된다:

$$ L(x, λ, ν) = f₀(x) + ∑ᵢ λᵢ fᵢ(x) + ∑ⱼ νⱼ hⱼ(x) $$

여기서 λᵢ ≥ 0 는 불평등 제약에 대한 라그랑지 승수, νⱼ는 등식 제약에 대한 승수이다.

2. 라그랑지안 대함수 (Lagrange Dual Function)

$$ g(λ, ν) = \infₓ L(x, λ, ν) $$

이 함수는 각 (λ, ν)에 대해 **원문제의 목적함수의 하계(lower bound)**를 제공한다.

즉, 모든 (λ ≥ 0, ν)에 대해 g(λ, ν) ≤ f₀(x*) (x*는 primal optimal point).

3. 듀얼 문제의 정의

이 하계를 가능한 한 tight하게 만들기 위해, 듀얼 문제는 다음과 같이 정의된다:

듀얼 문제 (dual):

maximize g(λ, ν)
subject to λ ≥ 0