[최적화] Optimization problems

Reference

• Optimization problems?
• slide

Optimization problems?

최적화 문제(optimization problems)란 여러 개의 선택 가능한 후보 중에서 최적의 해(optimial value)를 찾는 것 또는 최적해의 근접한 값을 찾는 문제를 일컫습니다.

머신러닝 분야에서는 이를 비용 함수(cost function)를 최소화 또는 최대화 시키는 모델의 파라미터(parameter)를 구하는 것을 의미하고, 이를 최적화 문제로 정의합니다.

Mathematical optimization problems

최적화 문제는 수식적으로 아래와 같이 표현합니다.

$min_{x \in D}$ $f(x)$
subject to
$g_i(x) \le 0, i = 1, ... m$
$h_j(x) = 0, j = 1, ...r$

• $x \in R^n$ is the optimization variable
• $f: R^n \rightarrow R$ is the objective or cost function
• $g_i: R^n \rightarrow R, i=1, ..., m$ are the inequality constraint functions
• $h_i: R^n \rightarrow R, j=1,...,r$ are the equality constraint functions

위의 제약조건을 모두 만족하는 정의역(feasible domain)에서 objective function f를 최소로 만드는 벡터 $x$를 $x^*$로 표시하고 이를 optimal soultion이라 부릅니다.

여기서 제약조건의 경우 2가지로 구분된다고 합니다.

1. Explicit constarints
   말 그대로 optimization problem에 직접적으로 명시된 제약조건을 뜻한다. 위 [Fig1]에서 함수 $g_i$와 $h_i$로 표현된 제약조건이 이에 해당됩니다.
   참고로 explicit constraint가 없는 문제를 unconstrained problem이라고 부릅니다.
2. Implicit constraints
   Optimization problem에 직접적으로 명시되지 않는 제약조건을 말합니다. 이는 Objective function과 모든 constraint function들의 정의역에 대한 교집합입니다.

Note: $dom(f)$는 함수 $f$의 정의역을 의미하니다.

implicit constraint와 explicit constraint의 예시가 있습니다.

최적화 문제가

$minimize$ $log(x)$

로 주어졌을 때

여기서 objective function인 log 함수의 정의역이 $x>0$이므로 $x>0$이 이 문제에서의 implicit constraint가 됩니다.

이 문제를 explicit constraint가 포함된 형태의 최적화 문제로 표현한다면

$minimize$ $log(x)$ $subject$ $to$ $x>0$

가 됩니다.