Powered by GitBook

kb11_최적화 알고리즘

테스트

최적화 알고리즘

최적화 방법론

Linear programming (LP)
quadratic programming (QP)
second-order cone programming (SOCP)
semi-definite programming (SDP)

내리막 경사법(미분 기반) 최적화 알고리즘은 지역해 문제점 존재

해결책 : 시뮬레이티드 어닐링, 유전 알고리즘

최적화 알고리즘은 3가지 결정 사항

초기해 설정: 탐색의 시작점 선정
멈춤 조건: 해가 만족스러운지 판단 기준
해 갱신: 현재 해를 다음 해로 이동하는 방법

해 종류

최적(Optimal Solution)해
부 최적(sub-optimal Solution)해

1. 내리막 경사법

1.1 분석적 방법

목적함수를 미분한것이 0이 되는 값을 찾는다.

eg.

$J(\theta) = -2\theta^2 +20\theta -43$
$\frac{\partial J}{\partial \theta}= -4\theta +20 = 0$
$\hat\theta = 5$

$y = x^n \rightarrow y\prime = n\cdot x^{n-1}$
$J(x) = (4-2.1x_1^2+x_1^4/3)x_1^2+x_1x_2+(-4+4x_2^2)x_2^2$

1.2 수치적 방법 (eg.내리막 경사법)

분석적 방법은 한정된 상황에서만 가능, 대부분 반복적 계산을 통해 해 도출

대표적 방법 = 내리막 경사법, 오르막 경사법

$\theta_{t+1} = \theta- \rho\frac{\partial J}{\partial\theta}|\theta_t$

$\rho$ = 학습률

내리막 경사법은 대표적 욕심 알고리즘 이다. 즉, 과거/미래를 고려 하지 않고 현재 상황만 고려하여 지역해에 빠질 위험이 있다.

1.3 조건부 최적화

어떤 조건이 주어 지고 그 조건이 만족하는 상황에서의 최적화 문제

A. 조건식을 목적 함수에 대입 하는 방법

eg. $J(\theta)= x^2 +2y^2$ , 조건 = $2x+y =1$

조건식을 목적함수에 대입 : $J(\theta) = x^2 + 2(1-2x)^2=90x^2 -8x +2$ 미분 : $\frac{\partial J}{\partial x}=18x-8=0$

간단한 조건일때만 적용 가능한 방법

B. 등식 조건부 최적화 문제 : f(x) = a

라그랑제 승수 활용 하여 문제 해결 가능

Step 1. 라그랑제 함수 정의

$L(\theta, \lambda) = J(\theta) - \sum^n_{i=1}\lambda_i f_i(\theta)$

Step 2. 라그랑제 함수를 로 미분한 식 풀기

$\frac{\partial L}{\partial \theta_i}=0, i=1,....,k$ $\frac{\partial L}{\partial \lambda_i}=0, i=1,....,n$

[예제]

eg. $J(\theta)= x^2 +2y^2$ , 조건 = $2x+y =1$

Step 1. 라그랑제 함수 정의

$L(\theta, \lambda_1) = (x^2 +2y^2)- \lambda(2x+y -1)$

Step 2. 라그랑제 함수를 로 미분한 식 풀기

$\theta$ 로 미분한 식을 0으로 둠

$\frac{\partial L}{\partial x}=2x-2\lambda_1=0$
$\frac{\partial L}{\partial y}=4y-\lambda_1=0$

$\lambda$ 로 미분한 식을 0으로 둠

$\frac{\partial L}{\partial \lambda_1}=-(2x+y-1)=0$

C. 부등식 조건부 최적화 문제:f(x) a

Karush-Kuhn-Tucker(KKT) 3 조건 사용

조건 1 : 라그랑제 함수를 미분한식이 0이 되어야 한다. $\frac{\partial L(\theta, \lambda)}{\partial \theta}=0$
조건 2 : 모든 라그랑제 승수가 0보다 크거나 같아야 한다. $\lambda_i \geq 0, i=1,...,n$
조건 3 : 모든 조건식에 대해 $\lambda =0$ 이거나 $f_i(\theta)=0$ 이 되어야 한다. $\lambda_i f_i(\theta)=0, i=1,...,n$

조건	수식
기울기(Gradient)조건	$\frac{\partial L(X)}{\partial \theta}=0$
실행가능성(Feasibility)조건	$g_i(x) \leq 0$
직교성(Orthogonality)조건	$\lambda_i g_i(x) = 0$
양수(Nonegarivity)조건	$\lambda_i \geq 0$

f(x)=조건함수, g(x)= 제약함수

[예제]

eg. $J(\theta) = x^2 +2y^2$ , 조건 $f_1(\theta)= 2x+y -1 \geq 0$

Step 1. 라그랑제 함수 정의

$L(\theta, \lambda_1) = (x^2 +2y^2)- \lambda(2x+y -1)$

Step 2. KKT 조건 정의

조건 1x : $\frac{\partial L}{\partial x}=2x-2\lambda_1 = 0$
조건 1y : $\frac{\partial L}{\partial y}=4y-\lambda_1 = 0$
조건 2 : $\lambda_i \geq 0$
조건 3 : $\lambda_1(2x+y-1)=0$

D. 볼록성질을 만족하는 조건부 최적화 문제 : wolfe Dual로 변형 가능

볼록성질 : 목적 함수가 2차 항만을 가지고 있음, 지역해가 없는 경우

조건

$\frac{\partial L(\theta, \lambda)}{\partial \theta} = 0$
$\lambda_i \geq 0, i = 1...,N$

변형

$L(\theta,\lambda)=J(\theta)-\sum_{i=1,N} \lambda_if_i(\theta)$

결론

부등식 조건이 등식 조건으로 바뀜
최소화 문제가 최대화 문제로 바뀜

참고 : 패턴인식개론, 한빛미디어, 491p

2. 시뮬레이티드 어닐링

기본틀은 경사 하강법과 같음
조건에 따라 상승도 가능하다는 점이 경사 하강법과 다른점
- 조건 : 온도 t (t가 크면 하강/상승을 비슷한 비율로, t가 작으면 하강에 초점
장점 : 상승도 가능하므로 지역해의 단점 해결 가능

참고 : AI Study_Simulated Annealing

3. 유전 알고리즘

추후 별도로 정리

4. Matrix Inversion

5. EM

6. Newton's Method

[추천]: Machine Learning 스터디 (7) Convex Optimization

조건부 최대화 문제
- 목적 함수가 2차 함수, 제약 조건이 1차 부등식이나 등식으로 된 것
비선형 계획법이라고도 한다

cf. QP 2차 방정식을 사용하고, LP는 1차 방정식으로 설정된 것을 사용한다.

Convex문제는 선의 어떤 두점을 잡아서 이를 직선으로 연결하면 선의 모든 점도 곡선의 위에 존재 하게 된다??

[참고] Linear Complementarity Problem

w = Ax + b 가 주어 졌을때

x $\geq$ 0 : x가 0이 되어서 w = b의 형태 문제
w $\geq$ 0 : w가 0이 되어서 Ax + b = 0의 형태 문제
x'w = 0

Linear Programming 문제의 경우 간단한 수식 이항을 통해 LCP로 바꿀수 있고 Quadratic Programming 문제의 경우 수식의 변형을 통해 LCP로 바꿀수 있다고 합니다.

results matching ""

No results matching ""