오목한 함수의 차를 과소평가 함수로 이용한 새로운 전역 최적화 방법

화학공학의 이론과 응용 제8권 제1호 2002년

Theories and Applications of Chem. Eng., 2002, Vol. 8, No. 1

장민호, 박영철, 이태용

한국과학기술원 생명화학공학과

A Novel Global Optimization Algorithm with Difference of Convex Underestimator

Min Ho Chang, Young Cheol Park, and Tai-yong Lee

Department of Chemical & Biomolecular Engineering

Korea Advanced Institute of Science and Technology

373-1, Kusong-dong, Yusung-gu, Taejon, 305-701, Korea

Introduction

The area of global optimization has attracted the interest in chemical engineering in the last decade for three reasons. First, a number of process synthesis, design, control and operation include global optimization problems. Second, the local optimization routines may fail to obtain a feasible solution or are trapped in a local optimum solution. Third, the obtained local optimum solution has quite different physical meaning compared with the global optimum[2].

The global optimization techniques can be classified into stochastic and  deterministic methods. Stochastic methods, such as simulated annealing and genetic algorithm, aim at high probability of finding the global optimum. These methods, however, guarantee neither optimality nor globality of the obtained solution. Deterministic methods, on the other hand, guarantee finite [eqn: epsilon]-convergence and the globality of the obtained solution. Recent interest in rigorous global optimization has resulted in a number of different approaches to solving convex, or non-convex problems[1,3].

In this paper, the proposed method, difference of convex(d.c.) envelope method belongs to the covering method which is one deterministic methods. [eqn: alpha]BB method, one of the most famous covering method, uses a convex envelope to make a lower(upper) bounding function in branch-and-bound algorithm and needs a local optimization procedure to obtain lower(upper) bounding value. The objective of this research is to make an underestimator without using iterative optimizer to find lower(upper) bounding value.

Underestimator

The general unconstrained NLP optimization problem is given by equation (1).

[eqn: min~f( bold { x) } #s.t.~~x_{ i } ^{ L } <= x_{ i } <= x_{ i } ^{ U } `````````````````` FORALL i~~~^{ }]	(1)

where [eqn: f( bold { x) }], objective function for global minimization problem, belongs to [eqn: C^{ 2 }] and [eqn: bold { x }] is a variable vector.

Underestimator in [eqn: bold { alpha }]BB algorithm

In [eqn: alpha]BB algorithm, convex underestimator, [eqn: P( bold { x) }], of any twice differentiable function is given by equation (2).

[eqn: f(bold x ) >= P(bold x )= f(bold x ) + alpha SUM from { i} ( x_i ^L -x_i ) ( x_i ^U -x_i ) = f(bold x ) + Q(bold x )]             (2)

where [eqn: f(bold x )] is a general nonlinear function and belongs to [eqn: C^{ 2 }] which is a set of twice differentiable function,

[eqn: P(bold x )] is a relaxed convex underestimator, and

[eqn: Q(bold x )] is a convexifying quadratic function for [eqn: f( bold { x } )].

Note that [eqn: alpha] is chosen as a non-negative number large enough to make [eqn: P(bold x )] convex[4].

The minimum of the relaxed convex underestimator, [eqn: P( bold { x } )], in [eqn: alpha]BB should be found through iterative local optimization procedure. And in order to guarantee [eqn: epsilon]-convergence of final local optimization results, each of above procedure must satisfy an extremely strict convergence criteria, which is not desirable.

Proposed underestimator

Let's consider a tangential hyper plane of [eqn: P( bold { x } )] represented by [eqn: R( bold { x } )], then [eqn: R( bold { x } )] is a linear underestimator of [eqn: P( bold { x } )].

Then we can establish a new underestimator, [eqn: S( bold { x } )], of original objective function, [eqn: f( bold { x } )], such that

[eqn: S( bold { x } )=R( bold { x } )-Q( bold { x } )#``~`~`~`=f( bold { x } )+ left { R( bold { x } )-P( bold { x } ) right } #`~`~`~` <= f( bold { x } )]                       (3)

The new underestimator, [eqn: S( bold { x } )] is is a d.c., function, since each of [eqn: R( bold { x } )] and [eqn: S( bold { x } )] is convex[2].

Remarks

i) [eqn: R(bold x )] is a polyhedron whose vertices are determined by the intersection of (n+1) tangential and constraint hyperplanes.

ii) The location of vertices of [eqn: S(bold x )] is the same as that of [eqn: R(bold x )].

iii) The global minimum of [eqn: S(bold x )] is located at one of the vertices of [eqn: S(bold x )].

Using these facts, we can easily find the global minimum of [eqn: S( bold { x } )] since the location of the each vertex of [eqn: R( bold { x } )] is obtained by solving simple linear algebras. The relation between objective function, [eqn: f( bold { x } )], convex underestimator, [eqn: P( bold { x } )], linear underestimator of [eqn: P( bold { x } )], [eqn: R( bold { x } )], and proposed d.c. underestimator, [eqn: S( bold { x } )],  is shown by figure 1.

Branch-and-bound algorithm using d.c. underestimator

The proposed algorithm has basic features of branch-and-bound algorithm. The flow chart of general branch-and-bound algorithm is shown figure 2. The branch-and-bound algorithm consists of three rules, bounding rule, selection rule, and branching rule. The d.c. underestimator is used by obtaining lower bounding value of the current subregion for minimization problems. Since the global minimum of [eqn: S( bold x )] is located at one of the vertices of [eqn: S(bold x )], which serves as the lover bound of the global minimum of [eqn: f(bold x )]. The upper bound of the global minimum of [eqn: f(bold x )] can be selected as the minimum value of [eqn: f(bold x )] evaluated at each vertex. The selection rule of this algorithm is to select the subregion which has minimum lower bounding value among active current subregions. The branching rule is to divide the subregion selected by above selection rule into two equal subregions cross the longest relative interval[4].

Implementation results

To illustrate the performance of the proposed algorithm, several global optimization test problems are solved on Intel Pentium III, 866MHz CPU. All test problems whose names, dimension, and shape are provided in table 1 are taken from [5] and [6].

Table 1 Test problems - name, dimension, and shape

Name	Dim.	Ref.	Problem
Beale	2	[5]	[eqn: (1.5-x_{ 1 } +x_{ 1 } x_{ 2 } )^{ 2 } +(2.25-x_{ 1 } +x_{ 2 } ^{ 2 } )^{ 2 } +(2.625-x_{ 1 } +x_{ 1 } x_{ 2 } ^{ 3 } )^{ 2 }]
Fenton	2	[6]	[eqn: { 1 } over { 10 } left { 12+x_{ 1 } ^{ 2 } + { 1+x_{ 2 } ^{ 2 } } over { x_{ 1 } ^{ 2 } } + { x_{ 1 } ^{ 2 } x_{ 2 } ^{ 2 } +100 } over { (x_{ 1 } x_{ 2 } )^{ 4 } } right }]
Rosenbrock	2	[6]	[eqn: 100 left ( x_{ 2 } -x_{ 1 } ^{ 2 } right ) ^{ 2 } + left ( 1-x_{ 1 } right ) ^{ 2 }]
Hartman3	3	[5]	[eqn: - sum from { i=1 } to { 4 } { c_{ i } rm { exp it { left ( - sum from { j=1 } to { 3 } { A_{ ij } (x_{ j } -P_{ ij } )^{ 2 } } right ) } } }]
Schwefel	3	[5]	[eqn: sum from { i=1 } to { 3 } { (x_{ 1 } -x_{ i } ^{ 2 } )^{ 2 } + left ( x_{ i } -1 right ) ^{ 2 } }]
Powell	4	[5]	[eqn: (x_{ 1 } +10x_{ 2 } )^{ 2 } +5(x_{ 3 } -x_{ 4 } )^{ 2 } +(x_{ 2 } -2x_{ 3 } )^{ 4 } +10(x_{ 1 } -x_{ 4 } )^{ 4 }]
Shekel5	4	[5]	[eqn: - sum from { i=1 } to { 5 } { 1/ sum from { j=1 } to { 4 } { left ( x_{ j } -A_{ ij } right ) ^{ 2 } } }]

And in table 2, the computational results are summarized by comparing between [eqn: alpha]BB algorithm and proposed algorithm. Since the proposed method does not need iterative local optimization procedure, the number of function calls of proposed method is less than that of [eqn: alpha]BB. In the point of view of CPU time, however, the proposed method is not always better than [eqn: alpha]BB.

Table 2 Summary of computational results

Name	Dim.	# of function calls		CPU time(sec.)
		[eqn: alpha]BB	Proposed	[eqn: alpha]BB	Proposed
Beale	2	116592	28558	2.06	0.94
Fenton	2	84756	25297	1.76	0.88
Rosenbrock	2	9302	4097	0.11	0.06
Hartman3	3	2185	644	0.11	0.11
Schwefel	3	4576	1952	0.13	0.17
Powell	4	15669	5092	0.72	1.70
Shekel5	4	51740	16878	2.97	4.01

Conclusions

From the implementation results, the proposed d.c. underestimator is successfully applied to unconstrained NLP minimization problems as the lower bounding function. Compared with   [eqn: alpha]BB algorithm, the propose method requires less number of function calls since it dose not need iterative optimizer to update lower bound of objective function.

화학공학의 이론과 응용 제8권 제1호 2002년

Acknowledgement

This work was also partially supported by the Brain Korea 21 Project.

Reference

[1] Y. Kim and T. Lee "Acceleration of [eqn: alpha]BB Global Optimization Algorithm using Quadratic and Linear Underestimator", Escape-11, 35(2001).

[2] Y. C. Park, M. H. Chang, T. Lee, "Constrained Univariate Global Optimization Algorithm using D.C. Underestimator", Proceedings of 2001 KIChE Fall Meeting, (2001).

[3] P. M. Pardalos, H. Tuy, "Recent Developments and Trends in Global Optimization", Journal of Computational and Applied Mathematics, 124, 209(2000).

[4] C. S. Adjiman, C. A. Floudas "A global Optimization Method, [eqn: alpha]BB, for General Twice-Differentiable Constrained NLPs - I. Theoretical Advances", Comp. Chem. Engng., 9, 1137(1998).

[5] D. Ratz, T. Csendes, "On the Selection of Subdivision Directions in Interval Branch-and-Bound Methods for Global Optimization", J. Global Optim., 7, 183(1995).

[6] G. V. Reklaitis, A. Ravindran, K. M. Fagsdell, Engineering Optimization - Methods and Application, John Wiley & Sons, Canada(1983).

화학공학의 이론과 응용 제8권 제1호 2002년