Many engineering problems are formulated as general nonlinear optimization problems which are generally nonconvex and may have multiple local optima.
In this thesis, a new global optimization algorithm is proposed for unconstrained problems which uses a local optimization algorithm and escaping sequence iteratively. Robust algorithms for local optimization are well-developed and readily available for use. But using local optimization algorithm itself, we may be trapped in a local optimum solution. So we need an escape phase from local optimum point. The proposed algorithm is composed of two phases: local optimization phase (LOP) and escape phase (EP). The LOP finds a local optimum, and the EP escapes from that local optimum and finds a new starting point using cutting plane method and global line search. The interaction between LOP and EP continues until termination criterion is satisfied.
The proposed algorithm is successfully applied to a number of general nonlinear unconstrained optimization problems and shows excellent performance in terms of number of function calls compared to the interval branch and bound method. Also it is expected that the proposed algorithm shows much smaller number of function evaluations than stochastic methods, such as, random search, simulated annealing, and genetic algorithm.
많은 공학 문제들은 많은 경우에 볼록 함수가 아니고 많은 국부 최소점을 가지고 있는 일반적인 비선형 최적화문제로 형성되어 진다.
이 논문에서는 국부 최적화 알고리즘과 국부 최적점에서의 탈출을 되풀이 하는 새로운 전역 최적화 알고리즘이 제한 조건이 없는 전역 최적화 문제를 풀기 위해 제안되었다. 국부 최적화 알고리즘은 현재까지 잘 발전되어 왔고 또한 바로 이용이 가능하다. 또한 현재까지의 전역최적화 알고리즘은 목적함수를 부르는 개수가 같은 크기의 문제에 대한 국부최적화 알고리즘에 비해 너무 크다. 그리고, 국부 최적화 알고리즘 자체만 가지고는 우리는 국부 최적점에 빠져서 더 이상의 진행을 하지 못할 것이다. 따라서 국부 최적점으로부터 빠져나오기 위한 탈출의 절차가 필요한 것이다. 제안된 알고리즘은 두 개의 단계로 나눌 수 있는데, 첫 번째가 국부 최적화 단계이고 두 번째가 탈출 단계이다. 탈출 단계에 대한 자세한 논의가 본문에서 나올것이다. 제안된 알고리즘은 탈출을 위해서 절단 평면 방법과 전역 라인 서치(global line search) 방법을 이용하였다.
제안된 알고리즘은 일반적인 비선형의 제한 조건이 없는 전역최적화 문제에 성공적으로 적용이 되었고 또한 목적함수를 부르는 횟수에서 구간 분지 상한 방법(branch and bound method)에 비해 훌륭한 결과를 보여주었다. 또한 여러 다른 통계적 전역 최적화 방법보다 훨씬 더 작은 목적함수의 부름 개수를 줄 것으로 예상되어 진다.
