결정론적 글로벌 최적화

결정론적 글로벌 최적화는 수치 최적화의 한 분야로서, 보고된 솔루션이 사전 정의된 허용 오차 내에서 실제로 글로벌 솔루션이라는 이론적 보증을 제공하는 동시에 최적화 문제의 글로벌 솔루션을 찾는 데 초점을 맞춘다. "결정론적 글로벌 최적화"라는 용어는 일반적으로 완전하거나 엄격한(아래 참조) 최적화 방법을 가리킨다. 엄격한 방법들은 한정된 시간 안에 전지구적 최적으로 수렴된다. 결정론적 글로벌 최적화 방법은 일반적으로 글로벌 솔루션을 찾아야 하는 필요성(즉, 수학적 모델에 의해 설명되는 유일한 자연 발생 상태가 최적화 문제의 글로벌 최소인 경우), 실현 가능한 솔루션을 찾기가 극히 어려운 경우 또는 사용자가 b를 찾기를 원하는 경우 사용된다.문제에 대한 가능한 해결책을 제시하다

개요

Neumaier는^[1] 글로벌 최적화 방법을 최적화에 접근하는 엄격함의 정도에 따라 다음과 같이 4가지 범주로 분류했다.

• 불완전한 방법은 검색을 위해 직관적 접근법을 사용하지만 검색이 로컬 최소값으로 고착될 경우 안전장치가 없다.
• 무증상적으로 완전한 방법은 확실성 또는 최소한 무한정 오래 실행되도록 허용될 경우 확률 1로 글로벌 최소치에 도달하지만, 글로벌 최소화가 발견된 시기를 알 수 있는 수단이 없다.
• 완전한 방법은 정확한 계산과 무한정 긴 실행 시간을 가정하고, 한정된 시간 후에 대략적인 글로벌 최소화가 (규정된 허용 오차 범위 내에서) 발견되었음을 알고 있다.
• 엄격한 방법은 허용오차를 초과할 수 있는 거의 소멸된 경우를 제외하고 반올림 오류가 있는 경우에도 확실하고 주어진 허용오차 내에서 글로벌 최소치에 도달한다.

결정론적 글로벌 최적화 방법은 일반적으로 마지막 두 가지 범주에 속한다. 모든 종속성 또한 엄격하게 코딩되어야 하기 때문에 엄격한 소프트웨어를 만드는 것은 매우 어렵다는 점에 유의하십시오.

결정론적 글로벌 최적화 방법에는 공간의 영역에 걸쳐 함수 값을 엄격하게 구속하는 방법이 필요하다. 이 맥락에서 결정론적 방법과 비결정론적 방법의 주요한 차이는 전자가 솔루션 공간의 영역에 걸쳐 계산을 수행하는 반면 후자는 단일 점에 대해 계산을 수행한다는 것이다. 이것은 특정한 기능적 형태(예: McCormick Relaxation^[2])를 이용하거나 보다 일반적인 기능적 형태와 함께 작업하기 위해 간격 분석을 사용하여 수행된다. 어떤 경우든 경계가 필요한데, 이것이 블랙박스 코드로 작업할 때 결정론적 글로벌 최적화 방법이 기능 한계를 반환하도록 명시적으로 작성되지 않는 한 엄격한 결과를 줄 수 없는 이유다. 이러한 이유로, 결과 함수 값이나 파생상품이 (스칼라가 아닌) 구간을 산출하도록 모든 연산자에 과부하하는 것이 간단하기 때문에, 결정론적 글로벌 최적화의 문제는 계산 그래프를 사용하여 나타내는 것이 일반적이다.

결정론적 글로벌 최적화 문제의 종류

선형 프로그래밍 문제(LP)

선형 프로그래밍 문제는 모든 실제 문제에 있어서 매우 바람직한 공식이다. 그 이유는 인테리어 포인트 알고리즘의 상승으로 매우 큰 문제(수십만, 심지어 수백만 개의 변수를 발생시키는 것)를 글로벌 최적성으로 효율적으로 해결할 수 있기 때문이다. 선형 프로그래밍 최적화 문제는 엄격히 결정론적 글로벌 최적화 범주에 속한다.

혼합 정수기 선형 프로그래밍 문제(MILP)

선형 프로그래밍 문제와 마찬가지로, MILP는 의사결정 모델을 해결할 때 매우 중요하다. 이러한 유형의 복잡한 문제를 해결하기 위한 효율적인 알고리즘이 알려져 있으며, CPLEX와 같은 해결사 형태로 이용 가능하다.

비선형 프로그래밍 문제(NLP)

비선형 프로그래밍 문제는 결정론적 글로벌 최적화에 있어 매우 도전적이다. 현대적 해결사가 합리적인 시간에 처리할 것으로 기대할 수 있는 규모의 순서는 대략 100에서 수백 개의 비선형 변수들이다. 이 글의 작성 당시, 결정론적 LP와 NLP 프로그래밍의 복잡성 차이를 설명하는 NLP의 결정론적 해결책을 위한 병렬 해결사는 존재하지 않는다.

혼합 정수기 비선형 프로그래밍 문제(MINLP)

그들의 NLP 상대들보다 훨씬 더 어려운 것은 결정적으로 MINLP 문제를 해결하는 것이 매우 어려울 수 있다. 정수 절단과 같은 기법이나 정수 변수에 대한 문제 분기(결정적으로 해결될 수 있는 NLP 하위 문제를 만드는 것)가 일반적으로 사용된다.

제로 오더 방식

제로오더 방식은 제로오더 구간 산술을 활용하는 방식으로 구성된다.^[3] 대표적인 예가 구간 이분법이다.

1차 방법

1차 방법은 구간 구배 또는 구간 경사 등 1차 정보를 사용하는 방법으로 구성된다.

2차 방법

2차 방법은 2차 정보, 일반적으로 헤시안 행렬 간격에서 파생된 고유값 한계를 사용한다. 일반 유형의 문제를 처리하기 위한 가장 일반적인 2차 방법론 중 하나는 αβ3 알고리즘이다.

결정론적 글로벌 최적화 해결사

• 안티고네: 비선형 방정식의 연속 / 정수 전역 최적화를 위한 알고리즘).^[4] 그것은 독점 소프트웨어로, GAMS 모델링 플랫폼을 통해 이용할 수 있다.^[5]

• 바론: 바론은 AIMMS, 앰프 및 GAMS 모델링 언어와 NEOS 서버에서 사용할 수 있다.^[6] 그것은 독점 소프트웨어다.
• 쿠엔느: 비선형추정을 위한 볼록스 오버 앤 언더 엔벨롭스(Couenne)는 오픈소스 도서관이다.
• EAGO: Easy-Advanced Global Optimization(EAGO)은 줄리아(프로그래밍 언어)의 오픈소스 해결사다. 그것은 코네티컷 대학교에 의해 개발되었다.^[10]
• LINDO(Linear, Interactive 및 이산 옵티마이저)에는 글로벌 최적화 기능이 포함되어 있다.^[11]
• MAINGo: McCormick 기반 MAIGo(Mixed-integer 비선형 글로벌 최적화 알고리즘)는 MPI와 openMP 병렬화가 가능한 C++ 패키지로 Eclipse Public License - v 2.0에 따라^[13] 오픈 소스를 제공한다.
• 옥테락트 엔진은 병렬화 기능을 갖춘 독점 해결사다. 옥테락트(Octract)에서 개발·허가하고 있다.
• SCIP: SCIP는 여러 가지 중에서 혼합 정수 비선형 프로그래밍(MINLP)을 해결하는 최적화 솔버의 오픈 소스 제품군이다.

참조