직선 탐색 문서 원본 보기

{{위키데이터 속성 추적}}
{{구별|순차 검색 알고리즘}}
'''직선 탐색'''(Line search, 라인 서치) 전략은 [[수학적 최적화|최적화]]에서 [[손실 함수|목적 함수]] f: Rn → R의 국소 최소 x<sup>*</sup>를 찾는 두 가지 기본 반복 접근 방식 중 하나이다. 다른 접근 방식은 [[신뢰 영역]]이다.

직선 탐색 접근 방식은 먼저 목적 함수 f가 감소되는 하강 방향을 찾은 다음 x가 해당 방향을 따라 얼마나 멀리 이동해야 하는지를 결정하는 단계 크기를 계산한다. 하강 방향은 [[경사 하강법]]이나 [[준뉴턴법]] 등 다양한 방법으로 계산할 수 있다. 단계 크기는 정확하거나 부정확하게 결정될 수 있다.

== 알고리즘 ==
=== 직접 탐색 방법 ===
이 방법에서는 최소값을 먼저 괄호로 묶어야 하므로 알고리즘은 찾는 최소값이 두 지점 사이에 있도록 지점 x1과 x2를 식별해야 한다. 그런 다음 두 개의 내부 점 x3 및 x4에서 f(x)를 계산하고 두 개의 외부 점 중 가장 낮은 함수 값을 갖는 x3 및 x4의 점에 인접하지 않은 점을 거부하여 간격을 나눈다. 후속 단계에서는 하나의 추가 내부 점만 계산하면 된다. 간격을 나누는 다양한 방법 중에서 [[황금분할 탐색]]은 탐색 진행 방법에 관계없이 간격 비율이 유지되므로 특히 간단하고 효과적이다.

:<math>\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)</math>
여기서
: <math>\varphi=\frac{1}{2}(1+\sqrt 5) \approx 1.618</math>

== 같이 보기 ==
* [[할선법]]

{{토막글}}


[[분류:최적화 알고리즘 및 방법]]