Optimization Theory and Methods: Nonlinear Programming

ISBN-13: 9780387249759 / Angielski / Twarda / 2006 / 688 str.

Wenyu Sun; YA-Xiang Yuan

Opis

Optimization Theory and Methods can be used as a textbook for an optimization course for graduates and senior undergraduates. It is the result of the author's teaching and research over the past decade. It describes optimization theory and several powerful methods. For most methods, the book discusses an idea's motivation, studies the derivation, establishes the global and local convergence, describes algorithmic steps, and discusses the numerical performance.

Recenzje

From the reviews:

"The book contains a comprehensive presentation of methods for unconstrained and constrained optimization problems. ... The main strength of the book is the precise convergence analysis of most nonlinear programming algorithms presented, and it is especially comprehensive for line search, Newton, quasi-Newton, trust region and SQP methods. In this respect the book is a very valuable reference." (Darinka Dentcheva, Mathematical Reviews, Issue 2007 c)

"Optimization is a subject that is widely and increasingly used in science, engineering, economics, management, industry, and other areas. ... The book is self-contained, systematic in theory and algorithms, and easy to read. ... The book also contains an extensive ... bibliography with 366 references, which is an important part of the book, and is useful to readers for further studies. Each chapter ends with an exercise set." (Alexandr B. Vasil'ev, Zentralblatt MATH, Vol. 1129 (7), 2008)

Spis treści

Preface 1 Introduction 1.1 Introduction 1.2 Mathematics Foundations 1.2.1 Norm 1.2.2 Inverse and Generalized Inverse of a Matrix 1.2.3 Properties of Eigenvalues 1.2.4 Rank-One Update 1.2.5 Function and Differential 1.3 Convex Sets and Convex Functions 1.3.1 Convex Sets 1.3.2 Convex Functions 1.3.3 Separation and Support of Convex Sets 1.4 Optimality Conditions for Unconstrained Case 1.5 Structure of Optimization Methods Exercises 2 Line Search 2.1 Introduction 2.2 Convergence Theory for Exact Line Search 2.3 Section Methods 2.3.1 The Golden Section Method 2.3.2 The Fibonacci Method 2.4 Interpolation Method 2.4.1 Quadratic Interpolation Methods 2.4.2 Cubic Interpolation Method 2.5 Inexact Line Search Techniques 2.5.1 Armijo and Goldstein Rule 2.5.2 Wolfe-Powell Rule 2.5.3 Goldstein Algorithm and Wolfe-Powell Algorithm 2.5.4 Backtracking Line Search 2.5.5 Convergence Theorems of Inexact Line Search Exercises 3 Newton’s Methods 3.1 The Steepest Descent Method 3.1.1 The Steepest Descent Method 3.1.2 Convergence of the Steepest Descent Method 3.1.3 Barzilai and Borwein Gradient Method 3.1.4 Appendix: Kantorovich Inequality 3.2 Newton’s Method 3.3 Modified Newton’s Method 3.4 Finite-Difference Newton’s Method 3.5 Negative Curvature Direction Method 3.5.1 Gill-Murray Stable Newton’s Method 3.5.2 Fiacco-McCormick Method 3.5.3 Fletcher-Freeman Method 3.5.4 Second-Order Step Rules 3.6 Inexact Newton’s Method Exercises 4 Conjugate Gradient Method 4.1 Conjugate Direction Methods 4.2 Conjugate Gradient Method 4.2.1 Conjugate Gradient Method 4.2.2 Beale’s Three-Term Conjugate Gradient Method 4.2.3 Preconditioned Conjugate Gradient Method 4.3 Convergence of Conjugate Gradient Methods 4.3.1 Global Convergence of Conjugate Gradient Methods 4.3.2 Convergence Rate of Conjugate Gradient Methods Exercises 5 Quasi-Newton Methods 5.1 Quasi-Newton Methods 5.1.1 Quasi-Newton Equation 5.1.2 Symmetric Rank-One (SR1) Update 5.1.3 DFP Update 5.1.4 BFGS Update and PSB Update 5.1.5 The Least Change Secant Update 5.2 The Broyden Class 5.3 Global Convergence of Quasi-Newton Methods 5.3.1 Global Convergence under Exact Line Search 5.3.2 Global Convergence under Inexact Line Search 5.4 Local Convergence of Quasi-Newton Methods 5.4.1 Superlinear Convergence of General Quasi-Newton Methods 5.4.2 Linear Convergence of General Quasi-Newton Methods 5.4.3 Local Convergence of Broyden’s Rank-One Update 5.4.4 Local and Linear Convergence of DFP Method 5.4.5 Superlinear Convergence of BFGS Method 5.4.6 Superlinear Convergence of DFP Method 5.4.7 Local Convergence of Broyden’s Class Methods 5.5 Self-Scaling Variable Metric (SSVM) Methods 5.5.1 Motivation to SSVM Method 5.5.2 Self-Scaling Variable Metric (SSVM) Method 5.5.3 Choices of the Scaling Factor 5.6 Sparse Quasi-Newton Methods 5.7 Limited Memory BFGS Method Exercises 6 Trust-Region and Conic Model Methods 6.1 Trust-Region Methods 6.1.1 Trust-Region Methods 6.1.2 Convergence of Trust-Region Methods 6.1.3 Solving A Trust-Region Subproblem 6.2 Conic Model and Collinear Scaling Algorithm 6.2.1 Conic Model 6.2.2 Generalized Quasi-Newton Equation 6.2.3 Updates that Preserve Past Information 6.2.4 Collinear Scaling BFGS Algorithm 6.3 Tensor Methods 6.3.1 Tensor Method for Nonlinear Equations 6.3.2 Tensor Methods for Unconstrained Optimization Exercises

Blurb

This book, a result of the authors’ teaching and research experience in various universities and institutes over the past ten years, can be used as a textbook for an optimization course for graduates and senior undergraduates. It systematically describes optimization theory and several powerful methods, including recent results. For most methods, the authors discuss an idea’s motivation, study the derivation, establish the global and local convergence, describe algorithmic steps, and discuss the numerical performance. The book deals with both theory and algorithms of optimization concurrently. It also contains an extensive bibliography with 366 references. Finally, apart from its use for teaching, Optimization Theory and Methods is also very beneficial for doing research.

Audience

This book is intended for senior students, graduates, teachers, and researchers in optimization, operations research, computational mathematics, applied mathematics, and some engineering and economics. It will also be useful for scientists in engineering and economics.