최적화가 무엇인지, 최적화의 기초에 대해서 공부한다. (with 데이터사이언스스쿨)

최적화란?

최적화 문제

: 함수 $f(x)$의 값을 최대 혹은 최소화하는 변수 $x$의 값, $x^*$을 찾는 것
최대화 문제도 $-f(x)$로 고칠 수 있으니, 최소화 문제만 고려한다.

그리드 서치 (Grid search)

: 가능한 $x$의 값을 많이 넣어서 찾는 방법. but 계산량이 상당히 크다.

수치적 최적화 (Numerical optimization)

: 함수 위치가 최적점이 될 때까지 가능한 한 적은 횟수만큼 $x$의 위치를 욺기는 방법

• 이를 위해 다음 2가지의 알고리즘이 필요한데
  • 현재 위치가 최적점인지 판단하는 알고리즘
  • 다음에 시도할 위치를 찾는 알고리즘

기울기 필요조건

: 어떤 독립 변수 값 $x^*$이 최소점이려면, 일단은 기울기가 0이여야한다.
모든 변수에 대한 편미분 값이 0, $\triangledown f = 0 \ or \ g = 0$

최대경사법

: 단순히 현재 위치에서 기울기 값만을 이용하여 다음 위치를 결정하는 방법.
$x_{k+1} = x_k - \mu\triangledown f(x_k)$, $\mu$는 step size

• step size의 크기를 적절히 설정하는 것이 중요하다.
  보통은 경험적으로 얻는 값 or 특정한 알고리즘에 따라서 설정.
• 진동(oscillation) 현상이 발생하는 경우, 수렴하기까지 시간이 오래 걸릴 수 있음.
• 진동 현상을 없앨 수 있는 방법
  • 2차 도함수, 헤시안 행렬을 이용
  • 모멘텀 방법 : 진행방향으로 계속 진행하도록 성분(모멘텀) 추가, 인공신경망 등에서 선호

전역 최적화 문제 / 컨벡스(convex) 문제

• 전역 최적화 문제 : 복수의 local minimum을 가지고 있는 경우, 반드시 global minimum에 도달한다는 보장이 없다.
  이때의 결과는 초기 추정값, 알고리즘, 파라미터($\mu$)등에 의존.
• 컨벡스 문제 : 2차 도함수의 값이 항상 0 이상이 되는 영역에서만 정의된 최적화 문제.
  컨벡스 문제에서는 항상 global minimum이 존재한다

제한조건이 있는 최적화 문제

등식 제한조건이 있는 최적화 문제

$x^* = arg\ min_x \ f(x)$
$x \in R^N$
$g_j(x) = 0 \ (j=1,...,M)$

라그랑주 승수법

: 목적함수를 $h(x,h) = f(x) + \sum_{j=1}^M \lambda_j g_j(x)$로 설정
$\triangledown h = 0$이 $N+M$개의 연립방정식이 되어 풀 수 있게 된다.

라그랑주 승수의 의미

: $\lambda_i =0$이면, 원래의 문제와 같아져 최적화 해의 위치도 같다.

부등식 제한조건이 있는 최적화 문제

$x^* = arg\ min_x \ f(x)$
$x \in R^N$
$g_j(x) \leq 0 \ \ (j=1,...,M)$
(만약, 부등식이 반대방향이라면 -1을 곱하여 바꾼다)

KKT 조건

1) 모든 독립 변수에 대한 미분값이 0이다.
2) 모든 라그랑주 승수 $\lambda_1,..., \lambda_N$가 0이거나 그 미분값이 0이다.
3) 라그랑주 승수는 음수가 아니여야한다. (설명어려움, 암기)

• 2)가 의미하는 바는, 제한조건이 쓸모없음 or 등식인 제한조건 이다.

선형계획법 / 이차계획법

선형계획법 문제

: 제한 조건을 가지는 선형 모형의 값을 최소화 하는 문제

$arg \ min_x \ c^Tx$
$Ax = b$
$x \ge 0$ (변수값이 음수가 아니어야하는 부등식 제한조건)

• 위의 형태가 기본형, 정규형은 부등식 조건($Ax \le b$) 허용.

이차계획법 문제

: 제한 조건을 가지는 일반화된 이차형식(quadratic form)의 값을 최소화 하는 문제; QP 문제

$arg \ min_x \ 1/2x^TQx + c^Tx$
$Ax = b$
$x \ge 0$ (변수값이 음수가 아니어야하는 부등식 제한조건)

• RSS를 최소화 하는 예측 모형에 추가적인 제한조건이 있으면, 이차계획법 문제가 된다.