다항최적화문제에 대한 계층 방법의 성능 분석

Abstract

다항최적화문제는 목적함수와 제약식이 모두 미지수가 n개인 실수 다항식으로 구성된 최적화문제이다. 이 논문은 가능해 영역이 컴팩트(compact)하고 내부점이 있는 다면체인 다항최적화문제에 초점을 맞추었다. 이 경우에는 다양한 양의 정리(Positivstellensatz)를 바탕으로 한 계층 해법이 최적값에 수렴한다는 것을 보일 수 있다. 이 논문에서는 이 중 한델만(Handelman) 계층을 대표적인 조합최적화문제에 적용했을 때의 성능을 연구하였다. 이를 위해 먼저, 여러 계층 해법의 원리와 해법의 다항성을 정리하였다. 그리고 각 계층을 적용시켰을 때의 성능을 검토하였다.

이 후 최대절단면문제를 n-차원 큐브 위에서 2차 다항식을 최대화시키는 것으로 묘사한 수리모형에 한델만 계층을 적용하였다. 그 결과 한델만 계층의 랭크는 그래프가 이분그래프인 경우에는 2, 홀수 회로인 경우에는 3, 완전그래프인 경우에는 n임을 증명하였다. 그리고 t < n인 경우 t차 한델만 계층이 출력하는 목적함수값이 최적값의 n/t배를 넘지 않는다는 것을 보였다. 이 오차 상한과 이분그래프에서의 랭크에 대한 결과는 가중치가 있는 경우에도 성립한다. 또한 선형화기법(RLT)과 한델만 계층이 서로 쌍대관계에 있음을 관찰하였다.

마지막으로 최대안정집합문제를 n-차원 큐브 위에서 2차 다항식을 최대화시키는 것으로 묘사한 수리모형에 한델만 계층을 적용하였다. 그 결과 한델만 계층의 랭크는 그래프가 이분그래프인 경우에는 2, 홀수 회로인 경우에는 3, 완전그래프인 경우에는 n임을 증명하였다. 그리고 t < n인 경우 t차 한델만 계층이 출력하는 목적함수값이 최적값의 n/t배를 넘지 않는다는 것을 보였다. 그리고 완전그래프에서는 정확하게 최적값의 n/t배를 출력한다는 것을 보였다. 그래서 이 오차 상한은 최선(`tight'의 의역)이다. 즉, 최대안정집합문제에 대한 t차 한델만 계층의 오차 분석은 더 이상 개선할 수 없다.