[Optimization] 최적화 (1) - 최적화 문제 정의와 개요

최적화 문제의 정의, 적용 사례를 정리합니다.

최적화 문제 정의

Optimization Problems 최적화 문제는 여러 개의 선택가능한 후보 중 Optimal value/solution 최적의 해 혹은 그에 근접한 값을 찾는 문제이다.

데이터 분석은 최종적으로 주어진 기준에 따라 적합한 수식을 찾는데 이 또한 최적화 과정이라 볼 수 있다. 예를 들어, 머신러닝에서 비용함수 최소화, 최대화 시키는 모델의 파라미터를 구하는 과정이 최적화 문제로 정의될 수 있다.

일반적으로 최적화 문제를 다음과 같은 형태로 표현할 수 있다.

$\min_{x \in D} \quad f(x)$
$\text{subject to} \quad g_i(x) \leq 0 ~ \text{for all } ~ i=1, \dotsc, m$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ h_j(x) = 0 ~ \text{for all } ~ j=1, \dotsc, n$

• $x \in R^n$ : optimization variable 최적화 변수
• $f: R^n \rightarrow R$ objective or cost function 목적함수, 비용함수
• $g_i: R^n \rightarrow R, i = 1, ..., m$ inequality constraint functions 부등식 제한조건
• $h_i: R^n \rightarrow R, j = 1, ..., r$ equality constraint functions 등식 제한조건

상기 조건을 모두 만족하는 정의역에서 목적함수 $f$를 최소로 만드는 벡터 $x^*$를 optimal solution 최적의 해라고 한다.

최적화 문제의 적용

• Portfolio optimization 포트폴리오 최적화
  • Objective : 전반적인 위험도 또는 주가 수익률 분산 return variance
  • Variables : 각 자산에 대한 투자금
  • Constraints : 예산, 자산당 최소/최대 투자가능 금액, 최소 수익
• Device sizing in electronic circuits 소비 전력 최적화를 위한 전자 회로 부품 사이징
  • Objective : 전력소비량
  • Variables : 각 부품의 너비와 길이
  • Constraints : 제조 공정상 제약사항, 최대 면적
• Data fitting - process of fitting models to data and analyzing the accuracy of the fit
  • Objective : 모델의 예측값에 대한 에러
  • Variables : 모델 파라미터
  • Constraints : 사전 정보, 파라미터에 대한 제약사항

Continuous Optimization

Continuous Optimization - Gradient Descent, Lagrange Multipliers, Convex Optimization을 정리합니다.

최적화 문제 개요

Continuous Optimization 최적화 문제를 unconstrained and constrained optimization 크게 2가지 갈래로 나누어볼 수 있다. 이 중 대표적인 아이디어는 Gradient Descent, Convex Optimization이다.

최적화 문제의 목적함수가 미분 가능하다고 가정하에 하기 방법론들을 정리할 것이다.

1. Unconstrained Optimization
   • Optimization Using Gradient Descent
     • Stepsize
     • Momentum 모멘텀
     • Stochastic gradient descent(SGD) 확률적 경사 하강법
2. Constrained Optimization
   • Lagrange Multipliers 라그랑주 승수법
3. Convex Optimization
   • Linear Programming 선형계획법
   • Quadratic Programming 2차계획법

---

Source&Reference : Mathematics for Machine Learning, MIT - Discrete Optimization vs Continuous Optimization, 모두를 위한 컨벡스 최적화, Convex Optimization — Boyd & Vandenberghe