D.C. 과소평가함수를 이용한

제약조건이 있는 단변수 전역 최적화 알고리즘

박 영 철 , 장 민 호, 이 태 용

대전광역시 유성구 구성동 373-1 (우) 305-701

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

Constrained Univariate Global Optimization Algorithm

using D.C. Underestimator

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

Department of Chemical  Engineering

Korea Advanced Institute of  Science and Technology

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

Introduction

A significant effort has been expended in the last five decades toward theoretical and algorithmic studies of applications that arise in chemical engineering process design, process synthesis, process control, as well as in computational chemistry and molecular biology. 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 too different physical meaning compared with the global optimum.

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 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. Review has been provided by Pardalos, Romeijn and Tuy (2000).

This paper introduces a rapidly convergent deterministic algorithm for solving constrained univariate global minimization. This algorithm has difference of convex underestimator, which comes from the modification of Fludas (2000) and Kim (2001). The proposed algorithm does not require branch-and-bound (BB) procedure.

Underestimator

In [eqn: alpha]BB algorithm, convex underestimator of any twice differentiable function is given by

[eqn: f(x) >= P(x)=f(x)+ alpha ( x_L -x ) ( x_U -x ) = f(x) + Q(x)]

where [eqn: f(x)] twice differentiable objective function (or constraint)

[eqn: P(x)] convex underestimator

[eqn: Q(x)] convexifying quadrature

Note that [eqn: alpha] is chosen as a non-negative number large enough to make [eqn: P(x)] convex. Kim suggested an intermediate quadratic underestimator [eqn: R(x)] that underestimates the underestimator [eqn: P(x)] of the original [eqn: alpha]BB algorithm for a general nonlinear function.

[eqn: P(x)=f(x)+Q(x) >= R(x)=beta_0 + beta_1 x + beta_2 x^2]

[eqn: R(x)] is used to obtain the new underestimator, [eqn: S(x)], which is defined as

[eqn: f(x)>=S(x)=R(x)-Q(x)=(beta_0 -alpha x_L x_U ) + (beta_1 +alphax_L +alphax_U ) x + (beta_2 -alpha) x^2]

Then, we can classify the underestimator into following five cases shown in Table 1.

Let's consider Case IV where [eqn: beta_2 =0]. In this case, the intermediate underestimator [eqn: R(x)] is linear and the ultimate underestimator [eqn: S(x)] is negative definite quadrature. This proposed underestimator has several remarks.

Remarks i) [eqn: R(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(x)] is the same as that of [eqn: R(x)].

iii) The global minimum of [eqn: S(x)] is located at one of the vertices of [eqn: S(x)], which serves as the lover bound of the global minimum of [eqn: f(x)].

iv) The upper bound of the global minimum of [eqn: f(x)] can be selected as the minimum value of [eqn: f(x)] evaluated at each vertex.

v) The preposed algorithm does not require branch-and-bound procedure.

Definition Let [eqn: OMEGA] be a convex set in [eqn: R^n]. We say that a function is d.c. on [eqn: OMEGA] if it can be expressed as the difference of two convex functions on [eqn: OMEGA].

By this definition, we can see an ultimate underestimator [eqn: S(x)] is d.c. function.

Minimization of nonlinearly constrained problems

In this section, we consider the minimization of general NLP problems given by

[eqn: min f(x)]

[eqn: s.t. g_ nu (x)>=0 , nu=1,..., n]

[eqn: h_ mu (x)=0 , mu=1,...,m]

For the nonlinear constraints, we can consider overestimator as the same methodology as proposed underestimator to find infeasible region.

[eqn: S_g (x)=R_g (x) + Q_g (x)>=g(x)]

where [eqn: S_g (x)] proposed overestimator for nonlinear inequality constraints ([eqn: g (x)>=0])

[eqn: R_g (x)] an intermediate overstimator (tangential hyperplane (linear) of [eqn: g (x)])

[eqn: Q_g f(x)] convexifying quadrature of [eqn: g (x)]

The idea of the proposed overestimator can be applied to the inequality constraints. Also if we represent the equality constraints as

[eqn: h_mu (x)>=0] and [eqn: -h_mu (x)>=0]

then, the proposed overestimator can be applied to the equality constraints, too.

Motivating example and Result

The proposed algorithm is applied to the following motivating example.

[eqn: min f(x) = (x^2 -x +1) sin x]

[eqn: s.t.]