Optimization & Convex Geometry

1. Overview

최적화와 볼록 기하학(Optimization & Convex Geometry, OCG)은 컴퓨터 공학이 직면한 수십만 개의 선택지 중에서 "어디로 가야 가장 자원을 덜 쓰고 최고 효율을 뽑아낼 수 있는가?"를 수학의 중력(Gradient)을 이용해 맹렬하게 추적하는 '계산 기하학의 정점'입니다.

학습자는 다차원 곡면에서 산골짜기(최소값)를 찾아 내려가는 **경사 하강법(Gradient Descent)**의 미분 역학을 뜯어보고, 공간이 활처럼 휘어져 있어(Convex) 한 번 미끄러지면 무조건 바닥(Global Minimum)에 도달함을 수학적으로 보장하는 **볼록 최적화(Convex Optimization)**의 절대 물리를 해부합니다. 나아가 제약 조건(Constraints)에 갇힌 우주에서 라그랑주 승수(Lagrange Multipliers)를 통해 선을 넘지 않으며 극한값을 캐내는 최적화 아키텍트 능력을 확보합니다.

2. Scope & Boundaries

In-Scope

• 최적화 기하학 (Optimization Geometry): 목적 함수(Objective Function), 전역 최솟값(Global Minimum)과 지역 최솟값(Local Minimum).
• 미분과 경사 하강 역학 (Gradient Mechanics): 1차 미분(Gradient, $\nabla f$), 경사 하강법(Gradient Descent), 학습률(Learning Rate, Step Size).
• 볼록 함수와 헤시안 (Convexity & Hessian): 볼록 집합(Convex Set), 볼록 함수(Convex Function, $f(\theta x + (1-\theta)y) \le \dots$), 2차 미분(Hessian Matrix, $\nabla^2 f$), 뉴턴 방법(Newton's Method).
• 제약 조건 최적화 (Constrained Optimization): 등식/부등식 제약(Constraints), 라그랑주 승수법(Lagrange Multipliers), KKT 조건(Karush-Kuhn-Tucker Conditions).

Out-of-Scope

• 미니배치 확률적 최적화: 딥러닝에서 쓰는 SGD, Adam, RMSprop 옵티마이저 상세 → 11-01. Learning & Optimization 영역.
• 선형 계획법의 심플렉스(Simplex) 튜닝: OR(Operations Research) 및 산업공학 수준의 수리 계획법 코드 디버깅 → 산업공학 영역.

Boundaries

• OCG vs. Matrix Calculus (01-03-02): 행렬 미적분(01-03-02)이 다변수 함수를 미분하여 자코비안이나 헤시안 행렬을 "계산하는 도구"를 던져준다면, OCG는 그 도구를 이용해 수만 개의 계곡(지형) 중에서 "어느 계곡으로 뛰어내려야 가장 빠르게 골짜기에 박히는지" 기하학적 궤적(Trajectory)을 조종하는 응용 물리학입니다.

3. Counterexample

• 논-컨벡스(Non-convex)의 치명적 착각 (Local Minimum Fallacy): "경사 하강법을 돌려서 기울기가 0이 되었으니 드디어 전역 최적해(Global Optimum)를 찾았다"며 기뻐하는 딥러닝 뉴비의 무지. 함수가 구불구불한 뱀처럼 생긴 Non-convex 지형이라면, 당신이 멈춘 그곳은 그저 산등성이의 얕은 웅덩이(Local Minimum)나 안장점(Saddle Point)일 뿐, 진정한 바닥이 아닙니다. 볼록 기하학을 모르면 자신이 갇힌 웅덩이가 세상의 바닥이라고 착각하는 시야의 협착이 발생합니다.
• 학습률 오버슈팅 (Learning Rate Overshoot): 경사 하강법에서 보폭(Step Size)을 무식하게 크게 잡아놓고 수렴(Convergence)을 바라는 행위. 헤시안(Hessian) 행렬의 고유값(곡률, Curvature)을 계산하지 않은 채 스텝을 밟으면, 알고리즘은 계곡의 양옆을 탁구공처럼 미친 듯이 튕기다가(Oscillation) 마침내 우주 밖으로 튕겨 나가는 발산(Divergence, NaN 에러) 폭발을 일으킵니다.

4. Prerequisites

• 행렬 미적분과 고유 분해 (Basic): 목적 함수가 최소화되려면 1차 미분(그래디언트)은 0이 되어야 하고, 2차 미분(헤시안 행렬)의 고유값들이 모두 양수(Positive Definite)여야 아래로 볼록하다는 것을 이해해야 합니다. (01-03-02 MCE)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 최적화의 해부학과 지형학 (Optimization Geometry)

• Why to Learn: 프로그램이 풀어야 할 비즈니스 문제(예: 배달 동선 최소화, 추천 오차 최소화)를 $f(x)$ 라는 수학적 산맥(지형)으로 치환하여 컴퓨터가 계산할 수 있는 과녁판을 만들기 위함입니다.
• What to Learn:
  • Concepts: 목적 함수(Objective Function), 파라미터 공간(Parameter Space).
  • Skills: 전역 최솟값(Global Minimum), 지역 최솟값(Local Minimum), 안장점(Saddle Point).
  • Tools: 등고선(Contour Plot) 및 3D 서피스 시각화.
  • Trade-offs: "조건 없이 그냥 제일 작은 값을 찾아라(Unconstrained)"의 깔끔한 미분 역학 vs "비용은 100만 원 이하, 거리는 10km 이내여야 함(Constrained)"이 추가될 때 지형의 모양 자체가 기괴하게 꺾여버리는 현실 세계의 제약 장벽.
• How to Learn:
  • 1단계: $f(x) = x^4 - 2x^2 + x$ 같은 다항 함수 그래프를 그려보고, 기울기가 0(평평한 곳)인 지점이 무려 3군데(극소 2개, 극대 1개)나 튀어나오는 수학적 지뢰밭을 시각적으로 뜯어봅니다.
  • 2단계: 안장점(Saddle Point, 말안장 모양)에서는 $x$ 축으로는 가장 낮지만 $y$ 축으로는 가장 높은 기괴한 위상 공간이 펼쳐지며, 단순한 1차 미분($\nabla f = 0$)만 믿다가는 여기서 엔진이 영원히 멈춰버리는(Stuck) 물리를 해부합니다.
• Implement: 2차원(x, y) 입력 변수를 받아 결과값 z를 내뱉는 복잡한 목적 함수(Ackley Function 등)를 넘파이 메시그리드(Meshgrid)로 3D 렌더링하여 산봉우리와 끝없는 웅덩이(Local Minima)들을 눈으로 확인하는 지형 뷰어.

Recommended

Core Topic 02: 1차 미분과 경사 하강 역학 (Gradient Descent)

• Why to Learn: 눈을 감고 산봉우리에 떨어졌을 때, 수억 개의 탐색 경로 중 오직 발바닥의 기울기(미분)만을 느끼며 가장 가파르게 골짜기로 다이빙하는 GPS를 설계하기 위함입니다.
• What to Learn:
  • Concepts: 그래디언트 벡터(Gradient, $\nabla f$), 방향 도함수(Directional Derivative).
  • Skills: 경사 하강법 알고리즘($\theta_{t+1} = \theta_t - \eta \nabla f(\theta_t)$), 학습률(Learning Rate, $\eta$).
  • Tools: 스텝 스케줄러(Step Scheduler).
  • Trade-offs: 보폭($\eta$)을 좁게 촘촘히 밟아 안전하게 바닥까지 기어가는 미친 듯한 연산 시간 지연(Under-stepping) vs 보폭을 크게 잡아 순식간에 내려가려다 계곡 반대편으로 튕겨 나가버리는 폭발(Overshooting) 사이의 아슬아슬한 줄타기.
• How to Learn:
  • 1단계: 그래디언트 텐서 $\nabla f$ 의 본질이 단순히 기울기가 아니라, "현재 위치에서 목적 함수 값이 가장 가파르게 **상승(Ascent)**하는 우주적 방향 화살표"라는 점을 기하학적으로 증명하고, 왜 앞에 마이너스($-$)를 붙여야 하강(Descent)이 되는지 뜯어봅니다.
  • 2단계: 좁고 깊은 타원형 계곡(지그재그 지형)에서 경사 하강법이 바닥을 향해 똑바로 가지 못하고 양쪽 벽을 탁구공처럼 때리며(Oscillation) 지그재그로 내려가는 끔찍한 물리적 비효율을 해부합니다.
• Implement: 이차 함수 $f(x, y) = 10x^2 + y^2$ (타원형 계곡) 위에서, 학습률 $\eta$ 를 0.01, 0.08, 0.12로 세팅했을 때 그래디언트 디센트가 바닥$(0,0)$ 을 찾아가는 $x, y$ 의 궤적(Trajectory) 좌표를 리스트로 찍어내어 수렴과 발산을 텍스트로 증명하는 엔진.

Practical

Core Topic 03: 볼록성과 2차 미분 헤시안 (Convexity & Hessian)

• Why to Learn: 내 코드가 웅덩이(Local Minima)에 빠진 게 아닌지 의심하는 공포에서 벗어나, "이 지형은 완벽한 밥그릇 모양(Convex)이라 한 번 굴리면 무조건 중앙 최저점에 박힌다"는 우주적 확신을 수학적으로 증명(Proof)하기 위함입니다.
• What to Learn:
  • Concepts: 볼록 집합(Convex Set), 볼록 함수(Convex Function).
  • Skills: 옌센의 부등식(Jensen's Inequality), 헤시안 행렬(Hessian Matrix, $\nabla^2 f$), 양의 정부호성(Positive Definite).
  • Tools: 뉴턴 방법(Newton's Method).
  • Trade-offs: 오직 발밑의 기울기(1차 미분)만 보고 걷는 경사 하강법의 멍청함 vs 전체 계곡의 곡률(2차 미분, Hessian)까지 전부 계산하여 단숨에 워프(Warp)하는 뉴턴 메서드의 미친 수렴 속도, 그리고 그 역행렬을 구할 때 CPU가 녹아버리는 $O(N^3)$ 의 살인적 연산량.
• How to Learn:
  • 1단계: 어떤 곡면 상의 두 점을 직선으로 이었을 때, 그 선분이 무조건 곡면보다 '위에' 떠 있다면($f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$), 그 공간은 완벽한 볼록 공간(Convex)이며 웅덩이가 오직 1개뿐임을 위상 수학적으로 뜯어봅니다.
  • 2단계: 2번 미분한 결과(헤시안 행렬)의 고유값들이 모두 0보다 크다(양의 정부호)는 성질이, 3차원 공간에서 밥그릇이 위로 입을 쫙 벌리고 있는 기하학적 형태와 물리적으로 1<1> 대응됨을 해부합니다.
• Implement: 입력된 함수의 헤시안 행렬 값을 계산하여 고유값 분해(Eigendecomposition)를 친 뒤, 고유값 중 하나라도 음수(-)가 있으면 "경고: 안장점(Saddle Point) 또는 Non-convex 지형 감지!"를 콘솔에 토해내는 곡률 검증기 모듈 작성.

Advanced

Core Topic 04: 제약 조건과 라그랑주 승수 (Constraints & KKT)

• Why to Learn: "서버 100대(비용 제약)를 넘지 않으면서 처리량을 극대화하라"처럼, 현실 세계의 펜스(제약식)가 처진 산속에서 선을 밟으면서도 가장 낮은 계곡을 귀신같이 찾아내는 서포트 벡터 머신(SVM)의 심장을 깎아내기 위해서입니다.
• What to Learn:
  • Concepts: 라그랑주 함수(Lagrangian Function, $L(x, \lambda)$), 라그랑주 승수(Lagrange Multiplier, $\lambda$).
  • Skills: KKT 조건(Karush-Kuhn-Tucker Conditions), 등식 제약($g(x)=0$)과 부등식 제약($h(x) \le 0$).
  • Tools: 쌍대성(Duality, Primal vs Dual Problem).
  • Trade-offs: 제약식(펜스)을 억지로 목적 함수 안에 집어넣어 $\lambda$ 라는 가상의 페널티 미지수를 추가해 문제를 뻥튀기하는(Lagrangian) 복잡성 증대 vs 이로 인해 제약 조건 위를 걷는 그래디언트들의 물리적 힘겨루기가 수식 하나로 완벽히 제어되는 수학적 마법.
• How to Learn:
  • 1단계: 산을 내려가는 중력 화살표($-\nabla f$)와 펜스 밖으로 튕겨 내는 수직 저항력 화살표($\lambda \nabla g$)가 팽팽하게 맞서 평형을 이룰 때($\nabla f + \lambda \nabla g = 0$), 바로 그 지점이 제약 조건하의 전역 최적해(Optimal Point)가 됨을 기하학적 벡터 힘의 평형(Physics Equilibrium)으로 뜯어봅니다.
  • 2단계: 등호($=$) 뿐만 아니라 작거나 같다($\le$)라는 부등식 펜스(Inequality Constraints)가 주어졌을 때, 해가 펜스 안에 있으면 $\lambda=0$ 이고 펜스 선반에 걸려 있으면 $\lambda > 0$ 이 되는 KKT 조건의 상보적 여유성(Complementary Slackness) 역학을 해부합니다.
• Implement: 2차원 좌표 $x, y$ 에서 $x^2 + y^2 = 1$ (원형 펜스 제약) 위를 맴돌면서 함수 $f(x, y) = x + y$ 의 최대값을 찾을 때, 라그랑주 승수 공식을 코드로 풀어 정답 접점($\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}$)을 기계적으로 뽑아내는 수학 엔진 파이프라인.

7. Terminology

8. References

Primary

• [P1] CS2023 - DS/Linear Algebra — Optimization foundations.
• [P4] DS-BoK - Data Analytics / Optimization Methods — ML context.

Secondary

• [Convex Optimization] Boyd & Vandenberghe — The world's most influential text on the subject.
• [Numerical Optimization] Nocedal & Wright — Focus on implementation physics.

Industry

• [Stochastic Gradient Descent in Big Data] — Real-world optimization mechanics.
• [Portfolio Optimization in Finance] — Constrained optimization in industry.

9. Final Checklist

Primary

• 특정 함수의 헤세 행렬(Hessian)을 계산하여, 그것이 '양의 정부호(Positive Definite)'임을 통해 볼록성을 수리 증명할 수 있는 가? (P1)
• 경사 하강법에서 학습률($\eta$)이 너무 작을 때의 시간 효율 손실과, 너무 클 때의 진동 물리 현상을 수식으로 설명 가능한가? (P1)

Secondary

• 부등식 제약 조건 하에서 '상보적 느슨함(Complementary Slackness)' 조건이 왜 최적해에서 물리적으로 성립해야 하는지 서술 가능한가?
• 볼록 최적화 문제에서 '지역적 최적해(Local Optimum)'가 곧 '전역적 최적해(Global Optimum)'가 됨을 논리적으로 입증할 수 있는가?

Industry

• 서버 자원 할당 시, 각 서버의 용량 제한이라는 부등식 제약 조건 내에서 전체 응답 지연을 최소화하는 라그랑주 모델을 설계할 수 있는 가? (SFIA)
• 머신러닝 모델의 오버피팅을 막기 위한 정규화(Regularization) 항이 최적화 공간의 기하학적 구조를 어떻게 물리적으로 변형시키는지 분석할 수 있는 가?