Mathematical Theory of Optimization

Front Cover
Ding-Zhu Du, Panos M. Pardalos, Weili Wu
Springer Science & Business Media, Oct 31, 2001 - Computers - 273 pages
Optimization is of central importance in all sciences. Nature inherently seeks optimal solutions. For example, light travels through the "shortest" path and the folded state of a protein corresponds to the structure with the "minimum" potential energy. In combinatorial optimization, there are numerous computationally hard problems arising in real world applications, such as floorplanning in VLSI designs and Steiner trees in communication networks. For these problems, the exact optimal solution is not currently real-time computable. One usually computes an approximate solution with various kinds of heuristics. Recently, many approaches have been developed that link the discrete space of combinatorial optimization to the continuous space of nonlinear optimization through geometric, analytic, and algebraic techniques. Many researchers have found that such approaches lead to very fast and efficient heuristics for solving large problems. Although almost all such heuristics work well in practice there is no solid theoretical analysis, except Karmakar's algorithm for linear programming. With this situation in mind, we decided to teach a seminar on nonlinear optimization with emphasis on its mathematical foundations. This book is the result of that seminar. During the last decades many textbooks and monographs in nonlinear optimization have been published. Why should we write this new one? What is the difference of this book from the others? The motivation for writing this book originated from our efforts to select a textbook for a graduate seminar with focus on the mathematical foundations of optimization.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Selected pages

Contents

Optimization Problems
1
12 Floorplanning
8
13 Satisfiability
15
Linear Programming
23
22 Duality
31
23 From Linear to Nonlinear
33
Blind Mans Method
41
31 Unconstrained Optimization
42
93 Huangs Family
143
Powells Conjecture
151
102 Powells Conjecture
154
103 Goldfarbs Method
161
Minimax
167
112 Steiner Trees
175
113 Solution of GilbertPollaks Conjecture
178
Relaxation
187

32 Global Convergence
43
33 Zangwills Theorem
45
Hitting Walls
51
42 Projection on Walls
54
43 Rosens Gradient Projection Method
59
Slope and Path Length
65
51 The First Slope Lemma
66
52 A Property of Line Searches
68
53 Consequences of the First Slope Lemma
72
Average Slope
81
62 The Global Convergence of Rosens Method
85
63 The Third Slope Lemma
93
Inexact Active Constraints
99
72 Rotating Tangent Plane
105
73 Reduced Gradient
112
Efficiency
125
82 Linear Rate
127
83 Kantorovich Inequality
130
Variable Metric Methods
133
92 QuasiNewton Methods
137
122 General Cover Problem
193
123 Rounding with Duality
195
Semidefinite Programming
201
132 Duality
203
133 Semidefinite Relaxation
205
Interior Point Methods
215
142 PrimalDual Affine Scaling
217
143 Central Path
220
From Local to Global
227
151 Convex Envelopes
228
152 Global Optimization Approaches to Discrete Problems
229
153 Nonconvex Quadratic Programming
230
1531 Concave Quadratic Programming
231
1532 PardalosRosen Algorithm Let
233
1533 Indefinite Quadratic Programming
241
Historical Notes
245
Bibliography
255
Index
271
Copyright

Other editions - View all

Common terms and phrases