fminsearch 알고리즘

fminsearch는 Lagarias et al. [57]에 설명된 것처럼 넬더-미드 단체 알고리즘을 사용합니다. 이 알고리즘은 n차원 벡터 x에 대해 n + 1개의 점으로 구성된 단체를 사용합니다. 이 알고리즘은 먼저 초기 추측값 x₀을 기준으로 단체를 만듭니다. 즉, x₀에 각 성분 x₀(i)의 5%를 더한 다음, 이러한 n개의 벡터를 x₀과 함께 단체의 요소로 사용합니다. (이 알고리즘은 x₀(i) = 0인 경우 0.00025를 성분 i로 사용합니다.) 그런 다음, 이 알고리즘은 다음 절차에 따라 단체를 반복해서 수정합니다.

참고

각 단계의 설명 끝에는 fminsearch 반복 표시의 키워드가 굵게 표시되어 있습니다.

1. x(i)가 현재 단체 i = 1,...,n + 1의 점 목록을 표시하도록 합니다.

2. 단체의 점을 가장 낮은 함수 값 f(x(1))에서 가장 높은 함수 값 f(x(n + 1)) 순서로 정렬합니다. 반복의 각 스텝에서, 알고리즘은 현재 가장 부적합한 점 x(n + 1)을 버리고 다른 점을 단체에 포함시킵니다. [또는, 아래 7단계의 경우 f(x(1))보다 큰 값을 갖는 n개의 점을 모두 바꿉니다.]

3. 반사된 점을 생성합니다.

   r = 2m – x(n + 1),

   여기서

   m = Σx(i)/n, i = 1...n,

   그런 다음 f(r)을 계산합니다.

4. f(x(1)) ≤ f(r) < f(x(n))이면 r을 받고 이 반복을 종료합니다. 반사(Reflect)

5. f(r) < f(x(1))이면 확장 점 s를 계산합니다.

   s = m + 2(m – x(n + 1)),

   그런 다음 f(s)를 계산합니다.

   1. f(s) < f(r)이면 s를 받고 반복을 중지합니다. 확장(Expand)

   2. 그렇지 않으면 r을 받고 반복을 중지합니다. 반사(Reflect)

6. f(r) ≥ f(x(n))이면 m과 x(n + 1) 또는 r 간에(어느 쪽의 목적 함수 값이 더 낮은지에 따라 결정) 수축(Contraction)을 수행합니다.

   1. f(r) < f(x(n + 1))이면(즉, r이 x(n + 1)보다 더 좋은 값이면) 다음을 계산합니다.

      c = m + (r – m)/2

      그런 다음 f(c)를 계산합니다. f(c) < f(r)이면 c를 받고 반복을 중지합니다. 외부로 수축(Contract outside)

      그렇지 않으면 7단계(축소(Shrink))를 계속 진행합니다.

   2. f(r) ≥ f(x(n + 1))이면 다음을 계산합니다.

      cc = m + (x(n + 1) – m)/2

      그런 다음 f(cc)를 계산합니다. f(cc) < f(x(n + 1))이면 cc를 받고 반복을 중지합니다. 내부로 수축(Contract inside)

      그렇지 않으면 7단계(축소(Shrink))를 계속 진행합니다.

7. n개 점을 계산합니다.

   v(i) = x(1) + (x(i) – x(1))/2

   그런 다음 f(v(i)), i = 2,...,n + 1을 계산합니다. 다음 반복 시 단체는 x(1), v(2),...,v(n + 1)이 됩니다. 축소(Shrink)

다음 그림은 fminsearch가 단계에서 계산할 수 있는 점과, 각각의 가능한 새 단체를 보여줍니다. 원래 단체는 굵은 윤곽선으로 표시되어 있습니다. 중지 조건을 충족할 때까지 반복이 계속됩니다.

참고 항목

fminsearch

관련 항목

• 제약 조건이 없는 비선형 최적화 알고리즘