Many global optimization techniques employ the branch-and-bound algorithm as their framework of refining search regions. So called αBB is one such example which utilizes twice-differentiable convex underestimator during the branch-and-bound procedure. The underestimator of αBB may be too conservative with the increase of the degree of complexity of functions.
In this research, a new underestimator is presented to make tight underestimator and accelerate convergence of αBB global optimization iteration procedure. The new tight underestimator has quadratic form which has the minimum points at the center of search regions. A new quadratic underestimator is derived and the technique to generate the quadratic underestimator is described. The branch-and-bound algorithm is used as the framework. And the quadratic underestimator is applied to solve the unconstrained global optimization. The number of iterations and overall computational time are obtained with the quadratic underestimator and the underestimator of αBB. The results with the quadratic underestimator are compared with the underestimator of αBB. Relative computational time is addressed. From the final result, the new tight underestimator exhibits better convergence for higher dimensional problems.
많은 전역 최적화 방법이 구간을 줄여나가는 분지 상한 방법(branch-and-bound algorithm)을 사용한다. 그런 방법 중에서 αBB알고리즘은 두 번 미분 가능한 함수에 대한 오목한 과소평가 함수를 만들어 분지 상한 방법을 수행한다. αBB의 과소평가 함수는 원래 함수의 복잡성이 증가하면서 더 밀접한(tight) 함수를 얻기 어려워진다.
본 논문에서는 αBB알고리즘에서보다 더 밀접한 과소평가 함수를 만들어 수렴시간을 가속시키는 방법이 연구되어졌다. 새롭게 제시되는 과소평가 함수는 2차 형태를 가지고 있는데, 탐색공간의 가운데에서 최소 함수값을 가지고 있다. 2차 과소평가 함수가 αBB알고리즘의 과소평가 함수로부터 유도되어져 있고, 이 함수를 만드는 방법이 기술되어져 있다. 이렇게 만들어진 과소평가 함수를 이용해서 제약조건이 없는 전역 최적화 문제를 풀었다. 반복 계산 회수와 문제를 풀기위해 필요한 계산 시간을 αBB알고리즘의 과소평가 함수와 제안된 과소평가함수를 이용해서 각각 그 결과를 얻었다. 이 결과를 이용해서 상대 계산 시간을 얻었다. 이로부터 높은 차원의 문제에 더 좋은 효과가 있음을 확인 하였다.
