최적화 문제

최적화 문제 (Optimization Problem)

최적화 문제의 정의

• 최적화(Optimization) 문제란 어떤 목적함수(Objective Function)의 함수값을 최적화(최대화 또는 최소화)시키는 변수(파라미터) 조합을 찾는 문제를 의미한다.
• 최적화 문제의 기본 형태는 다음과 같다.

$$\underset{\mathbf{x}}{\min }f(\mathbf{x})|\underset{\mathbf{x}}{\max }f(\mathbf{x})$$

• $\mathbf{x}$ : 최적화 변수 (Optimization Variable/Parameter)
• $f(\mathbf{x})$ : 목적 함수 (Objective Function)
• ${\mathbf{x}}^{\ast }$ : 최적해 (Optimal Solution)

주요 최적화 방법

• 목적 함수의 형태에 따라 주로 다음과 같은 최적화 방법들이 사용된다.
  • Newton’s Method
    • 2차 미분 정보(Hessian)를 사용하여 최적해 도출
  • Gradient Descent
    • 1차 미분 정보(Gradient)를 사용하여 최적해 도출
  • Gauss-Newton Method / Levenberg-Marquardt Method
    • 비선형 최소제곱 문제(Non-linear Least Square)에 특화된 방법으로, Newton Method의 변형

---

목적 함수 (Objective Function)

정의 및 역할

• 최적화하려는 함수를 목적함수(Objective function) 또는 비용함수(Cost function) 라 하며, 머신러닝에서 모델의 예측값과 실제값의 차이를 측정하는 손실 함수 (Loss Function) 라고 불리기도 한다.
• 목적 함수의 수학적 형태와 문제에 포함된 제약 조건의 유무는 최적화 문제를 해결하는 데 사용되는 알고리즘과 방법론을 결정하는 중요한 요소이다.

Convex vs Non-Convex

• 목적 함수의 볼록성(Convexity) 은 최적화 문제의 난이도와 해결 방법에 결정적인 영향을 미친다.

Convex Function

• 볼록 함수(Convex Function)는 함수의 두 점을 직선으로 연결했을 때 그 직선이 함수 그래프 위에 존재하는 것을 의미한다.
• 수학적으로는 임의의 두 점 ${\mathbf{x}}_1,{\mathbf{x}}_2$와 $\lambda \in [0,1]$에 대해 다음을 만족한다.

$$f(\lambda {\mathbf{x}}_1+(1-\lambda ){\mathbf{x}}_2)\le \lambda f({\mathbf{x}}_1)+(1-\lambda )f({\mathbf{x}}_2)$$

• (2차 미분을 이용한 볼록 함수 판별법) 이계 도함수 $f^{\prime \prime }(x)$는 일계 도함수 $f^{\prime }(x)$의 도함수 이다. 이때 $f(x)$가 볼록 함수라면 $f^{\prime }(x)$가 증가 함수여야 하며, $f^{\prime }(x)$가 증가 함수라면 모든 $x$에 대해 $f^{\prime \prime }(x)\ge 0$를 만족해야 한다.
• Convex Function의 특징 중 가장 중요한 것은 지역 최적해(Local Minimum)가 곧 전역 최적해(Global Minimum)가 된다는 것이며, 따라서 최적해를 찾는 문제가 상대적으로 단순하다.

$$\text{Local Minimum}=\text{Global Minimum}$$

• 대표적인 함수로는 $f(x)=x^2$, $f(x)=e^x$, $f(x)=|x|$ 등이 있다.

Non-Convex Function

• 볼록 함수가 아닌 모든 함수를 비볼록 함수(Non-Convex Function) 이라 하며, 두 점을 잇는 직선이 함수의 그래프 아래로 내려갈 수 있다.
• 여러 개의 지역 최적해(Local Mimimum)을 가질 수 있으므로 전역 최적해(Global Minimum)를 찾는 것이 상대적으로 어렵다.

$$\text{Local Minimum}\ne \text{Global Minimum}$$

• 대표적인 함수로는 $f(x)=\sin (x)$, $f(x)=\cos (x)$, 신경망의 손실 함수 등이 있다.

Local Optimum vs Global Optimum

Local Optimum

• 지역 최적해 (Local Optimum)은 목적 함수가 특정 이웃 내에서 가질 수 있는 가장 작은(최소화 문제의 경우) 또는 가장 큰(최대화 문제의 경우) 함수값을 만드는 변수 조합이다.
• 이는 전체 탐색 공간에서는 최적값이 아닐 수 있다.
• 비볼록 함수는 여러 개의 지역 최적해(Local Optimum)를 가질 수 있으며, 이들 중 하나만이 전역 최적해(Global Optimum)일 수 있다.
• 예를 들어, 다음 비볼록 함수 $f(x)$의 경우, $x=0$에서 Local Maximum, $x\pm \sqrt{2}$에서 Local Minimum(동시에 Global Minimum)을 가진다.

$$f(x)=x^4-4x^2+3$$

Global Optimum

• 전역 최적해 (Global Optimum)은 전체 탐색 공간 내에서 가질 수 있는 가장 작은(최소화 문제의 경우) 또는 가장 큰(최대화 문제의 경우) 함수값을 만드는 변수 조합이다.
• 최적화 문제에서 궁극적으로 찾고자 하는 해이며, 절대적인 최적값을 의미한다.
• 볼록 함수(Convex Function)의 경우, 모든 지역 최적해(Local Optimum)가 곧 전역 최적해(Global Optimum)가 되므로, 전역 최적해를 찾는 것이 상대적으로 용이하다.
• 반면, 비볼록 함수(Non-Convex Function)는 여러 개의 지역 최적해를 가질 수 있으며, 이들 중 하나만이 전역 최적해일 수 있기 때문에 전역 최적해를 찾는 것이 상대적으로 어렵고 복잡한 문제이다.
• 예를 들어, 다음 비볼록 함수 $f(x)$의 경우, 두 개의 지역 최소값을 가지며, 그 중 더 작은 값이 전역 최소값이 된다.

$$f(x)=x^4-4x^2+x$$

목적 함수의 형태에 따른 최적화 방법들

문제 유형	목적함수 / 문제 형태	대표적인 최적화 방법	특징
Linear Programming (LP)	선형 목적함수 + 선형 제약조건	Simplex, Interior-Point	선형 구조를 활용해 효율적으로 해결
Quadratic Programming (QP)	2차 목적함수 + 선형 제약조건	Active-Set, Interior-Point	Hessian이 상수인 Quadratic 문제
Nonlinear Optimization	일반적인 비선형 목적함수	Gradient Descent, Newton, Quasi-Newton	Gradient와 Hessian 등의 미분 정보를 활용
Nonlinear Least Squares (NLS)	${\min }_x\frac{1}{2}\Vert r(x){\Vert }^2$	Gauss-Newton, Levenberg-Marquardt	Least Squares 구조를 이용해 Hessian을 효율적으로 근사
Constrained Optimization	목적함수 + 비선형 제약조건	Lagrange, KKT, SQP, Interior-Point	제약조건을 고려하여 최적해 탐색