Global Optimization: Deterministic Approaches

Front Cover
Springer Science & Business Media, May 15, 1996 - Business & Economics - 730 pages
1 Review
The main contents and character of the monograph did not change with respect to the first edition. However, within most chapters we incorporated quite a number of modifications which take into account the recent development of the field, the very valuable suggestions and comments that we received from numerous colleagues and students as well as our own experience while using the book. Some errors and misprints in the first edition are also corrected. Reiner Horst May 1992 Hoang Tuy PREFACE TO THE FIRST EDITION The enormous practical need for solving global optimization problems coupled with a rapidly advancing computer technology has allowed one to consider problems which a few years aga would have been considered computationally intractable. As a consequence, we are seeing the creation of a large and increasing number of diverse algorithms for solving a wide variety of multiextremal global optimization problems. The goal of this book is to systematically clarify and unify these diverse approaches in order to provide insight into the underlying concepts and their pro perties. Aside from a coherent view of the field much new material is presented.
 

What people are saying - Write a review

User Review - Flag as inappropriate

Ghag o. X we
D

Contents

SOME IMPORTANT CLASSES OF GLOBAL OPTIMIZATION PROBLEMS
3
2 CONCAVE MINIMIZATION
9
22 Brief Survey of Direct Applications
12
23 Integer Programming and Concave Minimization
14
24 Bilinear Programming and Concave Minimization
20
25 Complementarity Problems and Concave Minimization
24
26 MaxMin Problems and Concave Minimization
25
3 DC PROGRAMMING AND REVERSE CONVEX CONSTRAINTS
26
19 Concave Minimization Problem with Convex Constraints
323
110 Unbounded Feasible Domain
328
111 A Class of Exhaustive Subdivision Processes
329
112 Exhaustive Nondegenerate Subdivision Processes
335
2 SIMPLICIAL ALGORITHMS
342
21 Normal Simplicial Subdivision Processes
343
22 Normal Simplicial Algorithm
345
23 Construction of an NSS Process
347

Applications
32
33 Reverse Convex Constraints
37
34 Canonical DC Programming Problems
39
4 LIPSCHITZIAN OPTIMIZATION AND SYSTEMS OF EQUATIONS AND INEQUALITIES
43
42 Systems of Equations and Inequalities
47
OUTER APPROXIMATION
53
2 OUTER APPROXIMATION BY CONVEX POLYHEDRAL SETS
58
3 CONSTRAINT DROPPING STRATEGIES
67
4 ON SOLVING THE SUBPROBLEMS Qk
71
41 Finding an Initial Polytope D1 and its Vertex Set V1
72
42 Computing New Vertices and New Extreme Directions
74
43 Identifying Redundant Constraints
84
CONCAVITY CUTS
89
2 VALID CUTS IN THE DEGENERATE CASE
95
3 CONVERGENCE OF CUTTING PROCEDURES
99
4 CONCAVITY CUTS FOR HANDLING REVERSE CONVEX CONSTRAINTS
104
5 A CLASS OF GENERALIZED CONCAVITY CUTS
108
6 CUTS USING NEGATIVE EDGE EXTENSIONS
113
BRANCH AND BOUND
115
2 FINITENESS AND CONVERGENCE CONDITIONS
126
3 TYPICAL PARTITION SETS AND THEIR REFINEMENT
137
32 Rectangles and Polyhedral Clones
142
4 LOWER BOUNDS
145
42 Vertex Minima
146
43 Convex Subfunctionals
148
44 Duality
159
45 Consistency
164
5 DELETION BY INFEASIBILITY
169
6 RESTART BRANCH AND BOUND ALGORITHM
176
CONCAVE MINIMIZATION
179
CUTTING METHODS
181
11 Valid Cuts and a Sufficient Condition for Global Optimality
182
12 Outline of the Method
187
2 FACIAL CUT ALGORITHM
190
22 Finding an Extreme Face of D Relative to M
192
23 Facial Valid Cuts
196
24 A Finite Cutting Algorithm
198
3 CUT AND SPLIT ALGORITHM
201
31 Partition of a Cone
202
32 Outline of the Method
203
33 Remarks V4
206
THE CASE OF CONCAVE QUADRATIC FUNCTIONALS
211
42 Konnos Cutting Method for Concave Quadratic Programming
217
43 Bilinear Programming Cuts
222
SUCCESSIVE APPROXIMATION METHODS
225
11 Linearly Constrained Problem
226
12 Problems with Convex Constraints
234
13 Reducing the Sizes of the Relaxed Problems
240
2 INNER APPROXIMATION
243
21 The DGProblem
244
22 The Concept of Polyhedral Annexation
245
23 Computing the Facets of a Polytope
248
24 A Polyhedral Annexation Algorithm
251
25 Relations to Other Methods
261
26 Extensions
264
3 CONVEX UNDERESTIMATION
267
32 The Falk and Hoffman Algorithm
269
33 Rosens Algorithm
273
4 CONCAVE POLYHEDRAL UNDERESTIMATION
278
42 Computation of the Concave Undeiestimators
281
43 Compulation of the Nonvertical Facets of Pk
282
44 Polyhedral Underestimation Algorithm
285
45 Alternative Interpretation
287
46 Separable Problems
289
SUCCESSIVE PARTITION METHODS
295
11 The Normal Conical Subdivision Process
296
12 The Main Subroutine
298
13 Construction of Normal Subdivision Processes
300
14 The Basic NCS Process
306
15 The Normal Conical Algorithm
308
16 Remarks Concerning Implementation
312
17 Example VII1
315
18 Alternative Variants
319
24 The Basic NSS Process
349
25 Normal Simplicial Algorithm for Problems with Convex Constraints
351
3 AN EXACT SIMPLICIAL ALGORITHM
353
32 A Finite Branch and Bound Procedure
356
33 A Modified ES Algorithm
358
34 Unbounded Feasible Set
361
4 RECTANGULAR ALGORITHMS
365
41 Normal Rectangular Algorithm
366
42 Construction of an NRS Process
369
43 Specialization to Concave Quadratic Programming
371
44 Example VII2
377
DECOMPOSITION OF LARGE SCALE PROBLEMS
381
1 DECOMPOSITION FRAMEWORK
382
2 BRANCH AND BOUND APPROACH
384
21 Normal Simplicial Algorithm
385
22 Normal Rectangular Algorithm
388
23 Normal Conical Algorithm
390
3 POLYHEDRAL UNDERESTIMATION METHOD
391
32 Separable Problems
393
4 DECOMPOSITION BY OUTER APPROXIMATION
401
42 Decomposition Algorithm
403
43 An Extension
408
44 Outer Approximation Versus Successive Partition
412
45 Outer Approximation Combined with Branch and Bound
417
5 DECOMPOSITION OF CONCAVE MINIMIZATION PROBLEMS OVER NETWORKS
421
52 The Single Source Uncapatitated Minimum Concave Cost Flow SUCF Problem
426
53 Decomposition Method for SUCF
433
54 Extension
443
SPECIAL PROBLEMS OF CONCAVE MINIMIZATION
447
11 Basic Properties
448
12 Cutting Plane Method
451
13 Polyhedral Annexation
456
14 Conical Algorithm
458
15 Outer Approximation Method
462
2 COMPLEMENTARITY PROBLEMS
469
21 Basic Properties
470
22 Polyhedral Annexation Method for the Linear Complementarity Problem
472
23 Conical Algorithm for the Linear Complementarity Problem
475
24 Other Global Optimization Approaches to LCP
483
25 The Concave Complementarity Problem
486
3 PARAMETRIC CONCAVE PROGRAMMING
490
31 Basic Properties
492
32 Outer Approximation Method for LRCP
497
33 Methods Based on the Edge Property
500
34 Conical Algorithms for LRCP
508
GENERAL NONLINEAR PROBLEMS
517
DC PROGRAMMING
519
11 Duality between the Objective and the Constraints
520
12 Outer Approximation Algorithms for Canonical DC Problems
526
13 Outer Approximation for Solving Noncanonical DC Problems
541
2 BRANCH AND BOUND METHODS
553
3 SOLVING DC PROBLEMS BY A SEQUENCE OF LINEAR PROGRAMS AND LINE SEARCHES
558
4 SOME SPECIAL BC PROBLEMS AND APPLICATIONS
572
42 The Diamond Cutting Problem
581
43 Biconvex Programming and Related Problems
592
LIPSCHITZ AND CONTINUOUS OPTIMIZATION
603
1 BRIEF INTRODUCTION INTO THE GLOBAL MINIMIZATION OF UNIVARIATE LIPSCHITZ FUNCTIONS
604
12 Algorithms for Solving the Univariate Lipschitz Problem
609
2 BRANCH AND BOUND ALGORITHMS
616
21 Branch and Round Interpretation of Piyavskiis Univariate Algorithm
617
22 Branch and Bound Methods for Minimizing a Lipschitz Function over an ndimensional Rectangle
621
23 Branch and Bound Methods for Solving Lipschitz Optimization Problems with General Constraints
632
24 Global Optimization of Concave Functions Subject to Separable Quadratic Constraints
634
25 Linearly Constrained Global Optimization of Functions with Concave Minorants
645
3 OUTER APPROXIMATION
653
4 TIIE RELIEF INDICATOR METHOD
662
41 Separators for f on D
663
42 A Global Optimality Criterion
666
43 The Relief Indicator Method
670
REFERENCES
681
NOTATION
719
INDEX
723
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »