Edwin K. P. Chong, Wu-Sheng Lu, and Stanislaw H. Żak
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.4 Quadratic Forms
- 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.5 Level Sets and Gradients
- 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 Gradient Methods
- 8.1 Introduction
- 8.2 Method of Steepest Descent
- 8.3 Analysis of Gradient Methods
- 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 Conjugate Direction Algorithm
- 10.3 Conjugate Gradient Algorithm
- 10.4 Conjugate Gradient Algorithm for Non-Quadratic Problems
- 11 Quasi-Newton Methods
- 11.1 Introduction
- 11.2 Approximating the Inverse Hessian
- 11.3 Rank One Correction Formula
- 11.4 DFP Algorithm
- 11.5 BFGS Algorithm
- 12 Solving Linear Equations
- 12.1 Least-Squares Analysis
- 12.2 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 Backpropagation Algorithm
- 14 Global Search Algorithms
- 14.1 Introduction
- 14.2 Nelder-Mead Simplex Algorithm
- 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
- 17.3 Matrix Games
- 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 Lagrangian Duality
- 23.1 Overview
- 23.2 Notation
- 23.3 Primal–Dual Pair
- 23.4 General Duality Properties
- 23.5 Strong Duality
- 23.6 Convex Case
- 23.7 Summary of Key Results
- 24 Algorithms for Constrained Optimization
- 24.1 Introduction
- 24.2 Projections
- 24.3 Projected Gradient Methods with Linear Constraints
- 24.4 Convergence of Projected Gradient Algorithms
- 24.5 Lagrangian Algorithms
- 24.6 Penalty Methods
- 25 Multiobjective Optimization
- 25.1 Introduction
- 25.2 Pareto Solutions
- 25.3 Computing the Pareto Front
- 25.4 From Multiobjective to Single-Objective Optimization
- 25.5 Uncertain Linear Programming Problems
Part V Optimization in Machine Learning
- 26 Machine Learning Problems and Feature Engineering
- 26.1 Machine Learning Problems
- 26.2 Data Normalization
- 26.3 Histogram of Oriented Gradients
- 26.4 Principal Component Analysis and Linear Autoencoder
- 27 Stochastic Gradient Descent Algorithms
- 27.1 Stochastic Gradient Descent Algorithm
- 27.2 Stochastic Variance Reduced Gradient Algorithm
- 27.3 Distributed Stochastic Variance Reduced Gradient
- 28 Linear Regression and Its Variants
- 28.1 Least-Squares Linear Regression
- 28.2 Model Selection by Cross-Validation
- 28.3 Model Selection by Regularization
- 29 Logistic Regression for Classification
- 29.1 Logistic Regression for Binary Classification
- 29.2 Nonlinear Decision Boundary via Linear Regression
- 29.3 Multicategory Classification
- 30 Support Vector Machines
- 30.1 Hinge-Loss Functions
- 30.2 Classification by Minimizing Hinge Loss
- 30.3 Support Vector Machines for Binary Classification
- 30.4 Support Vector Machines for Multicategory Classification
- 30.5 Kernel Trick
- 31 K-Means Clustering
- 31.1 K-Means Clustering
- 31.2 K-Means++ for Center Initialization
- 31.3 Variants of K-Means Clustering
- 31.4 Image Compression by Vector Quantization and K-Means Clustering
- References
- Index
Professor Edwin K. P. Chong,
