## Mathematical Theory of OptimizationDing-Zhu Du, Panos M. Pardalos, Weili Wu 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.

### 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 |

255 | |

271 | |

### Other editions - View all

Mathematical Theory of Optimization Ding-Zhu Du,Panos M. Pardalos,Weili Wu No preview available - 2013 |

### Common terms and phrases

active constraint algorithm approximation bounded Broyden's family cluster point compute concave concave function Consider continuously differentiable contradiction convex envelope Corollary counterexample Denote DFP method edge eigenvalues exact line search exists a subsequence f(xk feasible basis feasible point feasible region feasible solution Fritz John global convergence gradient projection Hence Hkyk index set infinite sequence initial point iteration Karmarkar's algorithm Kuhn-Tucker point line search procedure linear programming linearly independent matrix maximal maximum minimax minimize minimum point minimum spanning tree Newton's method normal line search Note objective function obtain optimal solution optimization problems point-to-set mapping polyhedron positive number Proof prove quadratic programming quasi-Newton methods reduced gradient method Rosen's method satisfying search direction semidefinite programming sequence of points sequence xk slope lemma solving spectrahedron stationary point Steiner tree problem subset Suppose topology vector vertex cover