Optimization Theory최적화 이론

minimize   f(x)          ← 목적 함수 (objective function)
subject to g_i(x) ≤ 0   ← 부등식 제약 조건
           h_j(x) = 0    ← 등식 제약 조건
           x ∈ ℝⁿ

볼록(Convex):
  - 지역 최솟값 = 전역 최솟값 (수렴 보장)
  - 예: 선형 계획법, SVM, LASSO

비볼록(Non-convex):
  - 여러 지역 최솟값 존재 → 전역 최적 탐색 어려움
  - 예: 신경망, 조합 최적화

선형 계획법 (LP):
  - 목적함수·제약 모두 선형
  - 심플렉스 알고리즘으로 다항 시간 내 해결

이차 계획법 (QP):
  - 목적함수에 이차항 포함, 제약은 선형
  - SVM 학습의 핵심

∇f(x*) + Σ λᵢ ∇gᵢ(x*) + Σ μⱼ ∇hⱼ(x*) = 0   (정류점)
λᵢ ≥ 0                                          (비음성)
λᵢ gᵢ(x*) = 0  for all i                        (상보적 느슨함)
gᵢ(x*) ≤ 0, hⱼ(x*) = 0                         (실현가능성)

헤시안 H = ∇²f(x*)

H 양의 정부호 (positive definite) → 극솟값
H 음의 정부호 (negative definite) → 극댓값
H 부정부호                        → 안장점 (saddle point)

import numpy as np

# 배치 종류
# - Batch GD:     전체 데이터로 기울기 계산 → 정확하나 느림
# - Stochastic GD: 샘플 1개씩 업데이트 → 빠르나 진동
# - Mini-batch GD: 32~256개 묶음 → 실용적 균형

class SGD:
    def __init__(self, lr=0.01, momentum=0.9):
        self.lr = lr
        self.momentum = momentum
        self.v = None

    def step(self, params, grads):
        if self.v is None:
            self.v = {k: np.zeros_like(v) for k, v in params.items()}
        for k in params:
            self.v[k] = self.momentum * self.v[k] - self.lr * grads[k]
            params[k] += self.v[k]
        return params

class AdamOptimizer:
    """Adam: Adaptive Moment Estimation (Kingma & Ba, 2014)"""
    def __init__(self, lr=0.001, beta1=0.9, beta2=0.999, eps=1e-8):
        self.lr = lr
        self.beta1, self.beta2, self.eps = beta1, beta2, eps
        self.m, self.v, self.t = None, None, 0

    def step(self, params, grads):
        if self.m is None:
            self.m = {k: np.zeros_like(v) for k, v in params.items()}
            self.v = {k: np.zeros_like(v) for k, v in params.items()}

        self.t += 1
        updated = {}
        for k in params:
            # 1차/2차 모멘텀 갱신
            self.m[k] = self.beta1 * self.m[k] + (1 - self.beta1) * grads[k]
            self.v[k] = self.beta2 * self.v[k] + (1 - self.beta2) * grads[k]**2

            # 편향 보정 (초기 단계 보상)
            m_hat = self.m[k] / (1 - self.beta1**self.t)
            v_hat = self.v[k] / (1 - self.beta2**self.t)

            updated[k] = params[k] - self.lr * m_hat / (np.sqrt(v_hat) + self.eps)
        return updated

from scipy.optimize import minimize
import numpy as np

# 제약 있는 볼록 최적화 예시 (SVM 마진 최대화)
def objective(x):
    return 0.5 * np.dot(x, x)  # ||w||² 최소화

constraints = [
    {'type': 'ineq', 'fun': lambda x: np.dot([1, 1], x) - 1},   # y₁(w·x₁+b) ≥ 1
    {'type': 'ineq', 'fun': lambda x: -np.dot([1, -1], x) + 1}, # y₂(w·x₂+b) ≥ 1
]

result = minimize(objective, x0=[0, 0], method='SLSQP', constraints=constraints)
print(f"최적해: {result.x}, 목적함수: {result.fun:.4f}")

볼록 함수 + Lipschitz 연속 기울기:
  학습률 α ≤ 1/L 이면 O(1/t) 수렴 (t = 반복 횟수)

강볼록(Strongly Convex) 함수:
  선형 수렴 (geometric convergence): O(ρᵗ), ρ < 1

비볼록:
  KKT 정류점 수렴 가능 (전역 최적 보장 없음)

뉴턴법:
  극소 근방에서 이차 수렴 (quadratic convergence)

예: 자동차 설계
  minimize  연료 소비량  f₁(x)
  minimize  제조 비용    f₂(x)

→ 파레토 최적: f₁ 개선 시 f₂ 악화 불가피한 해의 집합
   한쪽을 희생하지 않고는 다른 쪽을 더 개선할 수 없는 상태