지수 함수가 관련된 경우 전역 최적화
관련된 비선형 함수가 다음과 같은 형식 일 때 MINLP 문제의 전역 최적을 결정하는 방법이 있는지 궁금합니다. $Z = Y e^{- \alpha X}$, 어디 $Y \ge 0$ 과 $X \ge 0$.
그러한 접근 방식을 설명하는 문서가 있습니까? 이러한 기능에 악용 될 수있는 특성이 있습니까?
로그를 사용하여 함수를 다음과 같이 다시 작성할 수 있습니다. $\log(Z) = \log(Y) - \alpha X$,하지만 나는 아무것도이기는 것 같지 않습니다.
답변
이것은 볼록하지 않은 전역 최적화 문제입니다. 이를 해결하는 최첨단 방법은 인수 가능한 이완을 사용하는 것입니다.
여기서 핵심 통찰력은 $e^{-\alpha X}$ 볼록합니다 (당신의 $\alpha$ 긍정적 임).
방법론은 다음과 같습니다.
- 새로운 보조 변수 도입 $w=e^{-\alpha X}$
- 당신은 이제 $Z=Yw$, 및 $w=e^{-\alpha X}$
- 두 제약이 모두 볼록하지 않기 때문에 각각을 두 개의 부등식으로 분할합니다.
$Z\leq Yw, -Z\leq -Yw$
$ w\leq e^{-\alpha X}, -w\leq -e^{-\alpha X}$
첫 번째 부등식 세트는 McCormick 이완을 사용하여 볼록 화 될 수 있습니다 .
두 번째 부등식 세트는 각각 볼록하고 오목합니다. 볼록 부등식은 외부 근사를 사용하여 완화 할 수 있고 오목 부등식은 시컨트를 사용하여 완화 할 수 있습니다.
그런 다음 완화 된 문제를 분기 및 바인딩 알고리즘에 연결하면 2 차적으로 수렴됩니다.
이 방법론은 $Z,Y,X$.
또는이 모든 작업을 자동으로 수행하는 글로벌 솔버에 연결할 수 있습니다. Couenne 은 오픈 소스 선택이며 학업 / 학생 인 경우 SCIP 또는 자체 Octeract Engine 을 무료로 사용할 수도 있습니다 .
연속 이완이 볼록하다고 가정하면 지수 원뿔과 함께 원추 최적화를 사용할 수 있습니다. Mosek 모델링 요리 책은 세부 사항을 가지고있다.
당연히 Mosek 은 이러한 문제의 혼합 정수 버전을 해결할 수 있습니다.
JP Vielma 및 J Huchette의 다음 기사 (OR에서 제공 예정)에서 질문에 대한 부분 답변을 찾을 수 있습니다. https://arxiv.org/abs/1708.00050
이 논문에서 저자는 다중 초평면의 분리를 통해 목적에서 하나 또는 두 개의 변수의 비선형 함수를 근사하는 문제를 고려합니다. 그런 다음 결과 MIP를 범용 혼합 정수 솔버에 전달할 수 있습니다.
이 기사에는 도움이 될 수있는 다른 출처에 대한 인용이 포함되어 있습니다.