이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

국소 최적해와 전역 최적해

솔버가 가장 작은 최솟값을 찾지 못한 이유

일반적으로, 솔버는 국소 최솟값을 반환합니다. 그 결과는 전역 최솟값일 수 있지만 반드시 그렇다는 보장은 없습니다. 이 섹션에서는 솔버가 이렇게 동작하는 이유에 대해 설명하고, 필요한 경우 전역 최솟값을 탐색하는 방법에 대한 권장 사항을 제공합니다.

  • 함수의 국소 최솟값이란 함수 값이 인근 점에서보다는 더 작지만 멀리 있는 점에서보다는 더 클 수 있는 점을 말합니다.

  • 전역 최솟값이란 함수 값이 다른 모든 실현가능점에서보다 작은 점을 말합니다.

일반적으로, Optimization Toolbox™ 솔버는 국소 최적해를 찾습니다. (이 국소 최적해는 전역 최적해가 될 수 있습니다.) 솔버는 시작점의 끌개 유역(basin of attraction)에서 최적해를 찾습니다. 끌개 유역에 대한 자세한 내용은 끌개 유역 항목을 참조하십시오.

이 일반적인 규칙에는 몇 가지 예외가 있습니다.

  • 선형 계획법과 양의 정부호 2차 계획법 문제는 볼록 실현 가능 영역을 갖는 볼록 문제이므로 오직 하나의 끌개 유역만 있습니다. 실제로, 선택하는 옵션에 따라 linprog는 사용자가 제공한 시작점을 무시하기도 하고, quadprog는 시작점을 제공하면 최소화 속도가 빨라질 수 있지만 시작점을 필요로 하지는 않습니다.

  • Global Optimization Toolbox 함수(예: simulannealbnd)는 둘 이상의 끌개 유역을 탐색하려고 시도합니다.

더 작은 최솟값 찾기

전역 최적해가 필요하다면 전역 최적해의 끌개 유역에서 솔버의 초기값을 찾아야 합니다.

전역 최적화를 찾도록 초기값을 설정하는 방법에 대한 권장 사항은 다음과 같습니다.

  • 초기점의 정규 그리드를 사용합니다.

  • 문제의 모든 좌표가 유계인 경우 균등분포에서 추출한 임의의 점을 사용합니다. 일부 성분이 비유계인 경우 정규분포, 지수 분포 또는 기타 확률분포에서 추출한 점을 사용합니다. 전역 최적해의 위치에 대한 정보가 적을수록 확률분포는 넓게 퍼져야 합니다. 예를 들어, 정규분포는 평균에서 3 표준편차를 초과하여 떨어져 있는 값을 추출하는 일이 거의 없지만 코시(Cauchy) 분포(밀도는 1/(π(1 + x2))임)는 상당히 많이 다른 표본을 만듭니다.

  • 유계 좌표, 정규 좌표, 지수 좌표 등 각 좌표에 임의 섭동을 추가한 상태로 동일한 초기점을 사용합니다.

  • Global Optimization Toolbox 라이선스가 있으면 GlobalSearch 솔버 또는 MultiStart 솔버를 사용합니다. 이러한 솔버는 범위 내에서 임의 시작점을 자동으로 생성합니다.

가능한 초기점에 대해 많이 알수록 탐색이 더욱 집중적이고 성공할 확률이 높아집니다.

끌개 유역

목적 함수 f(x)가 매끄러우면 벡터 –∇f(x)f(x)가 가장 빠르게 줄어드는 방향을 향합니다. 최속강하법의 방정식, 즉 다음 방정식은

ddtx(t)=f(x(t)),

t가 커질수록 국소 최솟값으로 이동하는 경로 x(t)를 생성합니다. 일반적으로, 서로 가까운 초기값 x(0)은 동일한 최솟값 점으로 향하는 최속강하법 경로를 제공합니다. 최속강하법의 끌개 유역은 동일한 국소 최솟값에 이르는 초기값의 집합입니다.

다음 그림은 두 개의 1차원 최솟값을 보여줍니다. 이 그림에서는 서로 다른 선 스타일로 다른 끌개 유역을 표시하며 화살표로 최속강하법의 방향을 표시합니다. 이 그림과 그 다음 그림에서 검은색 점은 국소 최솟값을 나타냅니다. 모든 최속강하법 경로는 점 x(0)에서 시작하여 x(0)을 포함하는 끌개 유역의 검은색 점으로 이동합니다.

1차원 유역

다음 그림은 차원이 많아질수록 최속강하법 경로가 더 복잡해질 수 있다는 것을 보여줍니다.

다양한 시작점에서의 최속강하법 경로를 보여주는 하나의 끌개 유역

다음 그림에서는 더욱 복잡한 경로와 끌개 유역을 보여줍니다.

여러 끌개 유역

제약 조건은 하나의 끌개 유역을 여러 조각으로 나눌 수 있습니다. 예를 들어, 다음과 같은 조건으로 y를 최소화한다고 가정하겠습니다.

  • y ≥ |x|

  • y ≥ 5 – 4(x–2)2.

다음 그림에서는 최종점을 갖는 두 개의 끌개 유역을 보여줍니다.

 Figure 생성에 사용된 코드

최속강하법 경로는 제약 조건 경계로 내려가는 직선입니다. 제약 조건 경계에서 최속강하법 경로는 경계를 따라 아래로 이동합니다. 최종점은 초기 x값이 2보다 크거나 작은지에 따라 (0,0)이거나 (11/4,11/4)이 됩니다.