볼록 최적화(Convex Optimization)

볼록(convex) 문제에는 골짜기가 하나뿐입니다. 신경망(neural network)에는 수백만 개가 있습니다. 이 차이를 아는 것은 중요합니다.

유형: Build 언어: Python 선수 지식: Phase 1, Lesson 04(Calculus for ML), 08(Optimization) 예상 시간: 약 90분

학습 목표

• 정의(definition), 이계도함수(second derivative), 헤시안(Hessian) 기준으로 함수가 볼록(convex)인지 검사합니다.
• 뉴턴 방법(Newton's method)을 구현하고 경사 하강법(gradient descent)과 이차 수렴(quadratic convergence)을 비교합니다.
• 라그랑주 승수(Lagrange multiplier)로 제약 최적화(constrained optimization) 문제를 풀고 KKT 조건(KKT conditions)을 해석합니다.
• 신경망의 손실 지형(loss landscape)이 비볼록(non-convex)인데도 SGD가 좋은 해(solution)를 찾는 이유를 설명합니다.

문제

Lesson 08에서는 경사 하강법(gradient descent), 모멘텀(momentum), 그리고 Adam을 배웠습니다. 이 최적화 기법(optimizer)들은 어떤 곡면(surface) 위에서도 내리막(downhill) 방향으로 움직입니다. 하지만 보장은 없습니다. 비볼록(non-convex) 지형에서 경사 하강법은 나쁜 국소 최솟값(local minimum)에 빠질 수 있고, 안장점(saddle point)에서 멈춰버릴 수도 있으며, 영원히 진동(oscillate)할 수도 있습니다. 그럼에도 신경망이 비볼록이고 대안이 없기 때문에 사용해 왔습니다.

하지만 머신러닝(machine learning)의 많은 문제는 볼록(convex)합니다. 선형 회귀(linear regression), 로지스틱 회귀(logistic regression), 서포트 벡터 머신(SVM), LASSO, 리지 회귀(ridge regression)가 그렇습니다. 이런 문제에는 더 강한 도구가 있습니다. 바로 수학적 보장(mathematical guarantee)을 갖춘 최적화입니다. 볼록 문제에는 골짜기(valley)가 정확히 하나뿐입니다. 내리막으로 걸어가는 알고리즘은 전역 최솟값(global minimum)에 도달합니다. 재시작(restart)도, 학습률 스케줄(learning rate schedule)도, 기도도 필요 없습니다.

볼록성(convexity)을 이해하면 세 가지를 얻습니다. 첫째, 문제가 쉬운지(볼록) 어려운지(비볼록) 알 수 있습니다. 둘째, 볼록 문제에 뉴턴 방법(Newton's method) 같은 더 빠른 도구를 쓸 수 있습니다. 셋째, ML 전반의 개념, 즉 제약(constraint)으로서의 정규화(regularization), SVM의 쌍대성(duality), 그리고 볼록성의 좋은 성질을 모두 어기는데도 딥러닝(deep learning)이 작동하는 이유를 설명할 수 있습니다.

개념

볼록 집합(Convex Set)

집합(set) S 안에서 임의의 두 점(point)을 골랐을 때, 그 사이 선분(line segment) 전체가 S 안에 있으면 S는 볼록입니다.

엄밀한 검사(formal test): S 안의 임의의 x, y와 t in [0, 1]에 대해 tx + (1-t)y도 S 안에 있으면 됩니다.

볼록 집합 예시:

• 직선(line), 평면(plane), 전체 공간 R^n
• 공(ball, 즉 원·구·초구)
• 반공간(halfspace): {x : a^T x <= b}
• 임의 개수의 볼록 집합의 교집합(intersection)

비볼록 집합 예시:

• 도넛(원환, annulus)
• 서로 떨어진 두 원의 합집합(union)
• 움푹 패임(dent)이나 구멍(hole)이 있는 집합

볼록 함수(Convex Function)

함수 f의 정의역(domain)이 볼록 집합이고, 정의역 안의 임의의 x, y와 t in [0, 1]에 대해 다음을 만족하면 f는 볼록 함수입니다.

f(tx + (1-t)y) <= t*f(x) + (1-t)*f(y)

기하학적으로 보면, 그래프 위의 임의의 두 점을 잇는 선분이 그래프 위 또는 그 위쪽에 있다는 뜻입니다.

자주 보는 볼록 함수:

• f(x) = x^2 (포물선, parabola)
• f(x) = |x| (절댓값, absolute value)
• f(x) = e^x (지수 함수, exponential)
• f(x) = max(0, x) (ReLU, 조각별 선형 함수)
• f(x) = -log(x) for x > 0 (음의 로그, negative log)
• 선형 함수 f(x) = a^T x + b는 볼록인 동시에 오목(concave)합니다.

볼록성 검사(Convexity Test)

실용적인 검사 방법은 세 가지가 있습니다. 쉬운 것부터 더 엄밀한 것 순서로 살펴봅니다.

검사 1: 이계도함수 검사(second derivative test, 1차원). 모든 x에서 f''(x) >= 0이면 f는 볼록합니다.

• f(x) = x^2: f''(x) = 2 >= 0이므로 볼록입니다.
• f(x) = x^3: f''(x) = 6x로, x < 0에서는 음수가 되므로 볼록이 아닙니다.
• f(x) = e^x: f''(x) = e^x > 0이므로 볼록입니다.

검사 2: 헤시안 검사(Hessian test, 다변수). 헤시안 행렬 H(x)가 모든 x에서 양의 준정부호(positive semidefinite)이면 f는 볼록합니다. 헤시안은 이계 편도함수(second partial derivative)의 행렬입니다.

검사 3: 정의 검사(definition test). 부등식 f(tx + (1-t)y) <= t*f(x) + (1-t)*f(y)를 직접 확인합니다. 도함수를 계산하기 어려운 함수에 유용합니다.

왜 볼록성(Convexity)이 중요한가

볼록 최적화의 핵심 정리는 다음과 같습니다.

볼록 함수에서는 모든 국소 최솟값이 전역 최솟값입니다.

이는 경사 하강법이 갇히지 않는다는 뜻입니다. 어떤 내리막 경로(downhill path)를 택해도 결국 같은 답에 도달합니다. 알고리즘이 최적해(optimal solution)로 수렴(converge)하는 것이 보장됩니다.

graph LR
    subgraph "Convex: ONE answer"
        direction TB
        C1["Loss surface has a single valley"] --> C2["Gradient descent ALWAYS finds the global minimum"]
    end
    subgraph "Non-convex: MANY traps"
        direction TB
        N1["Loss surface has multiple valleys and peaks"] --> N2["Gradient descent may get stuck in a local minimum"]
        N2 --> N3["Global minimum might be missed"]
    end

결과:

• 무작위 재시작(random restart)이 필요 없습니다.
• 정교한 학습률 스케줄(sophisticated learning rate schedule)이 필요 없습니다.
• 수렴 증명(convergence proof)이 가능합니다. 수렴 속도(rate)는 함수의 성질에 따라 달라집니다.
• 해는 유일(unique)합니다. 평평한 영역(flat region)이 있으면 유일하지 않을 수도 있습니다.

ML에서 볼록(Convex) vs 비볼록(Non-convex)

볼록 손실을 갖는 선형 모형은 볼록합니다. 은닉층(hidden layer)과 비선형 활성화를 추가하는 순간 볼록성은 깨집니다.

헤시안 행렬(Hessian Matrix)

함수 f: R^n -> R의 헤시안(Hessian) H는 이계 편도함수로 이루어진 n x n 행렬입니다.

H[i][j] = d^2 f / (dx_i dx_j)

f(x, y) = x^2 + 3xy + y^2이면 다음과 같습니다.

df/dx = 2x + 3y       d^2f/dx^2 = 2      d^2f/dxdy = 3
df/dy = 3x + 2y       d^2f/dydx = 3      d^2f/dy^2 = 2

H = [ 2  3 ]
    [ 3  2 ]

헤시안은 곡률(curvature)을 알려줍니다.

• 고윳값(eigenvalue)이 모두 양수: 모든 방향으로 위로 휘어집니다. 그 점에서 볼록합니다.
• 고윳값이 모두 음수: 모든 방향으로 아래로 휘어집니다. 오목이며 국소 최댓값(local max)입니다.
• 부호가 섞임: 안장점(saddle point)입니다. 어떤 방향으로는 위로, 어떤 방향으로는 아래로 휘어집니다.
• 고윳값 0: 그 방향으로 평평합니다. 퇴화(degenerate) 상황입니다.

볼록성을 보장하려면 한 점이 아니라 모든 점에서 헤시안이 양의 준정부호(positive semidefinite), 즉 모든 고윳값이 0 이상이어야 합니다.

뉴턴 방법(Newton's Method)

경사 하강법은 1차 정보(first-order information), 즉 기울기(gradient)만 사용합니다. 뉴턴 방법은 2차 정보(second-order information), 즉 헤시안까지 사용합니다. 현재 점에서 이차 근사(quadratic approximation)를 맞춘 뒤, 그 이차식의 최솟값으로 곧장 이동합니다.

갱신 규칙:
  x_new = x - H^(-1) * gradient

경사 하강법과 비교:
  x_new = x - lr * gradient

뉴턴 방법은 스칼라 학습률(learning rate)을 헤시안의 역행렬(inverse Hessian)로 대체합니다. 국소 곡률(local curvature)에 따라 보폭(step size)과 방향이 자동으로 조정됩니다.

graph TD
    subgraph "Gradient Descent"
        GD1["Start"] --> GD2["Step 1"]
        GD2 --> GD3["Step 2"]
        GD3 --> GD4["..."]
        GD4 --> GD5["Step ~500: Converged"]
        GD_note["Follows gradient blindly -- many small steps"]
    end
    subgraph "Newton's Method"
        NM1["Start"] --> NM2["Step 1"]
        NM2 --> NM3["..."]
        NM3 --> NM4["Step ~5: Converged"]
        NM_note["Uses curvature for optimal steps"]
    end

장점:

• 최솟값 근처에서 이차 수렴(quadratic convergence)을 보입니다. 오차가 매 단계마다 제곱으로 줄어듭니다.
• 학습률을 조정(tune)할 필요가 없습니다.
• 스케일 불변(scale-invariant)입니다. 문제를 어떤 방식으로 매개변수화(parameterize)해도 잘 작동합니다.

단점:

• 헤시안 계산에 O(n^2) 메모리가 필요하고 역행렬을 구하는 데 O(n^3)이 듭니다.
• 100만 개의 가중치를 가진 신경망이라면 10^12개의 원소(entry)와 10^18번의 연산이 필요합니다.
• 딥러닝에서는 실용적이지 않습니다.

제약 최적화(Constrained Optimization)

제약이 없는 최적화(unconstrained optimization)는 모든 x에 대해 f(x)를 최소화합니다. 제약 최적화(constrained optimization)는 제약 조건(constraint)을 만족하는 x 중에서 f(x)를 최소화합니다.

현실의 문제에는 제약이 있습니다. 비용을 최소화하고 싶지만 예산이 제한되어 있고, 오차를 최소화하고 싶지만 모형의 복잡도가 한정되어 있습니다.

graph LR
    subgraph "Unconstrained"
        U1["Loss function"] --> U2["Free minimum: lowest point of the loss surface"]
    end
    subgraph "Constrained"
        C1["Loss function"] --> C2["Constrained minimum: lowest point within the feasible region"]
        C3["Constraint boundary limits the search space"]
    end

라그랑주 승수(Lagrange Multiplier)

라그랑주 승수법(Lagrange multiplier method)은 제약 문제를 제약이 없는 문제로 바꿔 줍니다.

문제: g(x) = 0 조건 아래에서 f(x)를 최소화합니다.

해법: 새로운 변수, 즉 라그랑주 승수(Lagrange multiplier) lambda를 도입하여 다음 제약 없는 문제를 풉니다.

L(x, lambda) = f(x) + lambda * g(x)

해에서는 L의 기울기가 0이 됩니다.

dL/dx = df/dx + lambda * dg/dx = 0
dL/dlambda = g(x) = 0

기하학적 직관: 제약 조건이 있는 최솟값(constrained minimum)에서는 f의 기울기가 제약 조건 g의 기울기와 평행해야 합니다. 평행하지 않다면, 제약 곡면(constraint surface)을 따라 움직여 f를 더 줄일 수 있습니다.

graph LR
    A["Contours of f(x,y): concentric ellipses"] --- S["Solution point"]
    B["Constraint curve g(x,y) = 0"] --- S
    S --- C["At the solution, gradient of f is parallel to gradient of g"]

예시: x + y = 1 조건 아래에서 f(x,y) = x^2 + y^2를 최소화합니다.

L = x^2 + y^2 + lambda(x + y - 1)

dL/dx = 2x + lambda = 0  =>  x = -lambda/2
dL/dy = 2y + lambda = 0  =>  y = -lambda/2
dL/dlambda = x + y - 1 = 0

앞의 두 식에서 x = y
대입하면 2x = 1, 즉 x = y = 0.5, lambda = -1

원점에서 직선 x + y = 1에 가장 가까운 점은 (0.5, 0.5)입니다.

KKT 조건(KKT Conditions)

KKT 조건(Karush-Kuhn-Tucker conditions)은 라그랑주 승수법을 부등식 제약(inequality constraint)까지 확장합니다.

문제: g_i(x) <= 0 (i = 1, ..., m) 조건 아래에서 f(x)를 최소화합니다.

KKT 조건, 즉 최적성(optimality)을 위해 필요한 조건은 다음과 같습니다.

1. 정상성(Stationarity):    df/dx + sum(lambda_i * dg_i/dx) = 0
2. 원문제 실현 가능성(Primal feasibility):  g_i(x) <= 0  (모든 i에 대해)
3. 쌍대 실현 가능성(Dual feasibility):    lambda_i >= 0  (모든 i에 대해)
4. 상보성 여유조건(Complementary slackness):  lambda_i * g_i(x) = 0  (모든 i에 대해)

핵심 통찰은 상보성 여유조건(complementary slackness)입니다. 제약이 활성(active)이거나(g_i = 0, 해가 경계 위에 있음) 또는 승수가 0입니다. 해에 영향을 주지 않는 제약은 lambda = 0이 됩니다.

KKT 조건은 SVM에서 핵심적인 역할을 합니다. 서포트 벡터(support vector)는 제약이 활성인 데이터 점, 즉 lambda > 0인 점입니다. 다른 데이터 점은 lambda = 0이므로 결정 경계(decision boundary)에 영향을 주지 않습니다.

제약 최적화로서의 정규화(Regularization as Constrained Optimization)

L1과 L2 정규화(regularization)는 임의로 만든 요령이 아닙니다. 제약 최적화 문제를 다른 방식으로 표현한 것입니다.

L2 정규화(Ridge):

minimize  Loss(w)  subject to  ||w||^2 <= t

동등한 제약 없는 형식:
minimize  Loss(w) + lambda * ||w||^2

제약 조건 ||w||^2 <= t는 공(ball)을 정의합니다. 2차원에서는 원, 3차원에서는 구입니다. 해는 손실 등고선(loss contour)이 이 공에 처음 닿는 지점입니다.

L1 정규화(LASSO):

minimize  Loss(w)  subject to  ||w||_1 <= t

동등한 제약 없는 형식:
minimize  Loss(w) + lambda * ||w||_1

제약 조건 ||w||_1 <= t는 마름모(diamond)를 정의합니다. 2차원에서는 회전된 정사각형입니다.

이것이 L1은 희소(sparse) 모델, 즉 특징 선택을 만들고 L2는 가중치를 줄이기만 하는 이유입니다. 마름모는 축과 정렬된 모서리를 갖습니다. 손실 등고선이 모서리에 닿을 가능성이 높고, 그 결과 하나 이상의 가중치가 정확히 0이 됩니다.

쌍대성(Duality)

모든 제약 최적화 문제(원문제, primal)에는 짝이 되는 문제(쌍대 문제, dual)가 있습니다. 볼록 문제에서는 원문제와 쌍대 문제가 동일한 최적값을 가집니다. 이것을 강한 쌍대성(strong duality)이라고 부릅니다.

라그랑주 쌍대 함수(Lagrangian dual function):

원문제(Primal): minimize f(x) subject to g(x) <= 0
라그랑지언(Lagrangian): L(x, lambda) = f(x) + lambda * g(x)
쌍대 함수(Dual function): d(lambda) = min_x L(x, lambda)
쌍대 문제(Dual problem): maximize d(lambda) subject to lambda >= 0

쌍대성이 중요한 이유:

• 쌍대 문제가 원문제보다 풀기 쉬운 경우가 있습니다.
• SVM은 쌍대 형식(dual form)으로 풀며, 쌍대 문제는 데이터 점들 사이의 내적(dot product)에만 의존합니다. 이것이 커널 트릭(kernel trick)을 가능하게 합니다.
• 쌍대 문제는 원문제 최적값의 하한(lower bound)을 제공하므로 해의 품질을 확인하는 데 유용합니다.

SVM에서는 다음과 같습니다.

원문제: 모든 i에 대해 y_i(w^T x_i + b) >= 1 조건 아래에서,
       마진 2/||w||를 최대화하는 w, b를 찾습니다.

쌍대 문제: maximize sum(alpha_i) - 0.5 * sum_ij(alpha_i * alpha_j * y_i * y_j * x_i^T x_j)
          subject to alpha_i >= 0, sum(alpha_i * y_i) = 0

쌍대 문제는 오직 내적 x_i^T x_j만을 포함합니다.
x_i^T x_j를 K(x_i, x_j)로 바꾸면 커널 트릭이 됩니다.

비볼록성(Non-convexity)에도 딥러닝이 작동하는 이유

신경망의 손실 함수는 매우 비볼록합니다. 고전적인 잣대로 보면 최적화는 실패해야 마땅합니다. 그런데 확률적 경사 하강법(stochastic gradient descent, SGD)은 안정적으로 좋은 해를 찾아냅니다. 몇 가지 이유가 있습니다.

대부분의 국소 최솟값은 충분히 좋은 값입니다. 고차원 공간(high-dimensional space)에서 기울기가 0인 무작위 임계점(random critical point)은 국소 최솟값보다 안장점일 가능성이 압도적으로 큽니다. 존재하는 국소 최솟값도 대체로 전역 최솟값과 손실 값(loss value)이 비슷합니다. 매개변수 공간(parameter space)이 수백만 차원이면 끔찍한 국소 최솟값에 갇힐 확률은 매우 낮습니다.

진짜 장애물은 국소 최솟값이 아니라 안장점입니다. n개의 매개변수를 가진 함수에서 안장점은 양의 곡률 방향(positive curvature direction)과 음의 곡률 방향을 모두 가집니다. 고차원에서 무작위 임계점이 n개의 고윳값을 모두 양수로 가질 확률은 대략 2^(-n)입니다. 거의 모든 임계점이 안장점입니다. SGD의 잡음(noise)은 이러한 안장점에서 빠져나오는 데 도움을 줍니다.

과매개변수화(overparameterization)는 지형을 매끈하게 만듭니다. 학습 예제(training example)보다 매개변수가 더 많은 신경망은 보다 매끄럽고 연결된 손실 곡면을 갖습니다. 폭이 넓은 신경망(wide network)에는 나쁜 국소 최솟값이 적습니다. 직관과는 다르지만 경험적으로 일관되게 관찰되는 사실입니다.

손실 지형의 구조:

확률적 잡음은 암묵적인 정규화(implicit regularization)처럼 작동합니다. 미니배치(mini-batch) SGD는 날카로운(sharp) 최솟값에 정착하지 못하게 하는 잡음을 더합니다. 날카로운 최솟값은 과대적합(overfit)으로 이어지고, 평평한(flat) 최솟값은 일반화(generalize)를 잘합니다. 잡음은 최적화를 손실 지형의 평평한 영역 쪽으로 이끄는 편향(bias)을 줍니다.

실무의 2차 방법(Second-order Method)

순수한 뉴턴 방법은 대형 모형에 적용하기에 비현실적입니다. 몇 가지 근사(approximation)를 통해 2차 정보를 활용할 수 있습니다.

L-BFGS(Limited-memory BFGS): 최근 m개의 기울기 차이(gradient difference)를 사용해 역헤시안(inverse Hessian)을 근사합니다. O(n^2) 대신 O(mn) 메모리만 필요합니다. 매개변수가 약 1만 개까지인 문제에 잘 작동합니다. 고전적인 ML(로지스틱 회귀, 조건부 무작위장(CRF))에서는 흔하지만 딥러닝에서는 잘 쓰이지 않습니다.

자연 경사(natural gradient): 표준 헤시안 대신 피셔 정보 행렬(Fisher information matrix), 즉 로그 가능도(log-likelihood)의 기댓값 헤시안을 사용합니다. 확률 분포의 기하 구조를 고려합니다. K-FAC(Kronecker-Factored Approximate Curvature)는 피셔 행렬을 크로네커 곱(Kronecker product)으로 근사하여 신경망에 적용할 수 있게 합니다.

헤시안 프리 최적화(Hessian-free optimization): H를 직접 만들지 않고 켤레 기울기법(conjugate gradient)으로 Hx = g를 풉니다. 헤시안-벡터 곱(Hessian-vector product)만 있으면 되며, 자동 미분(automatic differentiation)으로 O(n)에 계산할 수 있습니다.

대각 근사(diagonal approximation): Adam의 2차 모멘트(second moment)는 헤시안 대각 성분(diagonal)의 대각 근사로 볼 수 있습니다. AdaHessian은 허친슨 추정기(Hutchinson's estimator)를 사용해 실제 헤시안 대각 성분을 활용합니다.

만들어 보기

단계 1: 볼록성 검사기(Convexity Checker)

점을 표본 추출(sampling)하고 정의(definition)를 확인하면서 볼록성을 경험적으로(empirical) 검사하는 함수를 만듭니다.

import random
import math

def check_convexity(f, dim, bounds=(-5, 5), samples=1000):
    violations = 0
    for _ in range(samples):
        x = [random.uniform(*bounds) for _ in range(dim)]
        y = [random.uniform(*bounds) for _ in range(dim)]
        t = random.uniform(0, 1)
        mid = [t * xi + (1 - t) * yi for xi, yi in zip(x, y)]
        lhs = f(mid)
        rhs = t * f(x) + (1 - t) * f(y)
        if lhs > rhs + 1e-10:
            violations += 1
    return violations == 0, violations

단계 2: 2차원 뉴턴 방법

명시적인(explicit) 헤시안을 사용해 뉴턴 방법을 구현합니다. 경사 하강법과 수렴 속도를 비교합니다.

def newtons_method(f, grad_f, hessian_f, x0, steps=50, tol=1e-12):
    x = list(x0)
    history = [x[:]]
    for _ in range(steps):
        g = grad_f(x)
        H = hessian_f(x)
        det = H[0][0] * H[1][1] - H[0][1] * H[1][0]
        if abs(det) < 1e-15:
            break
        H_inv = [
            [H[1][1] / det, -H[0][1] / det],
            [-H[1][0] / det, H[0][0] / det],
        ]
        dx = [
            H_inv[0][0] * g[0] + H_inv[0][1] * g[1],
            H_inv[1][0] * g[0] + H_inv[1][1] * g[1],
        ]
        x = [x[0] - dx[0], x[1] - dx[1]]
        history.append(x[:])
        if sum(gi ** 2 for gi in g) < tol:
            break
    return history

단계 3: 라그랑주 승수 풀이

라그랑지언에 경사 하강법을 적용해 제약 최적화를 풉니다.

def lagrange_solve(f_grad, g_val, g_grad, x0, lr=0.01,
                   lr_lambda=0.01, steps=5000):
    x = list(x0)
    lam = 0.0
    history = []
    for _ in range(steps):
        fg = f_grad(x)
        gv = g_val(x)
        gg = g_grad(x)
        x = [
            xi - lr * (fgi + lam * ggi)
            for xi, fgi, ggi in zip(x, fg, gg)
        ]
        lam = lam + lr_lambda * gv
        history.append((x[:], lam, gv))
    return history

단계 4: 1차 방법과 2차 방법 비교

같은 이차 함수(quadratic function)에서 경사 하강법과 뉴턴 방법을 실행합니다. 수렴까지 필요한 단계 수를 셉니다.

def quadratic(x):
    return 5 * x[0] ** 2 + x[1] ** 2

def quadratic_grad(x):
    return [10 * x[0], 2 * x[1]]

def quadratic_hessian(x):
    return [[10, 0], [0, 2]]

뉴턴 방법은 이차 함수에서 정확(exact)하므로 1단계 만에 수렴합니다. 경사 하강법은 헤시안의 고윳값이 5배 차이가 나서 길게 늘어진 골짜기(elongated valley)가 만들어지기 때문에 수백 단계가 필요합니다.

사용하기

볼록성 분석은 ML 모형과 풀이기(solver) 선택에 곧바로 적용됩니다.

볼록 문제(로지스틱 회귀, SVM, LASSO):

• 전용 풀이기를 사용합니다. liblinear, CVXPY, scipy.optimize.minimize(method='L-BFGS-B') 등
• 유일한 전역 해(unique global solution)를 기대할 수 있습니다.
• 2차 방법(second-order method)이 실용적이고 빠릅니다.

비볼록 문제(신경망):

• 1차 방법(SGD, Adam)을 사용합니다.
• 해가 초기화(initialization)와 무작위성(randomness)에 의존한다는 점을 받아들입니다.
• 과매개변수화, 잡음, 학습률 스케줄을 암묵적 정규화로 활용합니다.
• 전역 최솟값을 찾는 데 시간을 들이지 않습니다. 좋은 국소 최솟값이면 충분합니다.

from scipy.optimize import minimize

result = minimize(
    fun=lambda w: sum((y - X @ w) ** 2) + 0.1 * sum(w ** 2),
    x0=np.zeros(d),
    method='L-BFGS-B',
    jac=lambda w: -2 * X.T @ (y - X @ w) + 0.2 * w,
)

SVM에서는 쌍대 형식(dual formulation)이 커널 트릭을 가능하게 합니다.

from sklearn.svm import SVC

svm = SVC(kernel='rbf', C=1.0)
svm.fit(X_train, y_train)
print(f"Support vectors: {svm.n_support_}")

산출물 만들기

이 lesson의 최종 산출물은 다음과 같습니다.

• code/convex.py: 볼록성 검사기, 헤시안 분석, 뉴턴 방법, 라그랑주 승수, 정규화 기하 시연을 포함합니다.
• outputs/skill-convexity-checker.md: 최적화 문제가 볼록인지 확인하고 풀이기를 선택하는 skill 문서입니다.

연습문제

1. 쉬움 — 볼록성 갤러리(convexity gallery). 검사기로 다음 함수들을 검사합니다. f(x) = x^4, f(x) = sin(x), f(x,y) = x^2 + y^2, f(x,y) = x*y, f(x) = max(x, 0). 각 결과가 왜 타당한지 설명합니다.

2. 중간 — 뉴턴 방법 대 경사 하강법 경주. 시작점 (10, 10)에서 f(x,y) = 50*x^2 + y^2를 두 방법으로 최적화합니다. 손실 < 1e-10에 도달하기까지 각각 몇 단계가 필요한가요? 조건수(condition number), 즉 헤시안의 최대 고윳값과 최소 고윳값의 비율이 커지면 경사 하강법에는 어떤 일이 일어나나요?

3. 중간 — 라그랑주 승수의 기하학. x + 2y = 4 조건 아래에서 f(x,y) = (x-3)^2 + (y-3)^2를 최소화합니다. 해에서 f의 기울기가 g의 기울기와 평행한지 확인합니다.

4. 어려움 — 정규화 제약. L1 제약 최적화를 구현합니다. |x| + |y| <= 1 조건 아래에서 (x-3)^2 + (y-2)^2를 최소화합니다. 해의 좌표 중 하나가 0이 되는지 보입니다. 이것이 마름모 제약(diamond constraint)에서 나오는 희소성입니다.

5. 어려움 — 헤시안 고윳값 분석. 로젠브록 함수(Rosenbrock function)의 헤시안을 (1,1)과 (-1,1)에서 계산합니다. 두 점에서의 고윳값을 구합니다. 고윳값이 최솟값 근처와 먼 곳의 곡률에 대해 무엇을 알려주나요?

핵심 용어

더 읽을거리

• Boyd & Vandenberghe: Convex Optimization: 온라인으로 공개된 볼록 최적화 표준 교재입니다.
• Bottou, Curtis, Nocedal: Optimization Methods for Large-Scale Machine Learning (2018): 볼록 최적화 이론과 딥러닝 실무를 연결해 정리합니다.
• Choromanska et al.: The Loss Surfaces of Multilayer Networks (2015): 비볼록 신경망 손실 지형이 생각만큼 나쁘지 않은 이유를 다룹니다.
• Nocedal & Wright: Numerical Optimization: 뉴턴 방법, L-BFGS, 제약 최적화를 포괄적으로 다루는 참고 서적입니다.