Optimization & Convex Geometry

1. Overview

최적화 및 볼록 기하학(Optimization & Convex Geometry, OCG)은 컴퓨터 과학이 직면한 가장 현실적인 질문인 "어떻게 하면 최소한의 비용으로 최대한의 효율을 낼 것인가"를 수학적으로 해결하는 학문입니다.

학습자는 함수가 볼록(Convex)할 때 지역 최솟값이 곧 전역 최솟값이 되는 볼록성의 물리적 이점을 배우고, 기울기를 따라 해를 찾아가는 **경사 하강법(Gradient Descent)**의 수렴 원리를 익힙니다. 특히 제약 조건이 있는 상황에서 최적해를 찾는 **라그랑주 승수법(Lagrange Multipliers)**은 복잡한 자원 할당이나 머신러닝의 규제(Regularization) 문제를 풀기 위한 필수적인 물리 논리입니다. 이를 통해 단순한 코딩을 넘어 알고리즘이 '최선의 경로'를 수학적으로 따라가도록 설계하고 통제하는 능력을 갖춥니다.

2. Scope & Boundaries

In-Scope

• Convexity Physics: 볼록 집합과 볼록 함수의 정의 및 2차 미분(Hessian)을 통한 판별
• Unconstrained Optimization: 경사 하강법, 뉴턴 방법(Newton's Method)의 수렴 역학
• Constrained Optimization: 탄젠트 평면과 등위곡선을 이용한 라그랑주 승수법 논리
• Duality Theory: 주 문제(Primal)와 쌍대 문제(Dual)의 관계 및 KKT 조건의 물리적 의미

Out-of-Scope

• 비볼록(Non-convex) 공간에서의 휴리스틱 최적화(유전 알고리즘 등) 상세 (AI 특수 영역)
• 선형 계획법(Linear Programming)의 심플렉스 알고리즘 디테일 (04-03 OPT 영역으로 위임)

Boundaries

• OCG vs. Numerical Methods: 수치 해석이 '근사치를 구하는 기계적 스텝'에 집중한다면, OCG는 '최적해가 존재할 수 있는 공간의 기하학적 구조와 보장 조건'에 집중합니다.

3. Counterexample

• 단순히 "라이브러리의 minimize 함수를 호출하는 것"은 OCG 학습이 아닙니다. 왜 특정 러닝 레이트(Learning Rate)가 너무 크면 최적해 근처에서 발산하게 되는지 함수의 곡률(Hessian) 관점에서 설명할 수 있어야 하고, 함수가 볼록하지 않을 때 **지역 최솟값(Local Minimum)**의 물리적 덫에 걸려 전역 해를 찾지 못하는 모순을 증명하지 못한다면 OCG의 깊이를 이해하지 못한 것입니다.

4. Prerequisites

• Matrix Calculus & Eigendecomposition (Basic): 그래디언트 벡터와 헤세 행렬 연산이 필수입니다. (03-02 MCE)
• Vector Spaces & Linear Maps (Recommended): 다차원 평면과 법선 벡터 기하학이 권장됩니다. (03-01 VLM)

5. Learning Map

1. Landscape Analysis: 함수의 굴곡을 분석하여 함정(Local Min)과 목표(Global Min)가 하나뿐인 '착한 공간'을 찾습니다.
2. Descent Mechanics: 현재 위치에서 가장 빨리 낮아지는 방향(Gradient)을 계산하고 물리적으로 이동합니다.
3. Boundaries & Constraints: 자원의 한계(부등식/등식 제약)라는 물리적 장벽 위에서의 최적 지점을 도출합니다.
4. Duality Conversion: 풀기 어려운 최적화 문제를 논리적으로 뒤집어(Dual) 더 쉬운 문제로 치환하여 해결합니다.

6. Learning Topics

Basic

Core: 볼록성과 그래디언트의 기하학 (Convex Basics)

• Why to Learn: 한 번 찾은 최솟값이 '진짜 최전의 정답'임을 수학적으로 확신하기 위함입니다.
• What to Learn:
  • 볼록 집합(Convex Set): 임의의 두 점을 이은 선분이 집합 내에 존재하는 물리적 특성
  • 볼록 함수와 젠센의 부등식(Jensen's Inequality)의 수리적 의미
  • 1차 미분 조건: $f(y) \geq f(x) + \nabla f(x)^T(y-x)$의 기하학적 평면 해석
• How to Learn:
  • 포물선($x^2$)과 로그($\log x$) 함수의 볼록성을 2차 미분 부호로 판별하는 실습
  • 볼록하지 않은 함수(예: $sin x$)에서 시작점에 따라 최솟값이 달라지는 현상 관찰
• Implement: 함수의 볼록성을 샘플링을 통해 확률적으로 테스트하거나 헤세 행렬로 확정하는 검증기

Recommended

Core: 경사 하강법과 수렴 제어 (Descent Physics)

• Why to Learn: 알고리즘이 목표치에 도달하는 속도와 정확도를 물리적으로 튜닝하기 위해서입니다.
• What to Learn:
  • 경사 하강법의 업데이트 규칙: $x_{new} = x - \eta \nabla f(x)$
  • 학습률($\eta$)의 결정 물리: 오버슈팅(Overshooting)과 느린 수렴의 트레이드오프
  • 모멘텀(Momentum) 등 가속 기법의 수리적 배경
• How to Learn:
  • 등고선 맵(Contour Map) 위에서 경사 하강법의 이동 경로를 시각화하여 지그재그 현상 분석
  • 함수의 볼록한 정도(Condition Number)가 수렴 속도에 미치는 물리적 영향 연습
• Implement: 단순 경사 하강법에 모멘텀 수식을 추가하여 수렴 속도를 개선한 최적화 엔진

Practical

Core: 제약 조건과 라그랑주 승수 (Optimization with Constraints)

• Why to Learn: 현실의 모든 문제는 예산, 시간, 자원이라는 물리적 '벽' 안에서 최선을 찾아야 하기 때문입니다.
• What to Learn:
  • 등식 제약 조건: 점과 곡선이 만나는 지점의 그래디언트 평행 물리
  • 라그랑주 승수($\lambda$)의 경제학적 의미: 제약 조건 완화 시의 이득
  • 부등식 제약과 KKT(Karush-Kuhn-Tucker) 조건의 4대 논리 기둥
• How to Learn:
  • 원형 제약 조건($x^2+y^2=1$) 내에서 선형 함수의 최댓값을 라그랑주 승수법으로 계산 실습
  • 서포트 벡터 머신(SVM)의 마진 최대화 문제가 어떻게 라그랑주 쌍대 문제로 변환되는지 분석
• Implement: 제약 조건을 함수 내부로 끌어들이는 벌점 함수(Penalty Function) 기반의 최적화 알고리즘

Advanced

Core: 쌍대성 이론과 볼록 최적화 실전 (Duality & Convex Practice)

• Why to Learn: 직접 풀기 복잡한 문제의 해를 찾기 위해 논리적 거울(Dual)을 사용하여 우회 해결하기 위해서입니다.
• What to Learn:
  • 라그랑주 쌍대 함수(Lagrange Dual Function)의 항상 볼록한 성질
  • 강한 쌍대성(Strong Duality)과 슬레이터 조건(Slater's Condition)의 물리적 보장
  • 대규모 행렬 연산이 포함된 볼록 최적화 해결 도구(CVX 등)의 작동 원리
• How to Learn:
  • 원 문제(Primal)의 하한값을 제공하는 쌍대 문제의 특성을 이용해 연산 결과의 정당성 하한선 확인 실습
  • 네트워크 트래픽 흐름 최적화 문제를 쌍대성 관점에서 재정의하여 분산 처리 전략 수립练习
• Implement: 주 문제와 쌍대 문제의 갭(Duality Gap)을 추적하여 최적해 도달 여부를 판정하는 로직

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) 항이 최적화 공간의 기하학적 구조를 어떻게 물리적으로 변형시키는지 분석할 수 있는 가?