In this thesis, a new convex cut function method is proposed to handle the constraints that appear in the twice-differentiable general NLP problems. For unconstrained minimization problem, the difference of convex underestimator which is proposed by Chang et al. is used. Both the underestimator and the convex cut function are constructed based on the interval Hessian matrix of objective function and constraints, respectively. For univariate global optimization with non-convex constraints, the proposed convex cut function method shows good performance to several tests. To accelerate the convergence of multi-dimensional global optimization with non-convex constraints, the branch-and-bound algorithm is hybridized so that both the underestimator and the convex cut function get tighter as the iteration proceeds. In the proposed method, the difference of convex underestimator which is proposed by Chang et al. is used to obtain lower bound and the convex cut function serves the basis of discarding rule for an infeasible subregion after branching. The cutting region by the convex cut function is memorized as hyperellipsoid. However, the convergence rate decreases as the number of cutting regions increases. To accelerate the convergence rate, an inclusion relation between two hyperellipsoids should be applied in order to reduce the number of cutting regions. We show that the two-hyperellipsoid inclusion relation is determined by maximizing a quadratic function over a sphere, which is a special case of a trust region subproblem. The proposed method is applied to ten univariate constrained NLP test problems, twelve general NLP test problems and five engineering design problems. The proposed method is proven to have a finite ε-convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering method, the index branch-and-bound algorithm, which uses the Lipschitz constant for univariate constrained NLP test problems. And numerical results for multi-dimensional problems show that the proposed method converges in a finite calculation time and produces accurate solutions.
본 연구에서는 두 번 미분 가능한 함수로 이루어진 일반적인 비선형계획법 문제에서 비선형 제약조건을 처리하는 새로운 방법으로 볼록절단함수를 제안하였다. 제약조건이 없는 최적화 문제에는 장外가 제안한 볼록한 함수의 차를 이용한 과소평가함수를 사용하였다. 과소평가함수와 볼록절단함수는 각각 목적함수와 제약조건의 구간 Hessian 행렬을 이용하여 생성된다. 단변수 비선형 제약 최적화 문제의 경우, 제안된 볼록절단함수가 다양한 문제에 좋은 성능을 보이는 것을 확인할 수 있었다. 다변수 비선형 제약 최적화 문제의 경우, 수렴 속도를 향상시키기 위해서 곁가지경계 방법을 볼록절단함수와 혼성하여 사용하였다. 그 이유는 과소평가함수와 볼록절단함수를 프로그램이 반복되는 동안 좀 더 목적함수와 제약조건에 더 근접하게 하기 위해서이다. 제안된 방법에서는 장外가 제안한 볼록한 함수의 차를 이용한 과소평가함수를 이용하여 하한값을 찾고, 볼록절단함수를 이용하여 타당영역을 벗어난 부영역을 제거한다.
볼록절단함수에 의해서 생성된 절단영역은 타원체로 저장된다. 수렴 속도가 절단영역의 증가에 따라서 느려지기 때문에 수렴 속도를 빠르게 하기위해서는 두개의 타원체 간의 포함관계를 규명하여 절단영역의 수를 줄일 필요가 있다. 본 연구에서는 두 타원체 간의 포함관계가 신뢰영역 부문제의 특별한 구조인 구를 제약조건으로 하는 2차 함수의 최대화 문제로 결정되는 것을 규명하였다. 제안된 방법론은 10개의 단변수 비선형 제약 최적화 문제와 12개의 일반적인 제약 최적화 문제 그리고 5개의 공학설계 문제에 적용되었다. 각 문제의 적용 결과 전역최적점으로 유한 수렴성을 보이는 것을 확인하였다. 단변수 문제의 경우 덮게방법의 하나로 Lipschitz 상수를 사용한 인덱스 곁가지방법론과 비교하여 우수한 성능을 보이는 것을 확인하였다. 다변수문제의 경우 유한 수렴성은 물론 정확한 해를 구하는 것을 확인하였다.
