파생 모델 없는 최적화

파생 모델 없는 최적화는 수학적 최적화에 관한 분야로서, 고전적 의미에서 파생 모델 정보를 사용하여 최적의 해결책을 찾지 않는다.때때로 목적함수 f의 파생상품에 대한 정보를 사용할 수 없거나, 신뢰할 수 없거나, 얻기 비실용적이다.예를 들어, f는 평가하기에 원활하지 않거나 시간이 많이 소요되거나 어떤 면에서 소음이 있을 수 있으므로 파생상품에 의존하거나 유한한 차이를 통해 파생상품에 근사치를 하는 방법은 거의 쓸모가 없다.그러한 상황에서 최적의 지점을 찾는 문제를 파생상품 없는 최적화라고 하며, 파생상품이나 유한차이를 사용하지 않는 알고리즘을 파생상품 없는 알고리즘이라고 한다.^[1]

소개

The problem to be solved is to numerically optimize an objective function ${\displaystyle f\colon A\to \mathbb {R} }$ for some set ${\displaystyle A}$ (usually ${\displaystyle A\subset \mathbb {R} ^{n}}$), i.e. find ${\displaystyle x_{0}\in A}$ such that without loss of generality ${\displaystyle }$${\displaystyle f}$${\displaystyle }$( ${\displaystyle {x\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$) ${\displaystyle \le }$ f${\displaystyle }$( ${\displaystyle x}$) $\$ f ( x ) {\$displaystyle$ f$(x_{$0})\leq f$(x)}$ 모든$$ $x{\displaystyle }$ $∈$ A {\displaystyle $x\in A}$.

해당되는 경우, 공통적인 접근방식은 객관적 기능 지형에서 국부적 힐 클라이밍에 의한 매개변수 추정을 반복적으로 개선하는 것이다.파생 모델 기반 알고리즘은 좋은 검색 방향을 찾기 위해$$ $f{\displaystyle }$ ${\displaystyle f}$의 파생 정보를 사용한다. 예를 들어 구배는 가장 가파른 상승 방향을 제공하기 때문이다.파생 모델 기반 최적화는 연속 영역 매끄러운 단일 모델 문제에 대한 국부적 최적화를 찾는데 효율적이다.그러나 그들은 예를 들어 문제가 생길 수 있다.${\displaystyle A}$이(가) 연결되지$$ 않거나(혼합) 정수가 되는 $경우{\displaystyle }$ 또는 f ${\displaystyle f}$이(가) 평가 비용이 많이 들거나 부드럽지 않거나 소음이 심하여 파생상품의 (숫자 근사치)가 유용한 정보를 제공하지 않는 경우.약간 다른 문제는 $f{\displaystyle }$ ${\displaystyle f}$이(가) 다중 모달일 때인데, 이 경우 현지 파생상품 기반 방법은 국부적 최적만 줄 뿐 글로벌 최적화를 놓칠 수 있다.

파생 모델이 없는 최적화에서는 f ${\displaystyle f$의 기능 값만 사용하여 이러한 과제를 해결하기 위해 다양한 방법을 채택하지만 파생 모델은 채택되지 않는다.이러한 방법들 중 일부는 최적성을 발견한다는 것을 증명할 수 있지만, 일부는 볼록 최적화에 비해 일반적으로 문제를 해결하기가 더 어렵기 때문에 오히려 메타휴리스틱하다.이러한 사람들에게, 야망은 오히려 충분한 자원이 주어질 수 있는 거의 최적일 수 있는 "좋은" 매개변수 값을 효율적으로 찾는 것이지만, 일반적으로 최적성 보장은 주어질 수 있다.도전이 다양해 보통 모든 종류의 문제에 하나의 알고리즘을 사용할 수 없다는 점을 명심해야 한다.

알고리즘

주목할 만한 파생 모델 없는 최적화 알고리즘에는 다음이 포함된다.

• 베이시안 최적화
• 좌표 강하 및 적응 좌표 강하
• 뻐꾸기 수색
• 완료
• 진화 전략, 자연 진화 전략(CMA-ES, xNES, SNES)
• 유전 알고리즘
• MCS 알고리즘
• 넬더-미드 방법
• 입자 군집 최적화
• 패턴 검색
• 무작위 검색(루우스-자콜라 포함)
• 시뮬레이션 어닐링
• 소분법

참고 항목

• 수학적 최적화

참조

외부 링크

• Audet, Charles; Kokkolaras, Michael (2016). "Blackbox and derivative-free optimization: theory, algorithms and applications". Optimization and Engineering. 17: 1–2. doi:10.1007/s11081-016-9307-4.