Mathematical Theory of Optimization

1. Front Matter

   Pages i-xiii

   PDF

2. Optimization Problems

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 1-21

3. Linear Programming

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 23-40

4. Blind Man’s Method

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 41-50

5. Hitting Walls

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 51-63

6. Slope and Path Length

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 65-79

7. Average Slope

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 81-98

8. Inexact Active Constraints

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 99-123

9. Efficiency

   • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

   Pages 125-132

10. Variable Metric Methods

    • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

    Pages 133-150

11. Powell’s Conjecture

    • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

    Pages 151-166

12. Minimax

    • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

    Pages 167-185

13. Relaxation

    • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

    Pages 187-200

14. Semidefinite Programming

    • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

    Pages 201-213

15. Interior Point Methods

    • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

    Pages 215-226

16. From Local to Global

    • Ding-Zhu Du, Panos M. Pardalos, Weili Wu

    Pages 227-243

17. Back Matter

    Pages 245-273

    PDF

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.

• Computer
• Variable
• algorithms
• combinatorial optimization
• computer science
• linear optimization
• nonlinear optimization
• optimization
• programming

• Department of Computer Science and Engineering, University of Minnesota, Minneapolis, USA

  Ding-Zhu Du, Weili Wu

• Center for Applied Optimization, ISE Department, University of Florida, Gainesville, USA

  Panos M. Pardalos

Policies and ethics