• PDF / 237,248 Bytes
• 5 Pages / 468 x 684 pts Page_size
• 90 Downloads / 272 Views

DOWNLOAD

REPORT

---

Introduction Constrained global optimization is concerned with the characterization and computation of global minima or maxima of nonconvex problems. The general constrained global minimization problem has the following form:

f(x)

MINxex Subject to h(x)

= o

g(x) < 0 where f(x) is a real wlued continuous function, X is a nonempty compact set in R n, h(x) represents a set of m equality constraints and g(x) represents a set of k inequality constraints. Such problems are widespread in the mathematical modeling of real world systems for a very broad range of applications. Such applications include structural optimization, engineering design, VLSI chip design and database problems, nuclear and mechanical design, chemical engineering design and control, economies of scale, fixed charges, allocation and location problems, quadratic assignment and a number of other combinatorial optimization problems such as integer programming and related graph problems (e.g. maximum clique problem).

From the complexity point of view global optimization problems belong to the class of NP-hard problems. This means that as the input size of the problem increases the computational time required to solve the problem is expected to grow exponentially. Furthermore, even for the case of quadratic nonconvex programming it has been shown that the problem of checking if a given feasible solution is a local optimum is NP-hard ([157], [175]). In addition, the problem of determining an e-approximate global solution remains NP-hard. Although standard nonlinear programming algorithms will usually obtain a local minimum or a stationary point to a global optimization problem, such a local minimum will only be global when certain conditions are satisfied (such as f(x) is quasi-convex and the feasible domain is convex). In general, several local minima may exist and the corresponding function values may differ substantially. The problem of designing algorithms that obtain global solutions is very difficult, since in general there is no local criterion for deciding whether a local solution is global. Active research during the past two decades has produced a variety of deterministic and stochastic methods for determining global solutions to nonconvex nonlinear optimization problems. Reviews and books on the subject of global optimization include [59], [60], [171], [172], [80], [185], [48], [220], [152], [114]. An extensive list of references on deterministic global optimization approaches is provided in the references section of this book. Some of the proposed algorithms for global optimization have been implemented and tested on certain problems. The efficiency of a global optimization algorithm is based upon several criteria including its effectiveness with respect to different problem classes, its speed, its capacity, and its accuracy. Since existing theory cannot itself provide measurement for these criteria, empirical computational testing is necessary. Testing and benchmarking of global optimization algorithms is a very difficult task. Three main