직선 탐색

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 1차원 직선 탐색
3. 다차원 직선 탐색
4. 국소 최소값 문제 해결
5. 알고리즘 (황금 분할 탐색)
6. 직선 탐색의 활용 예시 (경사 하강법)
참조

1. 개요

직선 탐색은 함수의 최솟값을 찾기 위한 최적화 방법으로, 1차원 및 다차원 함수에 적용될 수 있다. 1차원 직선 탐색은 함수의 단봉성을 활용하여 최소값을 괄호로 묶고, 구간을 좁혀가며 최소점을 찾아낸다. 이 과정에서 영차, 1차, 곡선 맞춤 방법 등이 사용되며, 특히 황금 분할 탐색은 간격 비율을 일정하게 유지하여 효율적이다. 다차원 직선 탐색은 하강 방향을 결정하고, 그 방향으로의 이동 거리를 계산하여 최솟값을 찾는다. 경사 하강법과 같은 최적화 알고리즘에서 직선 탐색은 최적의 단계 크기를 결정하는 데 활용되며, 국소 최솟값 문제를 해결하기 위해 시뮬레이티드 어닐링과 결합될 수 있다.

더 읽어볼만한 페이지

최적화 알고리즘 및 방법 - 신뢰 영역
신뢰 영역 방법은 비선형 최적화에서 함수의 모델을 신뢰할 수 있는 영역 내에서만 사용하여 최적화를 수행하는 방법으로, 다양한 분야에서 전역 최적해를 찾기 위한 도구로 활용된다.
최적화 알고리즘 및 방법 - 확률적 계획법
확률적 계획법은 불확실한 상황에서 최적의 의사 결정을 내리기 위한 수학적 방법론으로, 다양한 확률적 프로그래밍 기법을 포함하며, 생물학, 경제, 금융 공학 등 여러 분야에 응용된다.
토막글 틀에 과도한 변수를 사용한 문서 - 전향
전향은 종교적 개종이나 노선 변경을 의미하며, 근대 이후 정치적 이념 변화를 지칭하는 용어로 확장되어 개인의 신념 변화, 정치적 압력 등 다양한 요인으로 발생하며, 사회주의·공산주의로부터의 전향, 전향 문학, 냉전 시대 이후의 전향 현상 등을 폭넓게 논의한다.
토막글 틀에 과도한 변수를 사용한 문서 - 포토마스크
포토마스크는 반도체, 디스플레이, 인쇄 회로 기판 제조 시 웨이퍼에 회로 패턴을 전사하는 마스크로, 기술 발전을 거듭하며 융용 실리카 기판과 금속 흡수막을 사용하고 위상 천이 마스크, EUV 마스크 등의 고급 기술이 개발되어 반도체 미세화에 기여하고 있지만, 높은 제작 비용과 기술적 어려움은 해결해야 할 과제이다.
토론 이름공간 토막글 - 전향
전향은 종교적 개종이나 노선 변경을 의미하며, 근대 이후 정치적 이념 변화를 지칭하는 용어로 확장되어 개인의 신념 변화, 정치적 압력 등 다양한 요인으로 발생하며, 사회주의·공산주의로부터의 전향, 전향 문학, 냉전 시대 이후의 전향 현상 등을 폭넓게 논의한다.
토론 이름공간 토막글 - 포토마스크
포토마스크는 반도체, 디스플레이, 인쇄 회로 기판 제조 시 웨이퍼에 회로 패턴을 전사하는 마스크로, 기술 발전을 거듭하며 융용 실리카 기판과 금속 흡수막을 사용하고 위상 천이 마스크, EUV 마스크 등의 고급 기술이 개발되어 반도체 미세화에 기여하고 있지만, 높은 제작 비용과 기술적 어려움은 해결해야 할 과제이다.

직선 탐색
개요
유형	최적화 알고리즘
분야	수학 최적화
관련	경사 하강법, 準 뉴턴 방법
상세 내용
목적	최적의 스텝 크기 α 찾기
방법	구간 방법 (예: 황금 분할 탐색) 미분 기반 방법 (예: 뉴턴 방법)
고려 사항	함수의 형태 계산 비용 정확도 요구 사항
활용
적용	다양한 최적화 문제
장점	비교적 간단하고 구현 용이
단점	전역 최적해 보장 X 스텝 크기 선택에 민감

2. 1차원 직선 탐색

함수 ''f''가 1차원 함수, $f:\mathbb R\to\mathbb R$ 이고, 단봉성을 갖는다고 가정한다. 즉, 주어진 구간 [''a'',''z''] 안에 정확히 하나의 지역 최소점 ''x''*을 갖는다. 이는 ''f''가 [a,x*] 구간에서 엄격하게 감소하고 [x*,''z''] 구간에서 엄격하게 증가함을 의미한다. 이 경우 (근사) 최소점을 찾는 방법에는 여러 가지가 있다.^[1]

2. 1. 영차 방법 (Zero-order methods)

영차 방법은 도함수가 아닌 함수 평가(즉, 값 오라클)만 사용한다.^[1]

삼분 검색: ''a''<''b''<''c''<''z''가 되도록 두 점 ''b'', ''c''를 선택한다. f(''b'')≤f(''c'')이면 x*는 [''a'',''c''] 안에 있어야 하고, f(''b'')≥f(''c'')이면 x*는 [''b'',''z''] 안에 있어야 한다. 두 경우 모두 검색 간격을 더 작은 간격으로 바꿀 수 있다. ''b'',''c''를 간격 중앙에 아주 가깝게 선택하면 각 반복마다 간격이 ~1/2로 줄어들지만, 반복마다 두 번의 함수 평가가 필요하다. 따라서 이 방법은 $\sqrt{0.5}\approx 0.71$ 의 비율로 선형 수렴한다. a, b, c, z의 분할이 세 개의 동일한 길이 간격을 갖도록 b, c를 선택하면 각 반복마다 간격이 2/3으로 줄어들므로 이 방법은 $\sqrt{2/3}\approx 0.82$ 의 비율로 선형 수렴한다.
피보나치 검색: 이는 점 ''b'',''c''가 피보나치 수열을 기반으로 선택되는 삼분 검색의 변형이다. 각 반복에서 다른 점이 이미 이전 간격의 끝점이었으므로 한 번의 함수 평가만 필요하다. 따라서 이 방법은 $1/ \varphi \approx 0.618$ 의 비율로 선형 수렴한다.
황금 분할 검색: 이는 점 ''b'',''c''가 황금비를 기반으로 선택되는 변형이다. 마찬가지로 각 반복에서 한 번의 함수 평가만 필요하며 이 방법은 $1/ \varphi \approx 0.618$ 의 비율로 선형 수렴한다. 이 비율은 영차 방법 중에서 최적이다.

영차 방법은 매우 일반적이며 미분 가능성이나 연속성조차 가정하지 않는다.

2. 2. 1차 방법 (First-order methods)

1차 방법은 ''f''가 연속적으로 미분 가능하고, ''f''뿐만 아니라 그 도함수도 평가할 수 있다고 가정한다.^[1]

이분법은 구간의 중앙인 ''c''에서 ''f''의 도함수를 계산한다. 즉, f'(''c'')=0이면 이것이 최소점이고, f'(''c'')>0이면 최소점은 [''a'',''c'']에 있어야 하며, f'(''c'')<0이면 최소점은 [''c'',''z'']에 있어야 한다. 이 방법은 0.5의 속도로 선형 수렴한다.

2. 3. 곡선 맞춤 방법 (Curve-fitting methods)

곡선 맞춤 방법은 ''f''가 유한 차수의 다항식과 같은 해석적 형태를 갖는다고 가정하여 초선형 수렴을 달성하려고 시도한다. 각 반복에서 ''f''의 값(그리고 가능하면 그 도함수)을 알고 있는 일련의 "작업 점"이 있다. 이러한 점들을 기반으로, 알려진 값에 맞는 다항식을 계산하고, 그 최소값을 해석적으로 찾을 수 있다. 최소점은 새로운 작업 점이 되고, 다음 반복으로 진행한다.^[1]

뉴턴 방법은 곡선이 ''f''의 1차 및 2차 도함수를 사용하여 구성된 2차 다항식인 곡선 맞춤 방법의 특별한 경우이다. 이 방법이 비퇴화 국소 최소점(= 양의 2차 도함수)에 충분히 가깝게 시작되면, 2차 수렴을 갖는다.
가위치법은 함수를 2차 다항식에 맞추는 또 다른 방법이지만, 동일한 점에서의 1차 및 2차 도함수 대신 두 점에서의 1차 도함수를 사용한다. 이 방법이 비퇴화 국소 최소점에 충분히 가깝게 시작되면, $\varphi \approx 1.618$ 차수의 초선형 수렴을 갖는다.
''3차 맞춤''은 마지막 두 점에서의 함수 값과 그 도함수를 모두 사용하여 3차 다항식에 맞춘다. 이 방법이 비퇴화 국소 최소점에 충분히 가깝게 시작되면, 2차 수렴을 갖는다.

곡선 맞춤 방법은 국소 최소점에 충분히 가깝게 시작될 때 초선형 수렴을 갖지만, 그렇지 않으면 발산할 수 있다. ''보호된 곡선 맞춤 방법''은 곡선 맞춤 방법과 병렬로 선형 수렴 방법을 동시에 실행한다. 각 반복에서 곡선 맞춤 방법으로 찾은 점이 보호 방법으로 유지되는 간격에 충분히 가까운지 확인한다. 그렇지 않은 경우, 보호 방법은 다음 반복값을 계산하는 데 사용된다.^[1]

3. 다차원 직선 탐색

일반적으로 다차원 목적 함수 $f:\mathbb R^n\to\mathbb R$ 가 주어진다. 직선 탐색 방법은 먼저 목적 함수 $f$ 가 감소하는 하강 방향을 찾고, 그 다음 $\mathbf{x}$ 가 해당 방향으로 얼마나 이동해야 하는지를 결정하는 단계 크기를 계산한다. 하강 방향은 경사 하강법 또는 준 뉴턴 방법 등 다양한 방법으로 계산할 수 있다. 단계 크기는 정확하게 또는 부정확하게 결정될 수 있다.

다음은 직선 탐색을 사용하는 경사 방법의 예시이다.

# 반복 카운터 $k=0$ 으로 설정하고 최솟값에 대한 초기 추측 $\mathbf{x}_0$ 를 만든다. 허용 오차 $\epsilon$ 를 선택한다.

# 다음을 반복한다:

## 하강 방향 $\mathbf{p}_k$ 를 계산한다.

## 단계 크기가 주어진 하강 방향의 함수 값을 나타내는 일차원 함수 $h(\alpha_k)=f(\mathbf{x}_k+\alpha_k\mathbf{p}_k)$ 를 정의한다.

## $\alpha_k\in\mathbb R_+$ 에서 $h$ 를 최소화하는 $\displaystyle \alpha_k$ 를 찾는다.

## $\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k$ 및 $k=k+1$ 로 업데이트한다.

# $\|\nabla f(\mathbf{x}_{k+1})\|<\epsilon$ 까지 반복한다.

직선 탐색 단계 (2.3)에서 알고리즘은 $h'(\alpha_k)=0$ 을 풀어 ''h''를 '정확하게' 최소화하거나, 위에 언급된 일차원 직선 탐색 방법 중 하나를 사용하여 '근사적으로' 최소화할 수 있다. 또한 최적값을 반드시 근사하지 않는 ''h''의 충분한 감소를 요구함으로써 '느슨하게' 해결할 수도 있다. 전자의 예는 켤레 기울기법이다. 후자는 부정확한 직선 탐색이라고 하며, 백트래킹법과 같은 여러 가지 방법으로 수행하거나 Wolfe 조건을 사용할 수 있다.

4. 국소 최소값 문제 해결

직선 탐색은 다른 최적화 방법과 마찬가지로 국소 최솟값을 뛰어넘을 수 있도록 모의 담금질 (시뮬레이티드 어닐링)과 결합될 수 있다.^[1]^[2]

5. 알고리즘 (황금 분할 탐색)

이 방법은 최소값을 포함하는 구간 [x₁, x₂]에서 시작하여, 황금비를 이용하여 구간을 나누고 함수 값을 비교하여 구간을 좁혀나가는 방식이다. 최소값을 찾는 알고리즘은 우선 최소값이 두 지점 사이에 있도록 x₁과 x₂를 정해야 한다. 그런 다음 두 개의 내부 점 x₃ 및 x₄에서 f(x)를 계산하고, 두 개의 외부 점 중 함수 값이 더 낮은 쪽에 인접하지 않은 점을 제외하여 간격을 나눈다.^[2]

이후 단계에서는 하나의 추가 내부 점만 계산하면 된다. 간격을 나누는 다양한 방법 중에서 황금 분할 탐색은 탐색 진행 방법에 관계없이 간격 비율이 일정하게 유지되므로 특히 단순하고 효과적이다.^[2]

: $\frac{1}{\varphi}(x_2-x_1)=x_4-x_1=x_2-x_3=\varphi(x_2-x_4)=\varphi(x_3-x_1)=\varphi^2(x_4-x_3)$

여기서

: $\varphi=\frac{1}{2}(1+\sqrt 5) \approx 1.618$

6. 직선 탐색의 활용 예시 (경사 하강법)

경사 하강법에서 직선 탐색을 활용하는 방법은 다음과 같다. 먼저, 목적 함수 $f$ 가 감소하는 하강 방향을 찾는다. 그 후, $\mathbf{x}$ 가 해당 방향으로 얼마나 이동해야 하는지를 결정하는 단계 크기를 계산한다. 하강 방향은 경사 하강법 또는 준 뉴턴 방법 등 다양한 방법으로 계산할 수 있다.

다음은 직선 탐색을 사용하는 경사 하강법의 예시이다.

# 반복 카운터 $k=0$ 으로 설정하고, 초깃값 $\mathbf{x}_0$ 를 설정한다. 허용 오차 $\epsilon$ 를 선택한다.

# 다음을 반복한다:

## 하강 방향 $\mathbf{p}_k$ 를 계산한다.

## 단계 크기가 주어진 하강 방향의 함수 값을 나타내는 일차원 함수 $h(\alpha_k)=f(\mathbf{x}_k+\alpha_k\mathbf{p}_k)$ 를 정의한다.

## $\alpha_k\in\mathbb R_+$ 에서 $h$ 를 최소화하는 $\displaystyle \alpha_k$ 를 찾는다.

## $\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k$ 및 $k=k+1$ 을 업데이트한다.

# $\|\nabla f(\mathbf{x}_{k+1})\|<\epsilon$ 까지 반복한다.

위 단계에서 $h'(\alpha_k)=0$ 을 풀어 ''h''를 '정확하게' 최소화하거나, 일차원 직선 탐색 방법을 사용하여 '근사적으로' 최소화할 수 있다. 또는 ''h''의 충분한 감소를 요구함으로써 '느슨하게' 해결할 수도 있다. 전자의 예시는 켤레 기울기법이다. 후자는 부정확한 직선 탐색이라고 하며, 역추적 직선 탐색이나 Wolfe 조건을 사용하는 방법 등이 있다.

참조

_[1] 웹사이트 Optimization III: Convex Optimization http://www2.isye.gat[...] 2023
_[2] 서적 Non-Linear optimisation Techniques Oliver & Boyd

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com