Convex Analysis and Global OptimizationDue to the general complementary convex structure underlying most nonconvex optimization problems encountered in applications, convex analysis plays an essential role in the development of global optimization methods. This book develops a coherent and rigorous theory of deterministic global optimization from this point of view. Part I constitutes an introduction to convex analysis, with an emphasis on concepts, properties and results particularly needed for global optimization, including those pertaining to the complementary convex structure. Part II presents the foundation and application of global search principles such as partitioning and cutting, outer and inner approximation, and decomposition to general global optimization problems and to problems with a low-rank nonconvex structure as well as quadratic problems. Much new material is offered, aside from a rigorous mathematical development. Audience: The book is written as a text for graduate students in engineering, mathematics, operations research, computer science and other disciplines dealing with optimization theory. It is also addressed to all scientists in various fields who are interested in mathematical optimization. |
Nội dung
CONVEX SETS | 3 |
12 Convex Sets | 6 |
13 relative Interior and Closure | 8 |
14 Convex Hull | 13 |
17 Representation of Convex Sets | 26 |
18 Polars of Convex Sets | 28 |
19 Polyhedral Convex Sets | 30 |
110 Exercises | 38 |
49 Exercises | 130 |
SUCCESSIVE PARTITIONING METHOD | 133 |
52 Concavity Cuts | 136 |
53 Subdivision Processes | 140 |
54 Procedure DC | 146 |
55 Branch and Select Algorithms | 153 |
56 Rectangular Algorithms | 159 |
57 Reverse Convex Programming | 164 |
CONVEX FUNCTIONS | 41 |
22 Convexity Preserving Operations | 46 |
23 Lower SemiContinuity | 50 |
24 Lipschitz Continuity | 54 |
25 Convex Inequalities | 56 |
26 Approximation by Affine Functions | 60 |
27 Subdifferential | 62 |
28 Subdifferential Calculus | 67 |
29 Approximate Subdifferential | 69 |
210 Conjugate Functions | 72 |
211 Extremal Values of Convex Functions | 74 |
212 SaddleFunctions and Minimax | 77 |
213 Exercises | 80 |
DC FUNCTIONS AND DC SETS | 83 |
32 University of DC Functions | 85 |
33 DC Representation of Basic Composite Functions | 88 |
35 DC Representation of Polynomials | 93 |
36 DC Sets | 95 |
37 Convex Minorants of a DC Function | 100 |
38 The Minimum of a DC Function | 103 |
39 Exercises | 105 |
GLOBAL OPTIMIZATION | 107 |
MOTIVATION AND OVERVIEW | 109 |
42 Multiextrenality in the Real World | 110 |
43 Basic Classes of Nonconvex Problems | 115 |
44 General Nonconvex Structure | 117 |
46 DC Inclusion Associated with a Feasible Solution | 122 |
47 Approximate Solution | 123 |
48 When Global Optimization Motivated? | 125 |
58 Exercises | 174 |
OUTER AND INNER APPROXIMATION | 177 |
62 Concave Minimization Under Convex Constraints | 181 |
63 Canonical DC Programming | 186 |
64 Polyhedral Annexation | 192 |
65 Duality in Global Optimization | 199 |
66 Noncanonical DC Problems | 206 |
67 Continuous Optimization Problems | 211 |
68 Exercises | 220 |
Decomposition | 223 |
72 Decomposition by Projection | 227 |
73 Decomposition by Polyhedral Annexation | 233 |
74 The Parametric Approach | 236 |
75 Linear Multiplicative Programming | 240 |
76 Convex Constraints | 247 |
77 Reverse Convex Constraints | 255 |
78 Network Constraints | 261 |
79 Some PolynomialTime Solvable Problems | 269 |
710 Exercises | 274 |
NONCONVEX QUADRATIC PROGRAMMING | 277 |
82 Quadratic Minimization Over Ellipsoids | 281 |
83 Generalized Linear Programs | 285 |
84 Quadratic Problems with Convex Constraints | 287 |
85 Quadratic Problems with Quadratic Constraints | 293 |
86 Exercises | 316 |
| 319 | |
| 337 | |
Ấn bản in khác - Xem tất cả
Thuật ngữ và cụm từ thông dụng
accumulation point affine function affine set assume basic optimal solution branch and bound closed convex set compute concave function concave minimization convergence convex cone convex hull convex minorant convex program convex set Corollary d.c. function defined Denote exists extreme point f(xº feasible point feasible solution fi(x finite follows function f(x global minimizer global optimal global optimal solution halfline hence hyperplane implies inequality intC iteration K₁ Lemma linear program lower bound LRCP M₁ matrix method min{f(x nonconvex nonempty objective function optimal value optimization problems outer approximation P₁ partition Pk+1 polyhedron polytope Procedure DC Proof Let proper convex function Proposition quadratic function quasiconcave quasiconvex rectangle relative interior reverse convex satisfying sequence simplex solving Step subset Theorem vector vertex set
Đoạn trích phổ biến
Trang 328 - Quasiconjugates of functions, duality relationship between quasiconvex minimization under a reverse convex constraint and quasiconvex maximization under a reverse convex constraint and applications, Journal of Mathematical Analysis and Applications 159 (1991) 199-322.
Trang 329 - An Outer Approximation Method for Globally Minimizing a Concave Function over a Compact Convex Set', Acta Mathematica Vietnamica, 8, 21-40, 1983.
Trang 333 - SW (1982), A Design Centering Algorithm for Nonconvex Regions of Acceptability, IEEE Transactions on Computer- Aided- Design of Integrated Circuits and Systems CAD-1, 13-24.
Trang 329 - A finite algorithm for solving linear programs with an additional reverse convex constraint, Lecture Notes in Economics and Mathematical Systems, 225 ,291-302 (1985).
Trang 333 - A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs — II. Application of Theory and Test Problems. Computers and Chemical Engineering, 14(12), 14191434. Visweswaran, V., and Floudas, CA (1992). Unconstrained and Constrained Global Optimization of Polynomial Functions in One Variable.
Tài liệu tham khảo sách này
Algorithmic Principles of Mathematical Programming Ulrich Faigle,W. Kern,G. Still Không có bản xem trước - 2002 |