화학공정의 글로벌 최적화 기술현황

최 수 형

전북대학교 화학공학부

Global Optimization of Chemical Processes

― A State of the Art Review

Soo Hyoung Choi

School of Chemical Engineering and Technology, Chonbuk National University

Introduction

Optimization of chemical processes often leads to nonlinear programming problems that are nonconvex.  Such problems may possess many local optima, whose objective function value varies significantly from one to the other.  Thus identifying the global optimum is an important, albeit difficult, endeavor.  This paper reviews various global optimization algorithms and presents suggestions to help development of a global optimization method which is suitable for chemical process optimization.

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

min f(x)

subject to

g(x) ≤ 0

h(x) Ａ 0

where x □ Rn, f: Rn → R, g: Rn → Rl, and h: Rn → Rm.  If the objective function and the feasible region are convex, e.g., when f and g are convex and h is linear, the problem is called a convex problem, which has only one local minimum that is the global minimum.  Most of chemical process optimization problems, however, have a nonconvex feasible region because of nonlinear equality constraints.  Therefore, they 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 for global optimization of chemical processes.

Most global optimization algorithms belong to one of the two categories: (1) Deterministic approach and (2) Stochastic approach.  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, and do not guarantee the finite □-convergence (convergence to the global optimum in finite computation steps for a given finite error tolerance), or the globality of the obtained solution.  Algorithms that use the deterministic approach such as branch and bound (Soland, 1971) guarantee the finite □-convergence and the globality of the obtained solution.

The deterministic approach to global optimization of chemical processes has actively been studied since the 1980□s.  Most of the proposed algorithms are based on one of the following methods.

1) Generalized Benders Decomposition (GBD) (Geoffrion, 1972): This algorithm iterates between a primal and a master which give upper and lower bounds respectively for the global optimum.  Based on this approach, Duran and Grossmann (1986) proposed an Outer Approximation algorithm for a particular class of Mixed Integer Nonlinear Programs (MINLP).  Floudas et al. (1989) proposed Global Optimum Search (GOS) algorithm for general problems, which was considered very efficient, but Bagajewicz and Manousiouthakis (1991) indicated an error in this algorithm.  Floudas and Visweswaran (1990) corrected the error, proposing Global Optimization Algorithm (GOP), but the computation time for convergence greatly increased.

2) Branch and Bound: Soland (1971) presented an algorithm of the branch and bound type which solves a separable nonconvex problem by solution of a sequence of convex subproblems.  Each convex subproblem, if feasible, gives a lower bound on the global minimum in its domain.  Subproblems are discarded if they are infeasible or their lower bounds are higher than the upper bound which is set by the value of the objective function at a feasible point.  Feasible subproblems are divided into more subproblems, and the algorithm continues until the lower bound converges to the upper bound.  Based on this approach, Ryoo and Sahinidis (1995) and Adjiman et al. (1996) proposed algorithms for chemical process optimization.

3) Interval Analysis: Ratschek and Rokne (1988, 1991) presented a branch and bound algorithm which uses interval analysis to calculate lower bounds.  Unlike the above mentioned algorithms, their algorithm can be applied to any type of problems, not requiring any problem transformation.  This algorithm was modified and applied to chemical process optimization by Vaidyanathan and El-Halwagi (1994).

Global optimization of a nonconvex NLP is an NP (Non-Polynomially)-hard problem, and thus, when a deterministic algorithm is used, the computation time drastically (generally, exponentially) increases with the size of the problem.  This is the reason that all the example problems in the papers that propose deterministic algorithms are extremely small.  Chemical process optimization problems are generally highly nonlinear, nonconvex, and very large.  Therefore, the conventional deterministic algorithms are not suitable for chemical process optimization.  Some people suggest that the stochastic approach is practically the only way to global optimization of large problems.  However, as the computer hardware is rapidly being improved these days, it is still justifiable to study on the deterministic approach.

Methodology

The goal of global optimization is achieved if a method is developed which is guaranteed to do one of the following tasks.

1) Find a tight convex hull.  Assume that we have an NLP reformulated by a substitution variable so that the objective function is linear.  Consider a new problem in which the constraints form a tight convex hull for the feasible region of the reformulated problem.  This is a convex problem which can easily be solved by a local optimization technique and whose solution is equivalent to the global solution of the original problem.  This is the basic idea of most of the deterministic algorithms.

2) Find a feasible point.  Assume that we have a method which is guaranteed to find a feasible point if any exists.  Given a feasible point, standard software finds a local optimum without failure.  We can 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.

3) Find all Kuhn-Tucker points.  If a method is developed which is guaranteed to find all real roots of systems of nonlinear algebraic equations, the objective function values at all Kuhn-Tucker points can be compared to each other to find the global optimum.

Suggestions

Deterministic Approach: The deterministic algorithms based on methodology (1) described above can be applied to small problems only.  However, the power of computer hardware is rapidly being enhanced, and the massively parallel computing technique is actively being developed these days.  In the future, the size of many chemical process optimization problems will be considered small enough for the deterministic algorithms.  Therefore, further research is still required to develop efficient deterministic algorithms.

Stochastic Approach: Stochastic algorithms do not suffer from the NP-hardness, 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.  The simplest method is to convert constrained optimization problems to unconstrained problems using a penalty function.  However, when there are too many equality constraints as in chemical process optimization problems, it is difficult to keep the reformulated problem numerically stable.  Therefore, development of a new method is suggested, which may be based on methodology (2), since, for any given problem, we can formulate an infeasibility minimization problem for which a feasible point can easily be found.

Equation Solving Approach: Global optimization is achieved if all Kuhn- Tucker points can be determined.  This approach based on methodology (3) requires a method for finding all real roots of systems of nonlinear algebraic equations.  Global homotopy continuation methods such as proposed by Gustafson and Beris (1991) can be considered.  Methods based on path tracking are being improved and have high probability of finding all real roots.  The results from these methods are deterministic, and therefore, this approach may be considered a deterministic approach for which the globality of the obtained solution is highly probable.  Since it is not an NP-hard problem to trace all paths in the complex space, these methods can be applied to large problems.

Conclusion

Studies on global optimization indicate that no method has been successful in chemical process optimization yet.  Deterministic algorithms take too much computa- tion time even for moderately sized problems.  Stochastic algorithms have difficulties in dealing with equality constraints, and always request good luck, which we do not want to rely on.  A possible negotiation between deterministic and stochastic approaches at this point is a deterministic method which guarantees high probability of finding the global optimum such as the equation solving approach.

Acknowledgement

This work was supported by NON DIRECTED RESEARCH FUND, Korea Research Foundation.  The author also gratefully acknowledges partial support from Korea Science and Engineering Foundation through Automation Research Center at Pohang University of Science and Technology.

References

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

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

Duran, M. A. and Grossmann, I. E., □An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs□, Mathematical Programming, 36, 307-339 (1986).

Floudas, C. A., Aggarwal, A. and Ciric, A. R., □Global Optimum Search for Nonconvex NLP and MINLP Problems□, Computers & Chem. Eng., 13(10), 1117-1132 (1989).

Floudas C. A. and Visweswaran, V., □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, 237-260 (1972).

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

Gustafson, J. B. and Beris, A. N., □Evaluating All Real Roots of Nonlinear Equations Using a Fixed-Point Homotopy Method□, AIChE J. R&D Notes, 37(11), 1749-1752 (1991).

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

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

Ratschek, H. and Rokne, J., □Interval Tools for Global Optimization□, Computers Math. Applic., 21(6/7), 41-50 (1991).

Ryoo, H. S. and Sahinidis, N. V., □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 El-Halwagi, M., □Global Otimization of Nonconvex Nonlinear Programs via Interval Analysis□, Computers & Chem. Eng., 18(10), 889-897 (1994).