Global Optimization: Deterministic ApproachesThe 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. |
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 |
| 681 | |
NOTATION | 719 |
| 723 | |
Other editions - View all
Common terms and phrases
accumulation point affine function argmin basic optimal solution BB procedure bounding operation branch and bound compute con(Q concave function concave minimization problem concavity cut cone Conical Algorithm convergence convex envelope convex function convex programming convex set Corollary d.c. programming D₁ defined deletion denote edge facet feasible point feasible set follows function f global optimal solution global optimization problems halfline hence Horst hyperplane implies inequality iteration Lemma Linear Complementarity Problem linear program Lipschitz Lipschitzian lower bound lower semicontinuous M₁ Mathematical minimize f(x objective function obtained optimal value outer approximation method P₁ Pardalos partition elements partition sets polyhedron polytope programming problem Proof Proposition quadratic Quadratic Programming satisfying Section simplex simplices Step subdivision process Theorem Thoai V₁ vector vertex set vertices