연속적인 국부 최적화와 탈출을 이용한 전역 최적화

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

김범수, 이태용

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

Global Optimization by Successive Local Optimization and Escape

Bum-soo Kim, Tai-yong Lee

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

Department of Chemical and biomolecular Engineering, KAIST

Introduction

In the last decades, there are prominent efforts to the global optimization leading the development of theoretical and algorithmic studies which arise in chemical engineering design, synthesis, process control, as well as in computational chemistry and molecular biology. The area of global optimization has attracted the interest in chemical engineering for three reasons. First, a number of process synthesis, design, control, and operation include global optimization problems. Second, the local optimization routines such as generalized reduced gradient and successive quadratic programming may be trapped in a local optimum solution. Third, the obtained local optimum solution has too different physical meaning compared with the global optimum. This problem happens in the area of phase equilibrium[1].

At local optimum point, the equations resulting from the first-order necessary conditions known as Karush-Kuhn-Tucker conditions must be satisfied. Although a global optimum point must also be a local optimum, there are no mathematical conditions that characterize a global optimum point. Therefore, the global problem is much harder to solve. Many authors have concluded that the problem is unsolvable from a mathematical point of view[2]. In practice, however, numerical methods are available to find an approximate solution to the problem.

Robust algorithm for local optimization are well-developed and readily available for use. Robustness means numerical stability and ability to find a solution for a wide range of algorithmic parameters. For solution of global optimization problem, several algorithms have also been discussed in the literature. Details for the methods can be found in [3]. Among these algorithms, there are very few methods for general nonlinear global optimization problems. In addition, very few algorithms have been tested for engineering applications that are formulated as general nonlinear problems(NLPs). Therefore, there is a need for new methods. It is the one of the solutions that find a new method to take advantage of the available local optimization algorithms.

As mentioned above, the local optimization routines may be trapped in a local optimum solution. But if we can escape the local optimum and continue to find another local optimum, the global optimum can be founded. Termination criterion will be discussed later. In this paper, we introduced the method which uses the local optimization algorithm such as a conjugate gradient method.

Proposed Algorithm

The proposed algorithm can be decomposed into two phases. One is a local optimization phase and the other is escape phase. On the local optimization phase, we use the conjugate gradient method. The reason we select this method is that the conjugate gradient method is reliable far from local optimum and accelerates as the sequence of iterates approached the optimum. Also gradient based methods are very effective to find a optimum. Additionally, the conjugate direction method is evaluated completely by many authors since it was proposed. Because we use a gradient information, the objective function must be differentiable. We assume that we have a minimization problem.

[eqn: min ~f(x)]

[eqn: s.t.~:~a_i <= x_i <= b_i`,~~i=1,…,n]

Let [eqn: x^0] be a starting point. From the starting point, [eqn: x^0], the conjugate gradient method will find any local optimum, [eqn: x^1], [eqn: f(x^1 ) <= f(x^0 )], [eqn: f(x^1 )=f_1]. As we know, using local optimization method itself we cannot escape the local optimum. Therefore the escape phase is needed. On the escape phase, we solve the new problem which is composed by the following maximization problem.

[eqn: max`□x^2 -x^1 □]

[eqn: s.t.`:~□x^2 - x^1 □>= epsilon]

[eqn: f_2 =f(x^2 ) <= f_1]

[eqn: a_i <=x_i <= b_i`,~~i=1,…,n]

Once we obtain the local optimum, [eqn: x^1], we will determine epsilon so that [eqn: x^j] is the unique optimum in the epsilon-neighborhood of [eqn: x^j]. If we can get [eqn: x^2], that  means we escape the local minimum, because [eqn: x^2] is located outside of epsilon-neighborhood of [eqn: x^j]. Note that [eqn: x^2] is not the local or global optimum but a new starting point. At this point of time, we come back to the local optimization phase, then calculate another local optimum, [eqn: x^3],  using [eqn: x^2] as a new starting point. These procedures continue until the escape phase cannot find any new starting point. This is a termination condition. This procedures can be explained by the following basic frame of flow chart and Fig. 1.

[Flow Chart]	[Fig. 1]

As we see in flow chart and Fig. 1, this is a very simple and effective method to find the global optimum. In the following section, we evaluated this method by some examples.

Example and Results

In this section, example problems are described. Working examples are Levy No. 13 (n=2) and Levy No. 14 (n=3)[5].

[eqn: f_{ n } (x)= sum from { i=1 } to { n-1 } { (x_{ i } -1)^{ 2 } (1+sin^{ 2 } (3 pi x_{ i+1 } ))+(x_{ n } -1)^{ 2 } (1+sin^{ 2 } (2 pi x_{ n } ))+sin^{ 2 } (3 pi x_{ 1 } ) }]

The above problems are widely accepted as a standard one to test a new algorithm in the area of global optimization[4, 5]. These problems are chosen from several test problems since its nonlinearity increases with the dimension. 1-Dimensional problem is formulated based on Levy No. 13. This problem has the almost same degree of nonlinearity as n-dimensional problems do.

[eqn: f_{ 1 } (x)=(x-1)^{ 2 } (1+sin^{ 2 } (2 pi x))]

Objective function and initial boundaries of variables are summarized in Table 1. The shapes of example functions is shown in Fig. 2 and Fig. 3 that are Ex. 1 and Ex. 2.

Ex. No	n	Search region	Nick Name
Ex. 1	1	-10≤[eqn: x]≤10
Ex. 2	2	-5≤[eqn: x_i]≤5	Levy No. 13
Ex. 3	3	-5≤[eqn: x_i]≤5	Levy No. 14

[Table]

[Fig. 2]	[Fig. 3]

All given examples have the same optimum function value.

[eqn: (global)min~f(x)=0]

[eqn: Solutions~:~x_{ i } =1.0~~~~~~i=1, CDOTS ,n]

By using the proposed method, we can get the global optimum. The results are shown in Fig. 4 and Table 2. Fig. 4 shows convergence characteristics of the proposed algorithm for example 3. But as routine converges to the global optimum, the decrease speed gets slow. The obtained local optimum values are showed in Fig. 4.

Conclusion

The proposed method is applied to a standard test problem such as Levy problem and its global optimum points are obtained. We use the conjugate gradient method at the local optimization phase. As shown in Table 2, the obtatined solutions are ver close to the exact solutions. It means the proposed method works effectively and accurately.

In this algorithm, if the performance of the local optimization routine dose not guarantee, the whole procedure may be failed. Therefore its performance is very important. Also epsilon can be supplied by mathematical operation such as interval arithmetic. Because we are in a initial step to develop this method, we use MS-IMSL for local optimization. Further modification for acceleration and local optimization routine may improve its performance.

Ex. No	Exact Solution	Obtained Solution
Ex. 1	1	1.00000684
Ex. 2	(1, 1)	(1.0000015, 0.9991863)
Ex. 3	(1, 1, 1)	(1.00000048, 0.99996447, 1.00000007)

[Fig. 4]	[Table 2]

Acknowledgement

This work was also partially supported by the Brain Korea 21 project

References

1. Young-soo Kim and Tai-yong Lee, "Acceleration of □BB Algorithm using Quadratic Underestimator in Global Optimization", Master thesis, KAIST, 2000

2. O. A. Elwakeil and J. S. Arora, "Two Algorithm for Global Optimization of General NLP Problems", International Journal for Numerical Methods in Eng., vol. 39, pp. 3305-3325, 1996.

3. J. S. Arora, O. A. Elwakeil, A. I. Chahande and C. C. Hsieh, "Global Optimization Methods for Engineering Applications: a review", Struct. Optim. vol. 9, pp. 137-159, 1995

4. D. Ratz and T. Csendes, "On the Selection of Subdivision Directions in Interval Branch-and-Bound Methods for Global Optimization", J. Global Optim., vol.7, pp. 183, 1995

5. A. V. Levy, A. Montalvo, S. Gomez and A. Calderon, "Topics in Global Optimization", Lecture Notes in Mathematics, No. 909, Springer-Verlag, Berlin, 1981