PREFACE |
Part I FOUNDATIONS 1 |
1 SCOPE OF GLOBAL OPTIMIZATION 3 |
1.1 Models and Nature of the Problem 4 |
1.2 Mathematical Structure 10 |
1.3 Hierarchy of Global Optimization Problems 13 |
1.4 Transcending Stationarity as the Core of Global Optimization 15 |
1.5 Problems With Special Structures 18 |
2 QUASI-CONVEXITY 23 |
2.1 Quasi-Convex Functions 24 |
2.2 Quasi-conjugacy 30 |
2.3 Quasi-biconjugate 39 |
2.4 Quasi-subdifferential 43 |
3 D.C. FUNCTIONS AND D.C. SETS 47 |
3.1 Some Typical Examples 47 |
3.2 General Properties of D.C. Functions 50 |
3.3 How to Recognize D.C. Functions 52 |
3.4 Effective D.C. Representation 56 |
3.5 D.C. Sets 67 |
3.6 Global Optimality Criterion 72 |
4 DUALITY 77 |
4.1 Quasi-convex Minimization over a Convex Set 78 |
4.2 Maximization over a Convex Set and Minimization over the Complement of a Convex Set 85 |
4.3 D.C. Optimization 93 |
5 LOW-RANK NONCONVEX STRUCTURES 95 |
5.1 Nonconvexity Rank 96 |
5.2 Nonconvexity Index 100 |
5.3 Weakly Convex Functions 108 |
5.4 D.C. Representation by a Nucleus 113 |
6 GLOBAL SEARCH METHODS AND BASIC D.C. OPTIMIZATION ALGORITHMS 119 |
6.1 Outer Approximation 119 |
6.2 Successive Partition 130 |
6.3 Dualization 155 |
Part II METHODS AND ALGORITHMS 167 |
7 PARAMETRIC APPROACHES IN GLOBAL OPTIMIZATION 169 |
7.1 Minimization of a Generalized Linear Multiplicative Function and a Sum of Two Linear Fractional Functions 170 |
7.2 Rank Two and Rank Three Bilinear Programming Problems 177 |
7.3 Average Performance of Parametric Algorithms 184 |
7.4 Minimization of Low-Rank Concave Functions 191 |
8 MULTIPLICATIVE PROGRAMMING PROBLEMS 203 |
8.1 Convex Multiplicative Programming Problems 204 |
8.2 Minimization of a Product of Several Convex Functions 213 |
8.3 Other Problems Related to Multiplicative Functions 220 |
9 MONOTONIC PROBLEMS 229 |
9.1 Quasiconcave Monotonic Functions 230 |
9.2 Basic Structural Properties 234 |
9.3 Linearly Constrained Problems 240 |
9.4 Solution Methods for Monotonic Problems 244 |
9.5 Decomposition by Polyhedral Annexation 247 |
9.6 Decomposition by Projection 252 |
9.7 Problems With Monotonic Constraints 258 |
9.8 Cases of Polynomial Solvability: Network Constraints 264 |
10 DECOMPOSITION METHODS BY PRICES 273 |
10.1 Generalized Dantzig-Wolfe's Decomposition Method 274 |
10.2 Generalized Benders' Partitioning Method 283 |
10.3 Alternative Variant 291 |
11 DYNAMIC PROGRAMMING ALGORITHMS IN GLOBAL OPTIMIZATION 297 |
11.1 Multi-Echelon Production and Inventory Problem 298 |
11.2 Lot-Sizing Problems with Generalized Concave Cost Functions 303 |
11.3 Discrete-Variable Multi-Stage Problems 310 |
Part III SELECTED APPLICATIONS 323 |
12 LOW RANK NONCONVEX QUADRATIC PROGRAMMING 325 |
12.1 Concave Quadratic Programming Problems and Bilinear Programming Problems 326 |
12.2 Low Rank Concave Quadratic Programming Problems 331 |
12.3 Low Rank Bilinear Programming Problems 343 |
12.4 General Low Rank Nonconvex Quadratic Programming Problems 349 |
13 CONTINUOUS LOCATION 353 |
13.1 Unconstrained Location Problems 354 |
13.2 Solving Unconstrained Location Problems 362 |
13.3 Constrained Location Problems 367 |
13.4 Solving General Constrained Location Problems 371 |
14 DESIGN CENTERING AND RELATED GEOMETRIC PROBLEMS 375 |
14.1 Design Centering 375 |
14.2 Related Geometric Problems 389 |
15 MULTIOBJECTIVE AND BILEVEL PROGRAMMING 397 |
15.1 Optimization over the Efficient Set 398 |
15.2 Bilevel Linear Programming 408 |
15.3 Relationship between Monotonic, Multiobjective and Bilevel Programming 423 |
REFERENCES 427 |
INDEX 455 |
PREFACE |
Part I FOUNDATIONS 1 |
1 SCOPE OF GLOBAL OPTIMIZATION 3 |