1st Edition

# Numerical Methods and Optimization An Introduction

By Sergiy Butenko, Panos M. Pardalos Copyright 2014
414 Pages 53 B/W Illustrations
by Chapman & Hall

412 Pages
by Chapman & Hall

Also available as eBook on:

For students in industrial and systems engineering (ISE) and operations research (OR) to understand optimization at an advanced level, they must first grasp the analysis of algorithms, computational complexity, and other concepts and modern developments in numerical methods. Satisfying this prerequisite, Numerical Methods and Optimization: An Introduction combines the materials from introductory numerical methods and introductory optimization courses into a single text. This classroom-tested approach enriches a standard numerical methods syllabus with optional chapters on numerical optimization and provides a valuable numerical methods background for students taking an introductory OR or optimization course.

The first part of the text introduces the necessary mathematical background, the digital representation of numbers, and different types of errors associated with numerical methods. The second part explains how to solve typical problems using numerical methods. Focusing on optimization methods, the final part presents basic theory and algorithms for linear and nonlinear optimization.

The book assumes minimal prior knowledge of the topics. Taking a rigorous yet accessible approach to the material, it includes some mathematical proofs as samples of rigorous analysis but in most cases, uses only examples to illustrate the concepts. While the authors provide a MATLAB® guide and code available for download, the book can be used with other software packages.

Basics
Preliminaries
Sets and Functions
Fundamental Theorem of Algebra
Vectors and Linear (Vector) Spaces
Matrices and Their Properties
Preliminaries from Real and Functional Analysis

Numbers and Errors
Conversion between Different Number Systems
Floating Point Representation of Numbers
Definitions of Errors
Round-off Errors

Numerical Methods for Standard Problems
Elements of Numerical Linear Algebra
Direct Methods for Solving Systems of Linear Equations
Iterative Methods for Solving Systems of Linear Equations
Overdetermined Systems and Least Squares Solution
Stability of a Problem
Computing Eigenvalues and Eigenvectors

Solving Equations
Fixed Point Method
Bracketing Methods
Newton’s Method
Secant Method
Solution of Nonlinear Systems

Polynomial Interpolation
Forms of Polynomials
Polynomial Interpolation Methods
Theoretical Error of Interpolation and Chebyshev Polynomials

Numerical Integration
Trapezoidal Rule
Simpson's Rule
Precision and Error of Approximation
Composite Rules
Using Integrals to Approximate Sums

Numerical Solution of Differential Equations
Solution of a Differential Equation
Taylor Series and Picard’s Methods
Euler's Method
Runge-Kutta Methods
Systems of Differential Equations
Higher-Order Differential Equations

Introduction to Optimization
Basic Concepts
Formulating an Optimization Problem
Mathematical Description
Local and Global Optimality
Existence of an Optimal Solution
Convex Sets, Functions, and Problems

Complexity Issues
Algorithms and Complexity
Average Running Time
Randomized Algorithms
Basics of Computational Complexity Theory
Complexity of Local Optimization
Optimal Methods for Nonlinear Optimization

Introduction to Linear Programming
Formulating a Linear Programming Model
Examples of LP Models
Practical Implications of Using LP Models
Solving Two-Variable LPs Graphically
Classification of LPs

The Simplex Method for Linear Programming
The Standard Form of LP
The Simplex Method
Geometry of the Simplex Method
The Simplex Method for a General LP
The Fundamental Theorem of LP
The Revised Simplex Method
Complexity of the Simplex Method

Duality and Sensitivity Analysis in Linear Programming
Defining the Dual LP
Weak Duality and the Duality Theorem
Extracting an Optimal Solution of the Dual LP from an Optimal Tableau of the Primal LP
Correspondence between the Primal and Dual LP Types
Complementary Slackness
Economic Interpretation of the Dual LP
Sensitivity Analysis

Unconstrained Optimization
Optimality Conditions
Optimization Problems with a Single Variable
Algorithmic Strategies for Unconstrained Optimization
Method of Steepest Descent
Newton’s Method
Conjugate Direction Method
Quasi-Newton Methods
Inexact Line Search

Constrained Optimization
Optimality Conditions
Duality
Sequential Unconstrained Minimization

Notes and References

Bibliography

Index

### Biography

Sergiy Butenko, Panos M. Pardalos

"The book is in most parts very well developed and is served by nice illustrations, a fluid style of writing, and a layout that makes it easy to read. … [it will] serve well its purpose of bridging the gap between numerical analysis, operations research, and mathematical optimization for undergraduate students in the applied sciences."
Mathematical Reviews, August 2014

"If you are looking for an enjoyable and useful introduction to the basic topics of numerical methods and optimization, this is the right text to read. The authors are not only experienced lecturers but also active researchers in this area. They present the basic topics of numerical methods and optimization in an easy-to-follow, yet rigorous manner. In particular, they gently introduce some important topics, such as computational complexity, which are usually unavailable in textbooks on optimization for engineers. The authors occasionally turn to mathematical humor (such as ‘There are 10 types of people—those who understand binary, and those who don't’) to illustrate some material in the text. This informal contact with the reader exemplifies the engaging style of exposition characteristic of this excellent book."