[Math] Optimization Problem 의 종류

Optimization Problem의 종류

1. Minimization Problem vs. Maximization Problem

 

일반적인 최적화 문제는 최소화 문제로 공식화될 수 있음.

 

이는 다음과 같이 표현됨:

$$
\underset{\boldsymbol{\omega}}{\min} f(\boldsymbol{\omega})
$$

이는 다음의 제약 조건에 종속됨:

• $m$개의 부등식 제약 조건: $g_i(\boldsymbol{\omega}) \le 0$
• $p$개의 등식 제약 조건: $h_j(\boldsymbol{\omega}) = 0$

여기서:

• $f(\textbf{x})$: $\textbf{x}$의 실값 함수 (또는 스칼라 필드)
• $\textbf{x}$: 입력 열 벡터 $\textbf{x} = (x_0, x_1, \dots, x_n)^T$, 스칼라일 수도 있음
• $\textbf{g(x)}, \textbf{h(x)}$: 벡터 값 함수

함수의 매핑 관계는 다음과 같음:

$$
f: \mathbb{R}^n \rightarrow \mathbb{R} \\
\textbf{g}: \mathbb{R}^n \rightarrow \mathbb{R}^m \\
\textbf{h}: \mathbb{R}^n \rightarrow \mathbb{R}^p
$$

최대화 문제의 경우, 해당 함수에 $-1$을 곱하면 최소화 문제가 됨.
이는 최소화 문제만 고려해도 충분함을 의미함.

최적화 문제는 함수 $f(\textbf{x}), \textbf{g(x)}$ 및 $\textbf{h(x)}$의 속성에 따라 분류됨.

 

2023.07.06 - [.../Math] - [Math] Lagrangian from Standard Form using Indicator Function

[Math] Lagrangian from Standard Form using Indicator Function

---

2. 입력에 의한 분류

2-1. Univariate Optimization Problem (단변수 최적화 문제)

$\textbf{x}$는 1x1 벡터로, scalar(스칼라)임.

convex optimization등을 처음 배울 때 주로 나오는 예제들이 이 경우임.

---

2-2. Multivariate or Multidimensional Optimization Problem (다변수 또는 다차원 최적화 문제)

$\textbf{x}$는 vector(벡터)임.
고차원 objective functions(목적 함수)의 경우, $n$이 클수록 최적화 문제를 해결하는 것이 더 어렵고 계산 비용이 많이 듦.

---

3. Linearity에 의한 분류

3-1. Linear Programming Problem (선형 계획 문제)

Objective function(목적 함수)과 constraints(제약 조건)가 모두 linear(선형)일 경우,

이 최적화 문제는 선형 최적화 문제 또는 linear programming(선형 계획) 문제라고 함.

 

2023.07.08 - [.../Math] - [Math] Linear Programming and Quadratic Programming

[Math] Linear Programming and Quadratic Programming

---

3-2. Nonlinear Programming Problem (비선형 계획 문제)

Objective function(목적 함수)이나 constraints(제약 조건) 중 하나라도 비선형인 경우,

이는 비선형 최적화 문제 또는 nonlinear programming problem(비선형 계획 문제)임.

---

4. Constraints 유무에 의한 분류

Unconstrained Problem and Constrained Problem (비제약 문제와 제약 문제)

제약 조건(constraints)에 따라 최적화의 중요한 하위 클래스는 비제약 문제와 선형 및 비선형 제약 조건을 가진 문제들임.

또한, 등식 제약 조건과 부등식 제약 조건을 처리하는 데는 서로 다른 접근 방식이 필요함.

---

같이 읽어보면 좋은 자료들

https://www.amazon.com/Numerical-Python-Scientific-Applications-Matplotlib/dp/1484242459

 

 

---