화학공정의 글로벌 최적화를 위한 확률적 알고리듬

최 수 형

전북대학교 화학공학부

A Stochastic Algorithm for Global Optimization

of Chemical Processes

Soo Hyoung Choi

School of Chemical Engineering and Technology, Chonbuk National University

Introduction

Many chemical process optimization problems can be represented by nonlinear programming (NLP) problems in the following form.

min f(x)                               (P)

subject to

g(x) ≤ 0

h(x) Ａ 0

where x□Rn, f : Rn→R, g: Rn→Rl, h: Rn→Rm, and n > m.  Most of these problems are nonconvex, and in many cases, have multiple local optima.  However, most optimization techniques currently used are local methods, which easily crash, and at best, find only one local optimum.  The goal of this study is to develop a method suitable for global optimization of chemical processes which requires solution of large nonconvex NLP problems.

Most global optimization algorithms belong to one of the two categories: (1) Deterministic approach and (2) Stochastic approach.  Algorithms based on the deterministic approach such as Generalized Benders Decomposition (Geoffrion, 1972; Floudas and Visweswaran, 1990, Bagajewicz and Manousiouthakis, 1991), Branch and Bound (Soland, 1971; Ryoo and Sahinidis, 1995; Adjiman et al., 1996), and Interval Analysis (Ratschek and Rokne, 1988; Vaidyanathan and El-Halwagi, 1994; Han et al., 1997) guarantee the finite □- convergence (convergence to the global optimum in finite computation steps for a given finite error tolerance) and the global optimality of the obtained solution.  Algorithms such as simulated annealing (Kirkpatrick et al., 1983) and genetic algorithm (Goldberg, 1989) are based on the stochastic approach.  These algorithms aim high probability of finding the global optimum, not guaranteeing the finite □-convergence or the global optimality of the obtained solution.

The deterministic approach to global optimization of chemical processes has actively been studied since the 1980□s, and some history is summarized by Han et al. (1997).  However, since the global optimization of a nonconvex NLP problem is inherently an NP-hard and not NP-complete (Nondeterministic Polynomial time complete) problem, the deterministic algorithms that are currently available can be applied to small problems only.

Stochastic algorithms do not suffer from the NP-hardness of the problem, and thus they are considered to be suitable for large problems.  However, these algorithms still have difficulties when applied to chemical process optimization problems.  The stochastic algorithms are based on the random search technique.  Since the evaluation of the objective function is meaningful only at feasible points, they are suitable for unconstrained optimization problems only.  However, most chemical process optimization problems have many equality constraints.  Therefore, the problem or the algorithm should be modified.

There are methods to convert constrained optimization problems to unconstrained problems.  For example, a penalty function can be used.  However, when there are too many equality constraints as in chemical process optimization problems, it is difficult to keep the reformulated problem numerically stable.  In order to efficiently deal with equality constraints in stochastic algorithms, an infeasibility minimization technique is adopted in this work.

Complexity Analysis

The class of problems that can be solved by a deterministic algorithm in polynomial time is called P.  Polynomial time means time proportional to a polynomial in terms of the size of the problem.  The problems for which no polynomial time algorithm is available are called NP-hard problems.  For such problems, the computation time increases exponentially with the size of the problem.  Assume that there are problems for which an algorithm exists that can guess a solution and then check whether or not the guess is correct in polynomial time.   The class of such problems is called NP, which stands for Nondeterministic Polynomial time.  Although it is still not proven that P □ NP, it is extremely unlikely that P = NP.  Therefore, problems in NP are considered inherently hard problems.

There is a subclass of NP called NP-complete problems.  An NP-complete problem can be solved in polynomial time if and only if all other NP-complete problems can also be solved in polynomial time.  If an NP-hard problem can be solved in polynomial time then all NP-complete problems can be solved in polynomial time.  Therefore, an NP-complete problem is an NP-hard problem in NP.  NP-hard problems that are not in NP can be considered more difficult than the NP-complete problems.

Before the theory of NP-completeness (Cook, 1971; Horowitz et al., 1997) was developed, it was widely thought that □scaling up□ to larger problems was simply a matter of faster hardware and larger memories (Russell and Norvig, 1995).  The global optimization of a nonconvex NLP problem is an NP-hard and not NP-complete problem, in other words, one of the worst NP-hard problems.  Therefore, the deterministic global optimization algorithms cannot be applied to large problems.

Assume that we have a method which is guaranteed to find a feasible point if any exists.  Given a feasible point, standard software can find a local optimum without failure.  We can then add a new constraint that forces the objective function value to be lower than the current local minimum, and search for a new feasible point.  This procedure can be repeated until no feasible point exists.  The problem of finding a feasible point is in NP because checking the feasibility of a given point takes polynomial time.  Therefore, Finding a feasible point can be considered easier than finding the global optimum of a given problem.  A method based on this approach is proposed, which uses a conventional local optimizer and the Simulated Annealing technique (Kirkpatrick et al., 1983).

Stochastic Infeasibility Minimization Algorithm

Step 0. Initialization

(1) Get lower and upper bounds of the variables, and set a := lb x and

b := ub x.

(2) Get the global optimality tolerance □ > 0.

(3) Get the simulated annealing parameters N and T > 0.

(3) Set the previously found local minimum f o ← +∞.

Step 1. Starting point

(1) Take n random numbers u = {ui | ui □ [0, 1]}.

(2) Set xo = {xio | xio = ai ／ ui (bi １ ai)}.

(3) Solve the following infeasibility minimization problem for □ at fixed

x = xo.

min □                               (I)

subject to

g(x) ≤ □1

h(x) ≤ □1

１h(x) ≤ □1

f(x) ≤  f o １ □ ／ □

where 1 Ａ [1, ..., 1]T.  Note that □ < □ means that x is a feasible point at which the value of the objective function is lower than the previously found local minimum  f o.

(4) Set □o ← □, □* ← □, and x* ← xo .

Step 2. Infeasibility minimization phase 1: simulated annealing

(1) Take n random numbers v = {vi | vi □ [0, 1]}.

(2) Set x = {xi | xi = xio ／ (vi １ 0.5)(bi １ ai); If xi < ai, xi ← ai ; If xi >

bi, xi ← bi }.

(3) Solve Problem (I) for □ at fixed x.

(4) If △□ := □ １ □o ≤ 0,

(a) If □ < □*, set □* ← □ and x* ← x.

(b) Go to Step 2(6).

(5) Otherwise,

(a) Take a random number w □ [0, 1].

(b) If w ≤ exp( １ △□ / T ), go to Step 2(6).

(c) Otherwise, go to Step 2(1).

(6) Set xo ← x and □o ← □.

(7) Repeat Steps 2(1) through 2(6) for N times.

(8) If □* < □, go to Step 4.

Step 3. Infeasibility minimization phase 2: local minimization

(1) Starting from (x*, □*), solve locally Problem (I).

(2) If it converges to □ < □, take the solution x* as a feasible point, and

go to Step 4.

(3) Otherwise, go to Step 5.

Step 4. Objective function minimization

(1) Using the feasible point x* as the initial guess, solve locally Problem

(P).

(2) Update the local minimum f o, and display the solution as the

currently best result.

Step 5. Stopping rule

(1) If more iterations are allowed, go to Step 1.

(2) Otherwise, stop and conclude that  f o is the global minimum.

Conclusion

Studies on global optimization indicate that no method has been successful in chemical process optimization yet.  Deterministic algorithms take too much computation time even for moderately sized problems.  Stochastic algorithms have difficulties in dealing with equality constraints.  Therefore, a method suitable for large problems with many equality constraints has been proposed, which uses a stochastic global algorithm and a deterministic local algorithm together.  This method can be applied to large chemical process optimization problems.  It gives useful results in a reasonable time span, and as the procedure continues, the probability of the global optimality of the obtained solution continues to increase.

Acknowledgement

This work was supported by the Korea Science and Engineering Foundation (KOSEF) through the Automation Research Center at Pohang University of Science and Technology.

References

Adjiman, C. S., I. P. Androulakis, C. D. Maranas and C. A. Floudas, A Global Optimization Method, □BB, for Process Design, Computers & Chem. Eng., 20, Suppl., S419-S424 (1996).

Bagajewicz, M. and V. Manousiouthakis, On the Generalized Benders Decomposition, Computers & Chem. Eng., 15(10), 691-700 (1991).

Cook, S. A., The Complexity of Theorem-Proving Procedures, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151-158 (1971).

Floudas C. A. and V. Visweswaran, A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs - I. Theory, Computers & Chem. Eng., 14(12), 1397-1417 (1990).

Geoffrion, A. M., Generalized Benders Decomposition, J. Opt. Theory Applic., 10(4), 237-260 (1972).

Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.

Han, J. R., V. Manousiouthakis, and S. H. Choi, Global Optimization of Chemical Processes Using the Interval Analysis, Korean J. of Chem. Eng., 14(4), 270-276 (1997).

Horowitz, E., S. Sahni and S. Rajasekaran, Computer Algorithms/C++, Computer Science Press, 1997.

Kirkpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi, Optimization by Simulated Annealing, Science, 220(4598), 671-680 (1983).

Ratschek, H. and J. Rokne, New Computer Methods for Global Optimization, Ellis Horwood, 1988.

Russel, S. J. and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall, 1995.

Ryoo, H. S. and N. V. Sahinidis, Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design, Computers & Chem. Eng., 19(5), 551-566 (1995).

Soland R. M., An Algorithm for Separable Nonconvex Programming Problems II: Nonconvex Constraints, Management Science, 17(11), 759-773 (1971).

Vaidyanathan, R. and M. El-Halwagi, Global Optimization of Nonconvex Nonlinear Programs via Interval Analysis, Computers & Chem. Eng., 18(10), 889-897 (1994).