집밖은 위험해

감쇄 뉴턴 방법 알고리즘 damped newton

- 경사 하강 방향으로 조금씩 이동

- 감쇄 뉴턴 알고리즘 의사 코드

LMD-Newton 방법

- Levenberg-Marquardt Type Damped Newton Method

- 최소자에서 먼 곳에서는 경사 하강법, 최소자 근처에서는 속도가 빠른 뉴턴 방법을 사용.

 -> 경사 하강법과 뉴턴 방법의 혼합

- 위 기본 감쇄 뉴턴 탐색 방법에서 이득 비율 rho에 따라 mu가 갱신됨.

 -> rho가 1에 가까우면 mu는 줄이고, rho가 멀면 mu를 키움

태일러 급수를 이용해 2차까지 정리하면

L(h)를 최소화 하는 h가 뉴턴 방법의 해

뉴턴 방법 정리

- 아래의 이차 함수에서 A가 양 확정 행렬이면 반복 1회만에 최저점에 도달

 * 양 확정 행렬 positive definite matrix은 역행렬이 존재

뉴턴 방법으로 최저점 찾기

경사하강 방법과 뉴턴 방법의 차이

- 경사 하강 방법에서 여러번 반복이 수행됨

- 뉴턴 방법에는 1번만에 최소자에 도착

* 뉴턴 방법은 시작 점에 따라서 잘 수렴되지 않을 수 있음.

테일러 전개에를 통한 함수 근사화 정리

- 이차 형태(이차 함수)를 반복하여 최소자를 구함

2차 형태 정리

- 집합 S^n은 n x n의 대칭 행렬, f가 컨벡스 함수려면 A는 양 확정행렬이면 됨.

- 최소자는?

경사 하강 방법 gradient descent과 켤래 경사 방법 conjugate gradient의 차이

직선 탐색 알고리즘 line search algorithm

- 하강 방향 벡터 h를 구한 뒤, 하강 뱡향으로 얼마나 이동할지 보폭 크기 step size(alpha)를 결정하는 알고리즘

직선 탐색 알고리즘 예시

- 다음의 식과 초기값이 주어질 때

- 보폭 alpha에 대한 식 구하기

- alpha에 대한 그래프

- alpha = 0.5일때, x1 구하기

- x2에 대한 alpha 구하기

- x2 구하는데 필요한 alpha에 대한 그래프

- alpha = 1/10 일때, x2

=> 정리

직선 탐색 line search의 종류

1. 정확 직선 탐색 exact line search

 - 위 예시 처럼 x + alpha h에서 f(x)의 최소자 계산

2. 완만 직선 탐색 sort line search

 - f(x + alpha h) < f(x)를 만족하는 적당한 alpha를 선택하는 방법

1. 하강 방향

- 경사에 따라 내려가기 위해서 다음을 만족하는 값을 찾아야 함

- alpha가 충분히 작다면 아래와 같이 근사시킬수 있으며 여기서 h는 하강 방향 descent direction

- alpha는 보폭 크기 step size

2. 종료 조건 stopping criteria

- 반복 과정을 종료하기 위해서 다음의 종료 조건 중 선택하여 종료

3. 경사 하강 방법 gradient descent method

- 미분 가능한 함수 f가 초기값 x0에서 최소자 x*를 찾는 과정

- 정리

4. 경사 하강 예제

 최적화의 기본 개념

- 특정 데이터가 주어질때, 이로 부터 필요한 값들을 추출이 필요

 ex. 컴퓨터 비전, 머신러닝

- 목적 함수 objective function or 비용 함수 cost function : 이 값들을 구하기 위한 함수

최적화란?

- 목적 함수를 이용하여 f(x*) <= f(x)인 x*를 찾는 일

목적 함수의 판별 어려움

- 목적 함수로 구한 최소자가 전역 최소자인지, 목적 최소자인지 판별하기 힘듬

최소자를 찾는 방법

- 초기 지점 x0를 설정하고 초기 지점 보다 낮은 x1을 반복해서 찾음

- 하강방향 설정 -> 다음 지점 선택 -> 반복

=> 지역 최소자를 찾음

목적함수, 최소자 정리

최적화 방법들

1. 경사 하강법 gradient descent

2. 직선 탐색 line search

3. 황금 분할 탐색 gloden section search

4. 뉴턴 방법

5. 비선형 최소 자승 방법

6. 라그랑주 승수를 이용한 최적화

최소자 minimizer

- 전역 최소자 global minimizer : 함수 f : D -> R이 주어질 때, f(x*) <= f(x)인 x*

- 전역 최솟값 global minimum : 전역에대한 f(x*)

- 지역 최소자 local minimizer : 일부 구간에서 지역 최소값을 구하는 x*

- 지역 최소값 local minimum : 일부 지역에 대한 f(x*)

개구간과 폐구간

- 개구간 open interval : 초과, 미만 -> (a, b) 두 점 a, b를 포함하지 않는 사이 구간

- 폐구간 closed interval : 이상, 이하 -> [a, b] 두 점 a, b를 포함하는 구간 

컨벡스 집합 convex set

- K에 속하는 폐구간 집합

컨벡스 함수 convex function

- 컨벡스 집합 K가 주어질때 함수 f: K -> R이 아래의 조건을 따르는 함수

방향 미분 direction derivative

- 함수 f가 주어질때 하나의 방향에 대한 미분

다변수 함수에서의 평균값 정리

n차원 벡터공간에서 1차원 벡터공간에 대한 다변수 함수의 2차 테일러 급수 정리

- 연속적인 테일러 전개가 가능

m차원 벡터공간에서 n차워 벡터공간으로의 다변수 함수의 테일러 급수 정리

- n -> 1 벡터 공간과 달리 1차 테일러 전개만 가능

레벨 집합 level set

- n차원 벡터공간의 함수 f(x)가 c와 같을때에 대한 x 집합

- 벡터 공간이 2차원인 경우 레벨 집합은 등고선이 됨

곡선함수와 접선 벡터, 그라디언트

- 곡선 함수 alpha는 레벨 집합의 한 원소

- 법선 벡터 tangent vector : t0에서의 곡선 함수의 미분

- 그라디언트 벡터와 법선 벡터의 관계 : 항상 수직임

벡터와 델 연산자의 내적

- 다음과 같이 벡터와 델 연산자가 주어질 때 

- 내적과 내적의 n승은 다음과 같다.

미분의 내적

- 내적의 미분을 정리하면 다음과 같다.

- 아래의 예시의 경우 행렬 형태로 구하면

헤시안 행렬 hessian matrix

기울기 벡터(그라디언트) gradient vector

- 다변수 함수에 각 변수들에 대한 편미분

자코비안 행렬 Jacobian matrix

- 아래와 같이 다변수 함수들이 주어질때

- 다변수 함수들의 변수들에 대한 편미분들의 모음 -> 자코비안