이 내용은 책 Mathematics for machine learning(Marc Peter Deisenroth et al.)을 기반으로 하고 있습니다.
7.1장에서 보았던 최적화 문제는 단순히 함수의 최솟값을 찾는 문제였다. 이번 장에서는 제약(constraints)이 추가된 문제를 볼 것이다.
최소화하려는 함수 $f: \mathbb{R}^D \rightarrow \mathbb{R}$ 과 문제 $\min_x f(\boldsymbol{x})$은 동일하다. 거기에 $i = 1, \cdots, m$ 에 대한 실숫값 함수 $g_i: \mathbb{R}^D \rightarrow \mathbb{R}$을 제한으로 걸게 된다.
\[\begin{aligned} \min_x \quad &f(\boldsymbol{x}) \\ \mathrm{subject \ to} \quad &g_i(\boldsymbol{x}) \le 0 \quad \mathrm{for \ all} \quad i = 1, \cdots, m \end{aligned} \tag{1}\]여기서 $f, g_i$는 non-convex라 하겠다. 두 함수가 convex인 경우는 다음 장에서 본다.
위와 같은 ‘제한된 최적화 문제’를 ‘제한 없는(Unconstrained)’ 문제로 풀기 위한 방법 중 하나는 지시 함수(Indicator function)을 사용하는 것이다.
무한한 계단 함수(step func.) $\boldsymbol{1}(z)$ 를 아래와 같이 정의할 때
\[\boldsymbol{1}(z) = \begin{cases} 0 & (z \le 0) \\ \infty & (z > 0) \end{cases}\]지시 함수는
\[J(\boldsymbol{x}) = f(\boldsymbol{x}) + \sum \limits_{i=1}^m \boldsymbol{1}(g_i(\boldsymbol{x}))\]로 한다. 게단 함수를 위와 같이 정의해 지시함수에 포함함으로써, 제약(constraint)가 충족되지 않았을 땐 무한($\infty$)의 패널티를 부과하는 원리다.
물론 위와 같은 방법으로 동일한 해를 찾을 수는 있겠지만, 무한 계단 함수는 constraint problem과 마찬가지로 최적화가 어렵다. 그래서 도입한 것이 라그랑주 승수(Larange multipliers)이다.
라그랑주 승수의 주된 아이디어는 ‘계단 함수를 선형함수로 대체한다’이다.
Constrained Optimization Problem인 식 (1)을 라그랑주와 결함할 때, 라그랑즈 승수 $\lambda_i \ge 0$ 을 도입한다. 이 라그랑주 승수는 각각의 제한 부등식(inequality constraint) $g_i(\boldsymbol{x}) \le 0$와 대응한다. 따라서
\[\mathfrak{L}(\boldsymbol{x, \lambda}) = f(\boldsymbol{x}) + \sum \limits_{i=1}^m \lambda_i g_i(\boldsymbol{x}) = f(\boldsymbol{x}) + \boldsymbol{\lambda}^T \boldsymbol{g}(\boldsymbol{x})\]이다. 특히 마지막 식에선 모든 제약조건 $g_i(\boldsymbol{x})$를 하나의 벡터 $\boldsymbol{g}$로, 모든 라즈랑주 승수를 하나의 벡터 $\boldsymbol{\lambda}$ 로 나타냈다.
최적화에서 상대성(duality)이란, 한 변수의 집합 $\boldsymbol{x}$ 의 최적화 문제를 다른 변수의 집합 $\boldsymbol{\lambda}$ 의 최적화 문제로 전환하는 것을 말한다. 여기서 변환 이전 변수를 Primal variables, 이후 변수를 Dual variables라고 한다.
상대성을 다루는 두 가지 방법을 알아볼 것이며, 그 중 첫번째인 Lagrangian Duality는 지금, 다른 하나인 Legendre-Fenchel(르장드르-펜첼) duality는 다음 장에서 볼 예정이다.
primal variables $x$ 에 대응하는 primal problem은 아래와 같이 정의한다. $$ \begin{aligned} \min_x \quad &f(\boldsymbol{x}) \\ \mathrm{subject \ to} \quad &g_i(\boldsymbol{x}) \le 0 \quad \mathrm{for \ all} \quad i = 1, \cdots, m \end{aligned} $$
Dual variables $\boldsymbol{\lambda}$ 에 대해 Lagrangian Dual Problem은 아래와 같이 정의한다. $$ \begin{aligned} \max_{\boldsymbol{\lambda} \in \mathbb{R}^m} \quad &\mathfrak{D}(\boldsymbol{\lambda}) \\ (&\mathfrak{D}(\boldsymbol{\lambda}) = \min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x, \lambda})) \\ \mathrm{subject \ to} \quad &\boldsymbol{\lambda} \ge \boldsymbol{0} \end{aligned} $$
$\mathfrak{D}(\boldsymbol{\lambda})$ 은 dual object function이다. Primal Problem을 이해하기 위해 두 가지 개념을 짚고 넘어간다.
두 인자를 가진 임의의 함수 $\varphi(\boldsymbol{x}, \boldsymbol{y})$ 에 대해, maximin은 minimax 보다 작다. 이를 식으로 나타내면 아래와 같다.
\[\max_{\boldsymbol{y}} \min_{\boldsymbol{x}} \varphi(\boldsymbol{x, y}) \le \min_{\boldsymbol{x}} \max_{\boldsymbol{y}} \varphi(\boldsymbol{x, y}) \tag{2}\]식 (2)는 아래와 같은 부등식 (3)을 이용해 증명할 수 있다.
\[\mathrm{For \ all \ \boldsymbol{x, y}} \quad \min_{\boldsymbol{x}} \varphi(\boldsymbol{x, y}) \le \max_{\boldsymbol{y}} \varphi(\boldsymbol{x, y}) \tag{3}\]식 (3)은 식 (2)의 양변 안쪽 항에 해당한다. 따라서 식 (2)의 좌변은 직관적으로 보자면 ‘최소 중에서 최대로’, 우변은 ‘최대 중에서 최소로’의 뜻이 된다.
앞서 본 Minimax imequality 식(2)를 활용해, ‘primal values나 항상 dual values 보다 크거나 같음’을 말한다.
앞서 ‘제한된 최적화 문제’를 ‘제한 없는(Unconstrained)’ 문제로 풀기 위한 방법으로 지시함수 $J(\boldsymbol{x})$ 를 사용하는 방법을 논한 바 있었다. 또한 라그랑주를 활용한 방법도 보았다. 두 방법의 차이는 지시 함수를 선형 함수로 바꾸는 것이었다. 그러므로, $\lambda \ge 0$ 일 때 라그랑주 $\mathfrak{L}(\boldsymbol{x, \lambda})$ 는 $J(\boldsymbol{x})$ 의 하한(lower bound, 하계(아래로 유계)) 다. 이를 바꾸어 말하면 $\boldsymbol{\lambda}$에 대한 $\mathfrak{L}(\boldsymbol{x, \lambda})$ 의 최댓값을 아래와 같이 표현할 수 있다.
\[J(\boldsymbol{x}) = \max_{\boldsymbol{\lambda} \ge 0}\mathfrak{L}(\boldsymbol{x, \lambda})\]애초 최적화 문제는 $J(\boldsymbol{x})$ 를 최소화하는 것이었으므로
\[\min_{\boldsymbol{x} \in \mathbb{R}^d} \max_{\boldsymbol{\lambda} \ge 0}\mathfrak{L}(\boldsymbol{x, \lambda})\]로 나타낼 수 있고, minimax inequality(식 (2))를 적용하면
\[\min_{\boldsymbol{x} \in \mathbb{R}^d} \max_{\boldsymbol{\lambda} \ge 0} \mathfrak{L}(\boldsymbol{x, \lambda}) \ge \max_{\boldsymbol{\lambda} \ge 0} \min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x, \lambda}) \tag{4}\]이다. 이것이 weak duality이다. 참고로 우변의 $\mathfrak{L}(\boldsymbol{x, \lambda})$ 은 앞서 정의했듯 dual object function $\mathfrak{D}(\boldsymbol{\lambda})$ 이다.
우변의 안쪽 항을 살펴보자. 제약조건(constraints)가 있었던 본래 최적화 문제와는 다르게, $\min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x, \lambda})$ 은 주어진 값 $\boldsymbol{\lambda}$ 에 대한 제약이 없는 최적화 문제가 된다. 이 $\min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x, \lambda})$ 문제의 풀이가 쉽다면, 전체적 문제 역시 풀기 쉬워진다.
정말 그럴지, Lagrangian Dual Problem을 다시 상기해보자.
\[\begin{aligned} \max_{\boldsymbol{\lambda} \in \mathbb{R}^m} \quad &\mathfrak{D}(\boldsymbol{\lambda}) \qquad (\mathfrak{D}(\boldsymbol{\lambda}) = \min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x, \lambda})) \\ \mathrm{subject \ to} \quad &\boldsymbol{\lambda} \ge \boldsymbol{0} \end{aligned}\]위 최적화 문제에서 $\mathfrak{L}(\boldsymbol{x, \lambda})$ 는 $\boldsymbol{\lambda}$ 에 대한 어파인(affine) 이었다. 따라서 $\min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x, \lambda})$ 는 점 별로(pointwise) $\boldsymbol{\lambda}$ 에 대한 어파인 함수의 최솟값인 셈이다. 또한 $\mathfrak{D}(\boldsymbol{\lambda})$ 은 $f, g_i$가 convex하지 않더라도 concave(위로 오목한)하다.
Affine Function(어파인 함수)는 $f(x_1, \cdots, x_n) = A_1 x_1 + \cdots + A_n x_n + b$ 형태로 이루어진 함수를 말한다.
Convex는 아래로 볼록, Concave는 위로 볼록한 형태를 가진다. 
Weak Duality (식 (4)) 우변의 바깥 문제( $\lambda$ 에 대한 maximum, 즉 $\max_{\boldsymbol{\lambda} \ge 0} \min_{\boldsymbol{x} \in \mathbb{R}^d} \mathfrak{L}(\boldsymbol{x, \lambda})$ ) 시야를 넓여보자. 그 말인 즉슨, 위로 오목한 형태의 concave 함수의 최댓값을 찾겠단 소린데, 극대점은 하나로 분명하다. 따라서 찾기도 쉽고 연산도 효율적이다. 즉, 최적화 문제 풀이가 보다 쉬워진다.
만약 함수 $f(\cdot)$ 과 $g_i(\cdot)$ 이 미분 가능한 함수라면, Lagrange dual problem을 쉽게 찾을 수 있다. x에 대한 Lagrangian을 미분하고, 미분(differential)을 0으로 둔 뒤 최적값(optimal value)를 찾으면 된다. 두 함수가 convex일 때의 구체적 예시는 차차 다룰 예정이다.
이번장 초반에 다루었던 제약 조건이 있는 최적화 문제는 아래와 같았다.
\[\begin{aligned} \min_x \quad &f(\boldsymbol{x}) \\ \mathrm{subject \ to} \quad &g_i(\boldsymbol{x}) \le 0 \quad \mathrm{for \ all} \quad i = 1, \cdots, m \end{aligned} \tag{1}\]Inequality constraints $g_i(\boldsymbol{x})$ 을 포함하고 있는 식 (1)에, equality constraints $h_j(\boldsymbol{x})$를 추가해 아래와 같이 문제를 나타내자.
\[\begin{aligned} \min_x \quad &f(\boldsymbol{x}) \\ \mathrm{subject \ to} \quad &g_i(\boldsymbol{x}) \le 0 \quad \mathrm{for \ all} \quad i = 1, \cdots, m \\ &h_j(\boldsymbol{x}) = 0 \quad \mathrm{for \ all} \quad j = 1, \cdots, n \end{aligned} \tag{5}\]Equality constraints 을 두 개의 Inequality constraints 로 바꿔 모델링할 수 있다. 다시 말해, 각 equality constraints $h_j(\boldsymbol{x}) = 0$ 에 대해 두 개의 constraint $h_j(\boldsymbol{x}) \le 0$ , $h_j(\boldsymbol{x}) \ge 0$ 로 바꾸는 것이다. 그럼 결과적으로 라그랑주 승수가 unconstrained가 된다.
따라서, 식(5)의 Inequality constraints에 대응하는 라그랑주 승수를 음이 아니도록(non-negative) 제한했고(constrain), Equality constraints에 대응하는 라그랑주 승수는 제약이 없도록 했다(unconstrained).
