국소 최적해와 전역 최적해

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

일반적으로, 솔버는 국소 최솟값(또는 최적해)을 반환합니다. 그 결과는 전역 최솟값(또는 최적해)일 수 있지만 반드시 그렇다는 보장은 없습니다.

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

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

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

다음은 이 일반적인 규칙의 몇 가지 예외입니다.

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

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

더 작은 최솟값 찾기

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

전역 최솟값을 찾기 위해 다음과 같은 방법으로 초기값을 설정할 수 있습니다.

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

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

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

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

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

끌개 유역

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

$$\frac{d}{dt}x(t)=-\nabla f(x(t)),$$

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

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

1차원 유역

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

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

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

여러 끌개 유역

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

y ≥ |x|

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

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

 Figure 생성에 사용된 코드

myabs = @(x) abs(x);
mycurve = @(x) 5 - 4.*(x-2).^2;
myline = @(x) max(myabs(x),mycurve(x));
mybrdr = @(x) 1 + heaviside(x-2);
myarea = @(x,y) heaviside(y - myline(x)).*mybrdr(x);
% myarea = 0 where infeasible, 1 when x < 2, 2 when x > 2
marinv = @(x,y) 1./myarea(x,y); % removes the infeasible region

plot(0,0,'k.','MarkerSize',25,'LineWidth',2);
hold on
grid on
plot(11/4,11/4,'k.','MarkerSize',25,'LineWidth',2);
fplot(mycurve,'k',[.9 3],'LineWidth',2)
fplot(myline,[-2 5],'k','LineWidth',2)
fsurf(marinv,[-2 5 -1,6],'EdgeColor','none','FaceAlpha',0.5)
colormap jet

명령줄에 plottools를 입력하여 화살표 그리기 툴을 사용하여 화살표를 추가합니다.

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

관련 항목

• 결과 향상시키기