In this dissertation, Hessian approximation algorithms are proposed to estimate the search direction of the quasi-Newton methods for solving optimization problems of continuous parameters. The proposed algorithms are quite different from other well-known quasi-Newton methods such as Symmetric Rank-One(SRO), Davidon-Fletcher-Powell(DFP) and Broyden-Fletcher-Goldfarb-Shanno(BFGS) in that the Hessian matrix is not calculated from the gradient information but from the function values directly. The proposed algorithms are designed for a class of hybrid methods that combine evolutionary search with the gradient-based methods of quasi-Newton type. The function values calculated for the evolutionary search are used for estimation of the Hessian matrix (or its inverse) as well as the gradient vector. The Hessian matrix is recursively corrected so that its curvature matches the curvature information found from the fitness values. For this purpose, two different update methods, one called batch update and the other sequential update, are proposed. Furthermore, convergence properties of repetitive application of the proposed update schemes are investigated, both analytically and numerically. Since the estimation process of the Hessian matrix is independent of that of the gradient vector, more reliable Hessian estimation with a sparse population is possible compared with the previous methods based upon the classical quasi-Newton methods. Numerical experiments show that the proposed algorithms are very competitive with regards to state-of-the-art evolutionary algorithms for continuous optimization problems.
본 논문에서는 연속 파라미터를 가지는 수치 최적화 문제를 해결하는데 필요한 의사-뉴튼 방법의 탐색 방향을 추정하기 위한 새로운 헤시안 추정 알고리즘을 제안하였다. 새로운 알고리즘은 기존에 잘 알려진 의사-뉴튼 방법들 즉, SRO, DFP, 그리고 BFGS에서 사용하는 헤시안 추정 방법인 구배 정보로부터 헤시안을 추정하는 방법과는 매우 다른 방법을 사용하고 있는데, 필요한 헤시안을 함수 값들로부터 직접적으로 추정하는 방법을 사용한다. 제안된 알고리즘은 의사-뉴튼 방식의 구배 정보를 이용하는 국소 탐색기와 진화 전략을 이용한 전역 탐색기를 결합한 하이브리드 수치최적화 기법에 효과적으로 적용하기 위해 개발되었다. 하이브리드 최적화 기법의 전역 탐색기로 사용되는 진화 전략의 진행 과정에서 얻어진 함수 값으로부터 곡률 정보를 구할 수 있으며, 이를 이용해서 헤시안 행렬 (또는 헤시안 역행렬)을 순환적으로 추정해 나갈 수 있다. 본 연구에서는 헤시안 행렬의 추정을 위한 두 가지 방법으로 순차적 추정 방법과 일괄 추정 방법을 제시하고 있는데, 이는 이제까지 하이브리드 최적화 기법에 적용되었던 전통적인 의사-뉴튼 방법에 기초한 헤시안 추정 방법보다 안정적인 방법이다. 이것은 헤시안 행렬의 추정 과정이 구배 벡터의 추정과 독립적으로 이루어지기 때문이며, 이와 같은 이유로 하이브리드 수치최적화 기법에 적용할 때, 진화기반 헤시안 추정 알고리즘이 기존의 의사-뉴튼 방법을 사용하는 것보다 더 적합한 방법이 된다. 제안된 헤시안 추정 알고리즘을 사용한 하이브리드 최적화 기법을 이용하여 다양한 수치 최적화 문제들을 해결할 수 있으며, 최근에 개발된 다른 최적화 기법과의 실험적, 통계적 비교 분석을 통해 얻어진 결과를 바탕으로, 제안된 알고리즘이 경쟁력 있는 우수한 방법임을 확인할 수 있다.
