Linearism › 최적화 › OP.1

1장. 볼록집합과 볼록함수

최적화 · 1부. 볼록성과 최적성

기본 · 약 15분 · 연습문제 5

요약

최적화 문제의 꼴, 볼록집합, 볼록함수의 정의와 판정(1계·2계 조건), 볼록성을 지키는 연산, 국소 최솟값 = 전역 최솟값

산에서 가장 낮은 곳을 찾는다고 해 봅시다. 골짜기가 하나뿐인 그릇 모양이라면 계속 내려가기만 하면 바닥에 닿습니다. 골짜기가 여러 개라면 내려간 곳이 진짜 바닥인지 알 수 없습니다. “그릇 모양”을 수학으로 쓴 것이 볼록성이고, 볼록한 문제는 국소 최솟값이 곧 전역 최솟값이라 안심하고 풀 수 있습니다. 최소제곱, 로지스틱 회귀, SVM이 볼록 문제이고, 신경망 학습은 볼록이 아니라서 어렵습니다. 그 차이를 이해하는 것이 이 장의 목표입니다.

1.1 최적화 문제

정의 1.1. 다음 꼴의 문제를 최적화 문제(optimization problem)라 합니다.

min⁡x∈Cf(x)\min_{\mathbf x \in C} f(\mathbf x)

ff를 목적함수(objective function), CC를 실행 가능 집합(feasible set)이라 하고, 최솟값을 주는 x∗\mathbf x^*를 최적해(optimal solution)라 합니다.

최댓값 문제는 −f-f의 최솟값 문제로 바꿀 수 있으므로 최솟값만 다룹니다.

  • f(x∗)≤f(x)f(\mathbf x^*) \le f(\mathbf x)가 CC의 모든 x\mathbf x에 대해 성립하면 전역 최솟값(global minimum).
  • x∗\mathbf x^* 근처의 x\mathbf x에 대해서만 성립하면 국소 최솟값(local minimum).

예제 1.2. f(x)=x4−2x2f(x) = x^4 - 2x^2은 x=±1x = \pm1에서 국소 최솟값 −1-1을 가지며, 둘 다 전역 최솟값입니다. x=0x = 0은 국소 최댓값입니다. f(x)=x3−3xf(x) = x^3 - 3x는 x=1x = 1에서 국소 최솟값을 갖지만 x→−∞x \to -\infty에서 끝없이 작아지므로 전역 최솟값이 없습니다.

1.2 볼록집합

정의 1.3. 집합 CC의 임의의 두 점 x,y\mathbf x, \mathbf y와 0≤θ≤10 \le \theta \le 1에 대해 θx+(1−θ)y∈C\theta\mathbf x + (1 - \theta)\mathbf y \in C이면 CC를 볼록집합(convex set)이라 합니다.

두 점을 잇는 선분이 집합 밖으로 나가지 않는다는 뜻입니다.

예제 1.4.

  • 볼록: 직선, 평면, 원판 {x2+y2≤1}\{x^2 + y^2 \le 1\}, 반공간 {a⊤x≤b}\{\mathbf a^\top\mathbf x \le b\}, 다면체(반공간 여러 개의 교집합).
  • 볼록 아님: 원 둘레 {x2+y2=1}\{x^2 + y^2 = 1\}, 도넛 모양, 초승달 모양.

정리 1.5. 볼록집합들의 교집합은 볼록집합입니다.

증명. 두 점이 모든 집합에 들어 있으면 그 선분도 각 집합에 들어 있으므로 교집합에도 들어 있습니다. □

그래서 “부등식 제약 여러 개를 동시에 만족하는 점의 집합”은 각 제약이 볼록이면 볼록입니다.

1.3 볼록함수

정의 1.6. 볼록집합에서 정의된 ff가 모든 x,y\mathbf x, \mathbf y와 0≤θ≤10 \le \theta \le 1에 대해

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)f(\theta\mathbf x + (1 - \theta)\mathbf y) \le \theta f(\mathbf x) + (1 - \theta)f(\mathbf y)

이면 ff를 볼록함수(convex function)라 합니다. 0<θ<10 < \theta < 1이고 x≠y\mathbf x \ne \mathbf y일 때 부등호가 엄격하면 순볼록(strictly convex)이라 합니다.

그래프 위의 두 점을 이은 현이 그래프보다 위에 있다는 뜻입니다. 고등학교에서 “아래로 볼록”이라 부르던 것과 같습니다. −f-f가 볼록이면 ff를 오목(concave)이라 합니다.

예제 1.7. x2x^2, exe^x, ∣x∣|x|, −ln⁡x-\ln x(x>0x > 0)는 볼록입니다. sin⁡x\sin x, x3x^3은 볼록이 아닙니다. 일차함수 a⊤x+b\mathbf a^\top\mathbf x + b는 볼록이면서 오목입니다(등호).

1.4 판정법

정의를 직접 확인하기는 어려우므로 미분으로 판정합니다.

정리 1.8 (1계 조건). 미분가능한 ff가 볼록일 필요충분조건은 모든 x,y\mathbf x, \mathbf y에 대해

f(y)≥f(x)+∇f(x)⊤(y−x).f(\mathbf y) \ge f(\mathbf x) + \nabla f(\mathbf x)^\top(\mathbf y - \mathbf x).

접평면이 언제나 그래프 아래에 있다는 뜻입니다. 이 식은 한 점의 그래디언트가 함수 전체에 대한 정보(하한)를 준다는 점에서 중요합니다.

정리 1.9 (2계 조건). 두 번 미분가능한 ff가 볼록일 필요충분조건은 모든 x\mathbf x에서 헤세 행렬 ∇2f(x)\nabla^2 f(\mathbf x)가 양의 준정부호(positive semidefinite, 모든 고윳값 ≥0\ge 0)인 것입니다. 일변수이면 f′′(x)≥0f''(x) \ge 0입니다.

예제 1.10. f(x,y)=x2+xy+y2f(x, y) = x^2 + xy + y^2의 헤세 행렬은 (2112)\begin{pmatrix}2 & 1\\1 & 2\end{pmatrix}이고 고윳값이 1,31, 3이므로 볼록입니다. g(x,y)=x2+3xy+y2g(x, y) = x^2 + 3xy + y^2은 (2332)\begin{pmatrix}2 & 3\\3 & 2\end{pmatrix}의 고윳값이 5,−15, -1이라 볼록이 아닙니다(안장 모양).

예제 1.11 (이차형식). f(x)=12x⊤Ax+b⊤xf(\mathbf x) = \frac12\mathbf x^\top A\mathbf x + \mathbf b^\top\mathbf x(AA 대칭)의 헤세 행렬은 AA입니다. 그러므로 AA가 양의 준정부호일 때만 볼록입니다. 최소제곱 ∥Xβ−y∥2\|X\boldsymbol\beta - \mathbf y\|^2은 A=2X⊤XA = 2X^\top X이고, X⊤XX^\top X는 항상 양의 준정부호라서 볼록입니다.

1.5 볼록성을 지키는 연산

복잡한 함수는 아래 규칙으로 조립해 판정합니다.

  1. 음이 아닌 가중합: f,gf, g가 볼록이고 a,b≥0a, b \ge 0이면 af+bgaf + bg도 볼록.
  2. 일차변환과의 합성: ff가 볼록이면 f(Ax+b)f(A\mathbf x + \mathbf b)도 볼록.
  3. 최댓값: f,gf, g가 볼록이면 max⁡(f,g)\max(f, g)도 볼록.

예제 1.12.

  • 릿지 회귀 ∥Xβ−y∥2+λ∥β∥2\|X\beta - y\|^2 + \lambda\|\beta\|^2: 볼록 두 개의 합.
  • ReLU max⁡(0,x)\max(0, x)와 힌지 손실 max⁡(0,1−y w⊤x)\max(0, 1 - y\,\mathbf w^\top\mathbf x): 일차함수들의 최댓값.
  • 로지스틱 손실 ln⁡(1+e−z)\ln(1 + e^{-z}): 두 번 미분하면 σ(z)(1−σ(z))>0\sigma(z)(1 - \sigma(z)) > 0이므로 볼록이고, z=y w⊤xz = y\,\mathbf w^\top\mathbf x는 일차식이라 규칙 2로 w\mathbf w에 대해 볼록.

반면 신경망은 볼록함수를 여러 번 합성하는데, 볼록함수끼리의 합성은 일반적으로 볼록이 아닙니다. 그래서 신경망의 손실은 볼록이 아닙니다.

1.6 볼록 최적화의 핵심 정리

정리 1.13. 볼록집합 위의 볼록함수에서는 모든 국소 최솟값이 전역 최솟값입니다. 순볼록이면 최적해가 많아야 하나입니다.

증명. x∗\mathbf x^*가 국소 최솟값인데 f(y)<f(x∗)f(\mathbf y) < f(\mathbf x^*)인 y\mathbf y가 있다고 합시다. 볼록성에서 선분 위의 점 z=θy+(1−θ)x∗\mathbf z = \theta\mathbf y + (1 - \theta)\mathbf x^*는 f(z)≤θf(y)+(1−θ)f(x∗)<f(x∗)f(\mathbf z) \le \theta f(\mathbf y) + (1 - \theta)f(\mathbf x^*) < f(\mathbf x^*)를 만족합니다. θ\theta를 아주 작게 하면 z\mathbf z가 x∗\mathbf x^*에 얼마든지 가까워지므로, 국소 최솟값이라는 가정에 모순입니다. □

1.7 이 장의 요약

  • 최적화 문제 = 목적함수 + 실행 가능 집합. 국소 최솟값과 전역 최솟값을 구별합니다.
  • 볼록집합: 선분이 안에 머뭄. 볼록함수: 현이 그래프 위.
  • 판정: 접평면이 아래(1계), 헤세 행렬이 양의 준정부호(2계).
  • 볼록 문제에서는 국소 최솟값 = 전역 최솟값.

쓰이는 곳. 논문에서 “convex”, “the loss is convex in w”, “non-convex optimization”이라는 말은 이 장의 정의를 가리킵니다. 선형회귀·로지스틱 회귀·SVM의 수렴 보장, 신경망 학습이 왜 이론적으로 어려운지에 대한 논의, 제어공학의 볼록 최적화(모델 예측 제어), 신호처리의 압축 센싱이 모두 볼록성 위에 있습니다.

문제

1.1 [개념]

다음 중 볼록함수가 아닌 것은?

  1. e2xe^{2x}
  2. ∣x−3∣|x - 3|
  3. x4x^4
  4. ln⁡x\ln x (x>0x > 0)
정답
4
풀이

(ln⁡x)′′=−1/x2<0(\ln x)'' = -1/x^2 < 0이므로 ln⁡x\ln x는 오목입니다. 나머지는 이계도함수가 ≥0\ge 0이거나(1, 3), 일차함수의 절댓값입니다(2).

1.2 [계산] · 확인 문제

f(x,y)=x2+kxy+4y2f(x, y) = x^2 + kxy + 4y^2이 볼록이 되는 kk의 최댓값은?

힌트 1

헤세 행렬 (2kk8)\begin{pmatrix}2 & k\\k & 8\end{pmatrix}이 양의 준정부호이려면 대각성분이 ≥0\ge 0이고 행렬식이 ≥0\ge 0이어야 합니다.

정답
4
풀이

행렬식 16−k2≥016 - k^2 \ge 0이므로 ∣k∣≤4|k| \le 4, 최댓값은 44입니다.

1.3 [계산] · 확인 문제

f(x,y)=3x2+2xy+3y2f(x, y) = 3x^2 + 2xy + 3y^2의 헤세 행렬의 고윳값을 작은 것부터 씁니다.

고윳값 값
작은 것 [?]
큰 것 [?]
정답
4
8
풀이

헤세 행렬 (6226)\begin{pmatrix}6 & 2\\2 & 6\end{pmatrix}의 고윳값은 6±26 \pm 2, 곧 4,84, 8입니다. 모두 양수이므로 순볼록입니다.

1.4 [계산] · 확인 문제

f(x)=x2f(x) = x^2에 대해, x=1x = 1에서의 접선을 이용한 1계 조건의 하한 f(x)+f′(x)(y−x)f(x) + f'(x)(y - x)를 y=4y = 4에서 계산합니다.

정답
7
풀이

1+2(4−1)=71 + 2(4 - 1) = 7이고, 실제 값 f(4)=16≥7f(4) = 16 \ge 7입니다.

1.5 [증명]

f,gf, g가 볼록이면 h=max⁡(f,g)h = \max(f, g)도 볼록임을 보입니다.

풀이

z=θx+(1−θ)y\mathbf z = \theta\mathbf x + (1 - \theta)\mathbf y라 하면 f(z)≤θf(x)+(1−θ)f(y)≤θh(x)+(1−θ)h(y)f(\mathbf z) \le \theta f(\mathbf x) + (1 - \theta)f(\mathbf y) \le \theta h(\mathbf x) + (1 - \theta)h(\mathbf y)이고, gg도 같습니다. 그러므로 둘의 최댓값 h(z)h(\mathbf z)도 같은 상한을 갖습니다.