Introduction to Global Optimization

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 mọi người đang nói đến -Viết bài đánh giá

Chúng tôi không tìm thấy bài đánh giá nào ở các vị trí thông thường.

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