# An Introduction to Optimization, Fourth Edition

## Contents

Preface

### Part I. Mathematical Review

1 Methods of Proof and Some Notation
1.1 Methods of Proof
1.2 Notation
2 Vector Spaces and Matrices
2.1 Vector and Matrix
2.2 Rank of a Matrix
2.3 Linear Equations
2.4 Inner Products and Norms
3 Transformations
3.1 Linear Transformations
3.2 Eigenvalues and Eigenvectors
3.3 Orthogonal Projections
3.5 Matrix Norms
4 Concepts from Geometry
4.1 Line Segments
4.2 Hyperplanes and Linear Varieties
4.3 Convex Sets
4.4 Neighborhoods
4.5 Polytopes and Polyhedra
5 Elements of Calculus
5.1 Sequences and Limits
5.2 Differentiability
5.3 The Derivative Matrix
5.4 Differentiation Rules
5.6 Taylor Series

### Part II. Unconstrained Optimization

6 Basics of Set-Constrained and Unconstrained Optimization
6.1 Introduction
6.2 Conditions for Local Minimizers
7 One-Dimensional Search Methods
7.1 Introduction
7.2 Golden Section Search
7.3 Fibonacci Method
7.4 Bisection Method
7.5 Newton's Method
7.6 Secant Method
7.7 Bracketing
7.8 Line Search in Multidimensional Optimization
8.1 Introduction
8.2 The Method of Steepest Descent
9 Newton's Method
9.1 Introduction
9.2 Analysis of Newton's Method
9.3 Levenberg-Marquardt Modification
9.4 Newton's Method for Nonlinear Least-Squares
10 Conjugate Direction Methods
10.1 Introduction
10.2 The Conjugate Direction Algorithm
11 Quasi-Newton Methods
11.1 Introduction
11.2 Approximating the Inverse Hessian
11.3 The Rank One Correction Formula
11.4 The DFP Algorithm
11.5 The BFGS Algorithm
12 Solving Linear Equations
12.1 Least-Squares Analysis
12.2 The Recursive Least-Squares Algorithm
12.3 Solution to Linear Equation with Minimum Norm
12.4 Kaczmarz's Algorithm
12.5 Solving Linear Equations in General
13 Unconstrained Optimization and Neural Networks
13.1 Introduction
13.2 Single-Neuron Training
13.3 The Backpropagation Algorithm
14 Global Search Algorithms
14.1 Introduction
14.3 Simulated Annealing
14.4 Particle Swarm Optimization
14.5 Genetic Algorithms

### Part III. Linear Programming

15 Introduction to Linear Programming
15.1 Brief History of Linear Programming
15.2 Simple Examples of Linear Programs
15.3 Two-Dimensional Linear Programs
15.4 Convex Polyhedra and Linear Programming
15.5 Standard Form Linear Programs
15.6 Basic Solutions
15.7 Properties of Basic Solutions
15.8 Geometric View of Linear Programs
16 Simplex Method
16.1 Solving Linear Equations Using Row Operations
16.2 The Canonical Augmented Matrix
16.3 Updating the Augmented Matrix
16.4 The Simplex Algorithm
16.5 Matrix Form of the Simplex Method
16.6 Two-Phase Simplex Method
16.7 Revised Simplex Method
17 Duality
17.1 Dual Linear Programs
17.2 Properties of Dual Problems
18 Nonsimplex Methods
18.1 Introduction
18.2 Khachiyan's Method
18.3 Affine Scaling Method
18.4 Karmarkar's Method
19 Integer Linear Programming
19.1 Introduction
19.2 Unimodular Matrices
19.3 The Gomory Cutting-Plane Method

### Part IV. Nonlinear Constrained Optimization

20 Problems with Equality Constraints
20.1 Introduction
20.2 Problem Formulation
20.3 Tangent and Normal Spaces
20.4 Lagrange Condition
20.5 Second-Order Conditions
20.6 Minimizing Quadratics Subject to Linear Constraints
21 Problems With Inequality Constraints
21.1 Karush-Kuhn-Tucker Conditions
21.2 Second-Order Conditions
22 Convex Optimization Problems
22.1 Introduction
22.2 Convex Functions
22.3 Convex Optimization Problems
22.4 Semidefinite Programming
23 Algorithms for Constrained Optimization
23.1 Introduction
23.2 Projections
23.3 Projected Gradient Methods with Linear Constraints
23.4 Lagrangian Algorithms
23.5 Penalty Methods
24 Multiobjective Optimization
24.1 Introduction
24.2 Pareto Solutions
24.3 Computing the Pareto Front
24.4 From Multiobjective to Single-Objective Optimization
24.5 Uncertain Linear Programming Problems
References
Index

Professor Edwin K. P. Chong,