Introduction to Global OptimizationSpringer 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 |
314 | |
Ấn bản in khác - Xem tất cả
Introduction to Global Optimization R. Horst,Panos M. Pardalos,Nguyen Van Thoai Xem trước bị giới hạn - 1995 |
Introduction to Global Optimization R. Horst,Panos M. Pardalos,Nguyen Van Thoai Xem trước bị giới hạn - 2000 |
Thuật ngữ và cụm từ thông dụng
affine function assume bisection bound algorithm branch and bound c¹x Compute concave function concave minimization problem cone Consider constraints convex envelope convex function convex set corresponding d.c. functions d.c. program defined denote edge equivalent example feasible domain feasible point feasible set fi(x finite number function f(x given global minimum global optimization hence implies inequality integer intersection iteration Kuhn-Tucker Let f linear program Lipschitz constant Lipschitzian lower bound matrix maximum clique maximum clique problem MCCFP min{f(x n-simplex node nonempty nonlinear NP-complete NP-hard objective function objective function value obtain optimal solution optimal value optimization problem Pardalos partition sets piecewise linear polyhedral polynomial polytope problem min f(x programming problem Proof Proposition quadratic programming rectangle satisfying Section sequence simplex simplices solving subproblem Theorem upper bound variables vector vertex set vertices y-extension zero-one