Introduction to Global Optimization

B́a trước
Springer Science & Business Media, 30 thg 6, 1995 - 320 trang
Global optimization concerns the computation and characterization of global optima of nonlinear functions. Such problems are widespread in the mathematical modelling of real systems in a very wide range of applications and the last 30 years have seen the development of many new theoretical, algorithmic and computational contributions which have helped to solve globally multiextreme problems in important practical applications.
Most of the existing books on optimization focus on the problem of computing locally optimal solutions. Introduction to Global Optimization, however, is a comprehensive textbook on constrained global optimization that covers the fundamentals of the subject, presenting much new material, including algorithms, applications and complexity results for quadratic programming, concave minimization, DC and Lipschitz problems, and nonlinear network flow. Each chapter contains illustrative examples and ends with carefully selected exercises, designed to help students grasp the material and enhance their knowledge of the methods involved.
Audience: Students of mathematical programming, and all scientists, from whatever discipline, who need global optimization methods in such diverse areas as economic modelling, fixed charges, finance, networks and transportation, databases, chip design, image processing, nuclear and mechanical design, chemical engineering design and control, molecular biology, and environmental engineering.
 

Nội dung

Fundamental Results on Convexity and Optimization
1
12 General Properties of Optimization Problems
10
13 Convex Envelopes
16
14 KuhnTucker Conditions
20
15 Second Order Optimality Conditions
25
16 Duality in Nonlinear Programming
26
17 Complexity Issues
32
171 Complexity of KuhnTuckerPoints in Quadratic Programming
34
371 The basic algorithm
159
372 A simplicial branch and bound algorithm Partition sets and their subdivision
161
373 A conical branch and bound algorithm
167
374 A rectangular algorithm
173
375 Branch and Bound Methods for Convex Constraints
177
38 A Siniplicial Branch and Bound Approach for the General Quadratic Optimization Problem
178
39 Exercises
184
DC Programming
191

172 Complexity of Local Minimization
35
18 Exercises
39
Quadratic Programming
47
22 Quadratic Integer Programming
49
222 Nonlinear Assignment Problems
50
223 The Maximum Clique Problem
54
224 Branch and Bound Algorithm for Quadratic ZeroOne Programming
60
23 Linear Complementarity Problem
69
24 Complexity of Quadratic Optimization
72
242 A Polynomial Algorithm for Maximizing the Euclidean Norm over an Arbitrary Rectangular Parallelotope
77
25 Enumerative Methods
81
26 Separation and Interpolation
84
261 Reduction to Separable Form
85
262 Linear Underestimator and Error Bounds
86
263 Guaranteed eapproximate solution
89
264 Implementation
91
265 Indefinite Quadratic Problems
95
27 Exercises
99
General Concave Minimization
105
32 Applications
106
322 Problems that can be transformed into Concave Minimization Problems
108
33 Basic Operations
114
332 Concave Minimization over Standard Polytopes
115
333 yExtension
118
334 Vertex Enumeration
119
335 Facet Enumeration
125
336 Polyhedral Partitions
129
34 Cutting Plane Algorithms
131
341 Concavity Cut
132
342 A Cutting Plane for Concave Quadratic Function
134
343 Algorithm 31 Cutting Plane Method
138
35 Outer Approximation Algorithms
143
352 Implementation of Algorithm 32
145
353 Outer Approximation for Convex Constraints
150
361 The Basic Algorithm
153
362 Implementation and Finite Convergence
155
37 Branch and Bound Algorithms
158
42 The Space of DC Functions
192
43 Some Additional Applications
197
433 Webers Problem with Attraction and Repulsion
198
434 Minimax Problems
199
435 Engineering Design
200
44 The Canonical DC Program
202
442 Optimality Conditions
203
443 An Edge Following Algorithm
206
45 A Conical Branch and Bound Algorithm
211
46 A Prismatic Algorithm for Minimizing a DC Function Over a Polytope
219
47 Exercises
228
Lipschitz Optimization
231
52 Lipschitz Optimization Problems
234
521 Approximation problems
235
522 Systems of nonlinear equations and inequalities
236
53 Lower Bounds
237
54 Branch and Bound Algorithms
241
541 Lipschitz Optimization over Rectangles and Simplices
242
542 Linear Constraints
247
543 Lipschitz Constraints
249
55 Implementation of Branch and Bound Methods and Numerical Results
253
552 Numerical Example
254
56 Exercises
258
Global Optimization on Networks
261
62 Some MCCFP Models and its Complexity
264
622 The ProductionTransportation Problem with Concave Production Cost
265
623 The Steiner Problem on Networks
267
624 ProductionInventory Problems
268
625 Complexity of the MCCFP
269
63 Solution Methods
270
632 An Algorithm for problem PCpLq
272
633 A Decomposition Algorithm for Problem PCmLo
279
64 Exercises
282
Solutions
285
Selected References
308
Index
314
Bản quyền

Ấn bản in khác - Xem tất cả

Thuật ngữ và cụm từ thông dụng

Thông tin thư mục