ADMM algorithms in statistics and machine learning

2017, 28

6)

1229–1244

통계적 기계학습에서의 ADMM 알고리즘의 활용

ᄎ

ᅬ호식

¹

²

³

12경기대학교 응용통계학과 ·³경기대학교 경영정보학과

ᄌ ᅥ

ᆸᄉ ᅮ 2017ᄂ ᅧ ᆫ 10ᄋ ᅯ ᆯ 31ᄋ ᅵ ᆯ, ᄉ ᅮᄌ ᅥ ᆼ 2017ᄂ ᅧ ᆫ 11ᄋ ᅯ ᆯ 14ᄋ ᅵ ᆯ, ᄀ ᅦᄌ ᅢ ᄒ ᅪ ᆨᄌ ᅥ ᆼ 2017ᄂ ᅧ ᆫ 11ᄋ ᅯ ᆯ 21ᄋ ᅵ ᆯ

요 약

ᄎ

ᅬ ᄀ ᅳ ᆫ ᄋ ᅧᄅ ᅥ ᄇ ᅮ ᆫ ᄋ ᅣᄋ ᅦᄉ ᅥ ᄃ ᅦᄋ ᅵᄐ ᅥᄋ ᅦ ᄀ ᅳ ᆫ ᄀ ᅥᄒ ᅡ ᆫ ᄇ ᅮ ᆫᄉ ᅥ ᆨᄇ ᅡ ᆼᄇ ᅥ ᆸᄅ ᅩ ᆫ ᄋ ᅦ ᄃ ᅢᄒ ᅡ ᆫ ᄉ ᅮᄋ ᅭᄀ ᅡ ᄌ ᅳ ᆼ ᄃ ᅢ ᄃ ᅬ ᆷ ᄋ ᅦ ᄄ ᅡᄅ ᅡ ᄋ ᅵᄅ ᅳ ᆯ ᄎ ᅥᄅ ᅵᄒ ᅡ ᆯ ᄉ ᅮ ᄋ ᅵ ᆻ ᄂ

ᅳ ᆫ ᄎ ᅬᄌ ᅥ ᆨᄒ ᅪ ᄇ ᅡ ᆼᄇ ᅥ ᆸᄋ ᅵ ᄇ ᅡ ᆯᄌ ᅥ ᆫᄃ ᅬᄀ ᅩ ᄋ ᅵ ᆻᄃ ᅡ. ᄐ ᅳ ᆨ ᄒ ᅵ ᄐ ᅩ ᆼ ᄀ ᅨᄒ ᅡ ᆨᄀ ᅪ ᄀ ᅵᄀ ᅨᄒ ᅡ ᆨᄉ ᅳ ᆸ ᄇ ᅮ ᆫ ᄋ ᅣᄋ ᅴ ᄆ ᅮ ᆫ ᄌ ᅦᄃ ᅳ ᆯ ᄋ ᅦᄉ ᅥ ᄋ ᅭᄀ ᅮᄃ ᅬᄂ ᅳ ᆫ ᄃ ᅡᄋ ᅣ ᆼᄒ ᅡ ᆫ ᄌ ᅦᄋ ᅣ ᆨ ᄌ

ᅩᄀ ᅥ ᆫᄋ ᅳ ᆫ ᄇ ᅩ ᆯᄅ ᅩ ᆨ ᄎ ᅬᄌ ᅥ ᆨᄒ ᅪ (convex optimization) ᄇ ᅡ ᆼᄇ ᅥ ᆸᄋ ᅳᄅ ᅩ ᄒ ᅢᄀ ᅧ ᆯᄒ ᅡ ᆯ ᄉ ᅮ ᄋ ᅵ ᆻᄃ ᅡ. ᄇ ᅩ ᆫ ᄂ ᅩ ᆫᄆ ᅮ ᆫ ᄋ ᅦᄉ ᅥ ᄅ ᅵᄇ ᅲᄒ ᅡᄂ ᅳ ᆫ alter- nating direction method of multipliers (ADMM) ᄋ ᅡ ᆯᄀ ᅩᄅ ᅵᄌ ᅳ ᆷᄋ ᅳ ᆫ ᄉ ᅥ ᆫᄒ ᅧ ᆼ ᄌ ᅦᄋ ᅣ ᆨ ᄌ ᅩᄀ ᅥ ᆫᄋ ᅳ ᆯ ᄒ ᅭᄀ ᅪᄌ ᅥ ᆨᄋ ᅳᄅ ᅩ ᄎ ᅥᄅ ᅵ ᄒ ᅡ

ᆯ ᄉ ᅮ ᄋ ᅵ ᆻᄋ ᅳᄆ ᅧ, ᄒ ᅡ ᆸᄋ ᅴ ᄇ ᅡ ᆼᄉ ᅵ ᆨᄋ ᅳ ᆯ ᄐ ᅩ ᆼ ᄒ ᅢ ᄇ ᅧ ᆼᄅ ᅧ ᆯᄋ ᅧ ᆫᄉ ᅡ ᆫᄋ ᅳ ᆯ ᄉ ᅮᄒ ᅢ ᆼᄒ ᅡ ᆯ ᄉ ᅮ ᄋ ᅵ ᆻᄋ ᅥᄉ ᅥ ᄇ ᅥ ᆷᄋ ᅭ ᆼᄌ ᅥ ᆨᄋ ᅵ ᆫ ᄑ ᅭᄌ ᅮ ᆫ ᄎ ᅬᄌ ᅥ ᆨᄒ ᅪ ᄐ ᅮ ᆯ ᄅ ᅩ ᄌ ᅡᄅ ᅵᄆ ᅢᄀ ᅵ ᆷ ᄃ

ᅬᄀ ᅩ ᄋ ᅵ ᆻᄃ ᅡ. ADMMᄋ ᅳ ᆫ ᄋ ᅯ ᆫ ᄅ ᅢᄋ ᅴ ᄆ ᅮ ᆫ ᄌ ᅦᄇ ᅩᄃ ᅡ ᄎ ᅬᄌ ᅥ ᆨᄒ ᅪᄀ ᅡ ᄉ ᅱᄋ ᅮ ᆫ ᄇ ᅮᄇ ᅮ ᆫᄆ ᅮ ᆫ ᄌ ᅦᄅ ᅩ ᄇ ᅮ ᆫ ᄒ ᅡ ᆯᄒ ᅡᄀ ᅩ ᄋ ᅵᄅ ᅳ ᆯ ᄎ ᅱᄒ ᅡ ᆸᄒ ᅡ ᆷᄋ ᅳᄅ ᅩᄊ ᅥ ᄇ ᅩ ᆨ ᄌ ᅡ ᆸ ᄒ ᅡ

ᆫ ᄋ ᅯ ᆫ ᄆ ᅮ ᆫ ᄌ ᅦᄅ ᅳ ᆯ ᄒ ᅢᄀ ᅧ ᆯᄒ ᅡᄂ ᅳ ᆫ ᄇ ᅡ ᆼᄉ ᅵ ᆨᄋ ᅴ ᄀ ᅳ ᆫ ᄉ ᅡᄋ ᅡ ᆯᄀ ᅩᄅ ᅵᄌ ᅳ ᆷ ᄋ ᅵᄃ ᅡ. ᄇ ᅮᄃ ᅳᄅ ᅥ ᆸᄌ ᅵ ᄋ ᅡ ᆭᄀ ᅥᄂ ᅡ ᄇ ᅩ ᆨ ᄒ ᅡ ᆸᄌ ᅥ ᆨᄋ ᅵ ᆫ (composite) ᄆ ᅩ ᆨᄌ ᅥ ᆨ ᄒ ᅡ ᆷᄉ ᅮ ᄅ

ᅳ ᆯ ᄎ ᅬᄌ ᅥ ᆨᄒ ᅪᄒ ᅡ ᆯ ᄄ ᅢ ᄋ ᅲᄋ ᅭ ᆼ ᄒ ᅡᄆ ᅧ, ᄊ ᅡ ᆼᄃ ᅢᄋ ᅵᄅ ᅩ ᆫ ᄀ ᅪ proximal ᄌ ᅡ ᆨᄋ ᅭ ᆼ ᄉ ᅩ ᄋ ᅵᄅ ᅩ ᆫᄋ ᅳ ᆯ ᄐ ᅩᄃ ᅢᄅ ᅩ ᄎ ᅦᄀ ᅨᄌ ᅥ ᆨᄋ ᅳᄅ ᅩ ᄋ ᅡ ᆯᄀ ᅩᄅ ᅵᄌ ᅳ ᆷᄋ ᅳ ᆯ ᄀ ᅮᄉ ᅥ ᆼᄒ ᅡ ᆯ ᄉ

ᅮ ᄋ ᅵ ᆻᄀ ᅵ ᄄ ᅢᄆ ᅮ ᆫ ᄋ ᅦ ᄐ ᅩ ᆼ ᄀ ᅨ ᄆ ᅵ ᆾ ᄀ ᅵᄀ ᅨᄒ ᅡ ᆨᄉ ᅳ ᆸ ᄇ ᅮ ᆫ ᄋ ᅣᄋ ᅦᄉ ᅥ ᄑ ᅩ ᆨ ᄂ ᅥ ᆲᄀ ᅦ ᄒ ᅪ ᆯᄋ ᅭ ᆼ ᄃ ᅬᄀ ᅩ ᄋ ᅵ ᆻᄃ ᅡ. ᄇ ᅩ ᆫ ᄂ ᅩ ᆫᄆ ᅮ ᆫ ᄋ ᅦᄉ ᅥᄂ ᅳ ᆫ ᄎ ᅬ ᄀ ᅳ ᆫ ᄐ ᅩ ᆼ ᄀ ᅨᄋ ᅪ ᄀ ᅪ ᆫᄅ ᅧ ᆫ ᄃ ᅬ

ᆫ ᄋ ᅧᄅ ᅥ ᄇ ᅮ ᆫ ᄋ ᅣᄋ ᅦᄉ ᅥ ADMMᄋ ᅡ ᆯᄀ ᅩᄅ ᅵᄌ ᅳ ᆷ ᄋ ᅴ ᄒ ᅪ ᆯᄋ ᅭ ᆼ ᄃ ᅩᄅ ᅳ ᆯ ᄉ ᅡ ᆯᄑ ᅧᄇ ᅩᄀ ᅩᄌ ᅡ ᄒ ᅡᄆ ᅧ ᄌ ᅮᄋ ᅭᄒ ᅡ ᆫ ᄃ ᅮ ᄀ ᅡᄌ ᅵ ᄌ ᅮᄌ ᅦᄋ ᅦ ᄌ ᅮ ᆼᄌ ᅥ ᆷᄋ ᅳ ᆯ ᄃ ᅮᄀ ᅩ ᄌ

ᅡ ᄒ ᅡ ᆫᄃ ᅡ. (1) ᄆ ᅩ ᆨᄌ ᅥ ᆨᄉ ᅵ ᆨᄋ ᅴ ᄇ ᅮ ᆫ ᄒ ᅡ ᆯ ᄌ ᅥ ᆫᄅ ᅣ ᆨᄀ ᅪ ᄌ ᅳ ᆼ ᄀ ᅡ ᆼ ᄅ ᅡᄀ ᅳᄅ ᅡ ᆼᄌ ᅵᄋ ᅡ ᆫ ᄇ ᅡ ᆼᄇ ᅥ ᆸ ᄆ ᅵ ᆾ ᄊ ᅡ ᆼᄃ ᅢᄆ ᅮ ᆫ ᄌ ᅦᄋ ᅴ ᄉ ᅥ ᆯᄆ ᅧ ᆼᄀ ᅪ (2) proximal ᄌ ᅡ ᆨᄋ ᅭ ᆼ ᄉ

ᅩᄋ ᅴ ᄋ ᅧ ᆨᄒ ᅡ ᆯᄋ ᅵᄃ ᅡ. ᄋ ᅡ ᆯᄀ ᅩᄅ ᅵᄌ ᅳ ᆷ ᄋ ᅵ ᄌ ᅥ ᆨᄋ ᅭ ᆼᄃ ᅬ ᆫ ᄉ ᅡᄅ ᅨᄅ ᅩ, ᄇ ᅥ ᆯᄌ ᅥ ᆷᄒ ᅪ ᄒ ᅡ ᆷᄉ ᅮ ᄎ ᅮᄌ ᅥ ᆼ ᄃ ᅳ ᆼ ᄋ ᅴ ᄌ ᅩᄌ ᅥ ᆼᄒ ᅪ (regularization)ᄅ ᅳ ᆯ ᄒ ᅪ ᆯᄋ ᅭ ᆼ ᄒ ᅡ ᆫ ᄇ

ᅡ ᆼᄇ ᅥ ᆸᄅ ᅩ ᆫᄃ ᅳ ᆯᄋ ᅳ ᆯ ᄉ ᅩᄀ ᅢᄒ ᅡ ᆫᄃ ᅡ. ᄆ ᅩᄋ ᅴ ᄌ ᅡᄅ ᅭᄅ ᅳ ᆯ ᄒ ᅪ ᆯᄋ ᅭ ᆼ ᄒ ᅡᄋ ᅧ lasso ᄆ ᅮ ᆫ ᄌ ᅦᄋ ᅴ ᄎ ᅬᄌ ᅥ ᆨᄒ ᅪᄋ ᅦ ᄃ ᅢᄒ ᅡ ᆫ ᄉ ᅵ ᆯᄌ ᅳ ᆼᄀ ᅧ ᆯᄀ ᅪᄅ ᅳ ᆯ ᄌ ᅦᄉ ᅵᄒ ᅡ ᆫᄃ ᅡ.

ᄌ

ᅮ요용어: 벌점함수, 병렬컴퓨팅, 제약조건, 조정화, 최적화.

1. 서론 ᄎ

ᅬ근 여러 분야에서 데이터에 근거한 분석방법론에 대한 수요가 증대됨에 따라 이를 처리할 수 있 느

ᆫ최적화 방법이 발전되고 있다. 특히 통계학과 기계학습 분야의 문제들에서 요구되는 다양한 제약조 ᄀ

ᅥᆫ은 볼록 최적화 (convex optimization) 방법으로 해결할 수 있다. 지난 10년간 볼록 최적화 (con- vex optimization) 분야에서 각광받고 있는 ADMM (alternating direction method of multipliers;

Boyd 등, 2010)알고리즘은제약조건을비교적 쉽게 처리할 수 있다. ADMM방법을리뷰한 Boyd 등 (2010) 논문은 2017년 10월말 현재 약 6000여건의 피인용회수 (Google scholar 검색기준)를 보이고 이

ᆻ다. ADMM방법은 오랜 기간 다양하게 발전되어온 비슷한 아이디어들의 융합에근거하며, 크게 원 ᄉ

ᅵ (primal) 문제와 쌍대 (dual) 문제라 불리우는 두 단계의 교차 최적화와 그에 따른 해의 업데이트 ᄀ

ᅪ정으로 구성된다. 교차 갱신과정의 계산복잡도 (computational complexity)가 작을 때, 원문제 대 ᄇ

ᅵ 효율성이 크다고 알려져 있다. 많은 경우 ADMM 내부의 부분문제 (sub-problem)에 대한 최적화 느

ᆫ proximal알고리즘 (Parikh and Boyd, 2013)에 의해 수행된다. Proximal 알고리즘은최적화할 함

1

ᄀ ᅭᄉ ᅵ ᆫᄌ ᅥᄌ ᅡ: (16938) ᄀ ᅧ ᆼᄀ ᅵᄃ ᅩ ᄉ ᅮᄋ ᅯ ᆫ ᄉ ᅵ ᄋ ᅧ ᆼᄐ ᅩ ᆼ ᄀ ᅮ ᄀ ᅪ ᆼ ᄀ ᅭᄉ ᅡ ᆫᄅ ᅩ ᄀ ᅧ ᆼᄀ ᅵᄃ ᅢᄒ ᅡ ᆨᄀ ᅭ ᄋ ᅳ ᆼᄋ ᅭ ᆼᄐ ᅩ ᆼ ᄀ ᅨᄒ ᅡ ᆨᄀ ᅪ, ᄌ ᅩᄀ ᅭᄉ ᅮ.

E-mail: [email protected]

2

(16938) ᄀ ᅧ ᆼᄀ ᅵᄃ ᅩ ᄉ ᅮᄋ ᅯ ᆫ ᄉ ᅵ ᄋ ᅧ ᆼᄐ ᅩ ᆼ ᄀ ᅮ ᄀ ᅪ ᆼ ᄀ ᅭᄉ ᅡ ᆫᄅ ᅩ ᄀ ᅧ ᆼᄀ ᅵᄃ ᅢᄒ ᅡ ᆨᄀ ᅭ ᄋ ᅳ ᆼᄋ ᅭ ᆼᄐ ᅩ ᆼ ᄀ ᅨᄒ ᅡ ᆨᄀ ᅪ, ᄀ ᅭᄉ ᅮ.

3

(16938) ᄀ ᅧ ᆼᄀ ᅵᄃ ᅩ ᄉ ᅮᄋ ᅯ ᆫ ᄉ ᅵ ᄋ ᅧ ᆼᄐ ᅩ ᆼ ᄀ ᅮ ᄀ ᅪ ᆼ ᄀ ᅭᄉ ᅡ ᆫᄅ ᅩ ᄀ ᅧ ᆼᄀ ᅵᄃ ᅢᄒ ᅡ ᆨᄀ ᅭ ᄀ ᅧ ᆼᄋ ᅧ ᆼᄌ ᅥ ᆼᄇ ᅩᄒ ᅡ ᆨᄀ ᅪ, ᄇ ᅮᄀ ᅭᄉ ᅮ.

ᄉ

ᅮ를보다 부드러운함수로 만들어 줌으로써 국소근사해를찾아준다. 이 알고리즘은 proximal작용소 (operator)와 해의 방향이나 갱신속도를제어하는 gradient작용소로 구성된다.

ADMM 알고리즘을 살펴보기로 한다. p차원의 모수벡터 x ∈ R^p라 놓자. 통계학에서는 모수 (pa- rameter)라 부르나, 본고에서는참고문헌들에서 사용되는 용어들을감안하여 변수 (variable)로 혼용하 ᄋ

ᅧ 쓰기로 한다. 두 개의 함수 f(x)와 g(x)로 구성된 목적함수에 대한 다음의 최적화 문제를고려해보 ᄌ

ᅡ.

min

x f (x) + g(x). (1.1) ᄋ

ᅵ 문제와 동일한 문제는아래와 같이 구성할 수 있다.

minx,z f (x) + g(z) subject to x = z. (1.2) ᄋ

ᅯ

ᆫ 문제 (1.1)과 달리 문제 (1.2)에서는 새로운 모수벡터 z가 추가적으로 도입되었다. 여기서, z ∈ R^p를보조변수 (auxiliary variable)로 부르고, 원 변수 x의 복제변수로 원 목적식의 최적화 문제를 분 ᄒ

ᅡᆯ하게 하는역할을수행한다. 가장 단순한 형태의 분할은 원변수와 보조변수와의관계식이 항등관계인 x = z이다. 가장 널리 알려진 lasso 예제를 통해확인하여보자.

예제 1.1 [lasso 문제] 설명변수와 종속변수로 구성된자료쌍 {(xⁱ, yi)}ⁿi=1에 대해 다음의 lasso 목적식 으

ᆯ고려하자.

β∈Rmin^p 1 2

n

X

i=1

(yi− x^Tiβ)²+ λ

p

X

j=1

|βj|. (1.3)

ᄒ

ᅬ귀계수 β ∈ R^p에 대해 보조변수 γ ∈ R^p를도입하여 β = γ의관계식으로 설정하면 위와 동일한 문 ᄌ

ᅦ는

β∈Rmin^p,γ∈R^p

1 2

n

X

i=1

(yi− x^Tiβ)²+ λ

p

X

j=1

|γj| (1.4)

ᄀ

ᅡ된다. 원 목적식이 β-최적화 부분 (Pn

i=1(yi− x^Tiβ)²)과 γ-최적화 부분 (Pp

j=1|γj|)으로 분할됨을 ᄋ

ᅡ

ᆯ 수 있다. 반면, 최적화할 모수의 수는 β와 γ로 2배로 증가한다. 식 (1.3)은 β에 대한 이차계획법 (quadratic program) 문제이다. 반면 식 (1.4)는 β = γ의 제약식을제외하면 β와 γ의 최적화는개별 ᄅ

ᅩ 이루어질 수 있다. 그러므로 선형제약식 β − γ = 0을만족하게 하면서 교차로 β와 γ를최적화하는 ᄋ

ᅡ이디어를생각할 수 있겠다. 사실 이러한 분할 방법은 1950년대의 Douglas-Rachford splitting으로 ᄑ

ᅧᆫ미분방정식의 수치해를구하기 위한 방안으로 개발되었다. Bregmann iteration 등으로도 불리는데, ᄇ

ᅵ슷한 유형으로 통계학 및 기계학습분야 뿐만 아니라 이미지 프로세싱, compressive sensing, matrix completion,금융 등의 분야에서 발전되어왔다.

ADMM의 특징을간략히 정리하면 다음과 같다. 첫째, 분할될수 있는선형 제약조건을가진 볼록 문 ᄌ

ᅦ는보조변수를도입하여 모수의 분리함으로써 쉽게 처리될수 있다. 둘째, ADMM을 통해큰 문제를 ᄌ

ᅡ

ᆨ은 문제로 분할시킬 수 있다. 관측치가 많은데이터의 경우 데이터를 분할된 블록으로 분해하고 각 블 ᄅ

ᅩ

ᆨ에 대해 최적화를수행할 수 있다. 이 경우 각 데이터 블록에 대한 최적화를 통한 해가 전체 자료에 대 ᄒ

ᅡᆫ 해로 수렴할 수 있도록,서로 일치하게 하는제약 조건이 포함되어야 한다. 동일한 방법으로 각 변수 ᄅ

ᅳᆯ여러 블록으로 분할할 수 있고, 부분문제를취합하여 전체 문제에 대한 최적해를산출하는방법이라 ᄒ

ᅡᆯ 수 있다 (Hastie 등, 2016).

ᄒ

ᅡᆫ편 가장 일반적인 형태의 등호 선형 제약식은 Ax+Bz = c이다. 여기서 A와 B는적절한 행렬이고 c는상수벡터이다. 예를 들어, 모수들이 나무 (tree) 형태의 위계적으로 구조화된제약이 되어 있다하더 ᄅ

ᅡ도 ADMM 알고리즘을 적용할 수 있다 (Yan과 Bien, 2015). 최근에는 딥러닝 (deep learning) 분 ᄋ

ᅣ에 이르기까지 광범위하게 활용되고 있다. Wen 등 (2016)은 CNN (convolutional neural network) ᄇ

ᅡᆼ법에 대해 구조적 성긴 조정학습법 (structured sparsity learning)을활용하여 필터, 채널, 레이어의 ᄎ

ᅳ

ᆼ 등구조를 조정 (regularize)하기 위한 최적화 방법으로 ADMM을활용하였다. 이 외에도 Yang 등 (2017)과 Taylor 등 (2016) 등은 범용적인 딥러닝 방법의 분산처리를위해 ADMM을활용하였다. 제 ᄋ

ᅣ

ᆨ식의 구체적 적용사례는후술할 2.5절의 fused lasso를비롯한 여러 예제들에서 구체적으로 다루기로 ᄒ

ᅡᆫ다.

ADMM의 참고문헌으로는 Boyd 등 (2010), proximal알고리즘의 리뷰는 Parikh과 Boyd (2013)를 ᄎ

ᅡ

ᆷ고하기 바란다. 본 논문은주로 Boyd 등 (2010)과 Polson 등 (2015)의 리뷰를기초로 함을미리 밝히 ᄆ

ᅧ 구성은다음과 같다. 2절에서는 ADMM 알고리즘과 이에 필요한 기본적 내용 등을기술한다. 3절에 ᄉ

ᅥ는 ADMM의 응용사례을살펴보고, 간단한 모의 자료를활용하여 lasso 문제의 최적화에 대한 실증결 ᄀ

ᅪ를제시한다. 끝으로 4절에서는결론 및 GPU 병렬 처리를위한 향후 계획을기술한다.

2. ADMM 방법론 ᄋ

ᅵ 절에서는 제약조건을 가진 최적화 문제를 비제약 (unconstrained) 형식의 벌점화 (penaliza- tion)된 문제로 전환하여 이해하고, 이와 관련된쌍대문제 (dual problem)를 최적화하기 위한 방법을 서

ᆯ명한다.

2.1. 쌍대문제와 증강 라그랑지안 방법 무

ᆫ제 (1.2)에 대한 라그랑지안 함수 (Lagrangian function)를생각해 보자.

L(x, z, α) = f (x) + g(z) + α^T(x − z), ᄋ

ᅧ기서 α는 라그랑지안 승수 (Lagrangian multipliers)이다. 먼저 문제 (1.2)를 원시 (primal) 문제라 ᄒ

ᅡ고, 모수 x, z를 원시모수 (primal parameter)라 한다. α가 주어졌을 때, x, z에 대한 최소값을가지 느

ᆫ함수를쌍대함수 (dual function)라 부르고, 다음으로 정의한다.

d(α) = inf

x,zL(x, z, α).

ᄌ

ᅦ약조건 x − z = 0하에서 원시문제에서의 최적값을 p^∗ = infx,z{f (x) + g(z)}으로 놓으면 d(α)와 p^∗와의관계는다음과 같음을 증명할 수 있다 (Boyd와 Vandenberghe, 2004).

d(α) = inf

x,zL(x, z, α) ≤ p^∗= inf

x,z{f (x) + g(z)}.

ᄀ

ᅳ러므로 d(α)는 p^∗에 대한 하한 (lower bound)이된다. 따라서 이 하한의 최대값을구하면 p^∗와 최 ᄃ

ᅢ한근접하게될 것이라 예상할 수 있다. 이상의 설명을다음의 문제로 정식화할 수 있게된다.

maxα d(α).

ᄋ

ᅵ를 원시문제에 대한 쌍대문제라 부른다. 쌍대문제의 최적값을 d^∗= sup_αd(α)라 두면 위관계식에 ᄋ

ᅴ해 약쌍대성 (weak duality)

d^∗≤ p^∗