07. 문제 정식화 — 변수, 목적함수, 제약, feasible region

// CORE 1/7 — decision variables, objective function, constraints, feasible region

최적화 문제는 알고리즘으로 시작하지 않습니다. 먼저 문제를 정확히 써야 합니다. 정식화가 잘못되면 빠른 알고리즘은 잘못된 답에 더 빨리 도착할 뿐입니다.

표준 형태

가장 기본적인 최적화 문제는 다음처럼 씁니다.

\begin{aligned} \min_x\quad & f(x)\\ \text{subject to}\quad & g_i(x)\le 0,\quad i=1,\dots,m,\\ & h_j(x)=0,\quad j=1,\dots,p. \end{aligned}

이 식 하나에 네 가지 구성요소가 들어 있습니다.

decision variables는 우리가 직접 고를 수 있는 값입니다. 보통 $x$ 로 씁니다.

예시:

좋은 변수는 “바꿀 수 있는 것”이어야 합니다. 날씨나 재료 물성처럼 직접 고를 수 없는 값은 변수보다 parameter나 uncertainty로 두는 것이 자연스럽습니다.

objective function은 무엇을 최소화하거나 최대화할지 정의합니다.

f(x):\mathbb{R}^n\to\mathbb{R}.

최적화 알고리즘은 scalar objective를 비교해야 하므로, 여러 성능 지표가 있으면 하나의 숫자로 합쳐야 합니다.

예시:

f(x)=\text{cost}(x)+\lambda\,\text{error}(x).

여기서 $\lambda$ 는 비용과 오차의 trade-off를 조정합니다.

constraints는 반드시 만족해야 하는 조건입니다.

부등식 제약:

g_i(x)\le 0.

등식 제약:

h_j(x)=0.

box constraint처럼 변수 범위를 직접 제한할 수도 있습니다.

l\le x\le u.

제약은 “좋으면 좋은 것”이 아니라 “어기면 안 되는 것”입니다. 목적함수와 제약을 섞으면 문제의 의미가 바뀝니다.

feasible region은 모든 제약을 만족하는 후보들의 집합입니다.

\mathcal{F}=\{x\mid g_i(x)\le 0,\ h_j(x)=0\}.

최적화는 결국 $\mathcal{F}$ 안에서 $f(x)$ 가 가장 좋은 점을 찾는 일입니다.

x^\ast\in\arg\min_{x\in\mathcal{F}}f(x).

데이터 $(a_i,y_i)$ 가 있을 때 선형모델 $a_i^\top x$ 를 맞추는 문제는 다음과 같습니다.

\min_x \frac{1}{2}\sum_{i=1}^{n}(a_i^\top x-y_i)^2.

regularization을 넣으면 objective가 바뀝니다.

\min_x \frac{1}{2}\|Ax-y\|_2^2+\lambda\|x\|_2^2.