A First Course in Optimization

Cover

S Title

A First Course in Optimization

© 2015 by Taylor & Francis Group LLC
ISBN 978-1-4822-2658-4 (eBook - PDF)

Dedication

Contents

Preface

Overview

1. Optimization Without Calculus
1.1 Chapter Summary
1.2 The Arithmetic Mean-Geometric Mean Inequality
1.3 Applying the AGM Inequality: the Number e
1.4 Extending the AGM Inequality
1.5 Optimization Using the AGM Inequality
1.6 The H older and Minkowski Inequalities
1.6.1 H older's Inequality
1.6.2 Minkowski's Inequality
1.7 Cauchy's Inequality
1.8 Optimizing Using Cauchy's Inequality
1.9 An Inner Product for Square Matrices
1.10 Discrete Allocation Problems
1.11 Exercises

2. Geometric Programming
2.1 Chapter Summary
2.2 An Example of a GP Problem
2.3 Posynomials and the GP Problem
2.4 The Dual GP Problem
2.5 Solving the GP Problem
2.6 Solving the DGP Problem
2.6.1 The MART
2.6.2 MART I
2.6.3 MART II
2.6.4 Using the MART to Solve the DGP Problem
2.7 Constrained Geometric Programming
2.8 Exercises

3. Basic Analysis
3.1 Chapter Summary
3.2 Minima and In ma
3.3 Limits
3.4 Completeness
3.5 Continuity
3.6 Limsup and Liminf
3.7 Another View
3.8 Semi-Continuity
3.9 Exercises

4. Convex Sets
4.1 Chapter Summary
4.2 The Geometry of Real Euclidean Space
4.2.1 Inner Products
4.2.2 Cauchy's Inequality
4.2.3 Other Norms
4.3 A Bit of Topology
4.4 Convex Sets in RJ
4.4.1 Basic De nitions
4.4.2 Orthogonal Projection onto Convex Sets
4.5 More on Projections
4.6 Linear and A ne Operators on RJ
4.7 The Fundamental Theorems
4.7.1 Basic De nitions
4.7.2 The Separation Theorem
4.7.3 The Support Theorem
4.8 Block-Matrix Notation
4.9 Theorems of the Alternative
4.10 Another Proof of Farkas' Lemma
4.11 Gordan's Theorem Revisited
4.12 Exercises

5. Vector Spaces and Matrices
5.1 Chapter Summary
5.2 Vector Spaces
5.3 Basic Linear Algebra
5.3.1 Bases and Dimension
5.3.2 The Rank of a Matrix
5.3.3 The \Matrix Inversion Theorem
5.3.4 Systems of Linear Equations
5.3.5 Real and Complex Systems of Linear Equations
5.4 LU and QR Factorization
5.5 The LU Factorization
5.5.1 A Shortcut
5.5.2 A Warning!
5.5.3 The QR Factorization and Least Squares
5.6 Exercises

6. Linear Programming
6.1 Chapter Summary
6.2 Primal and Dual Problems
6.2.1 An Example
6.2.2 Canonical and Standard Forms
6.2.3 From Canonical to Standard and Back
6.3 Converting a Problem to PS Form
6.4 Duality Theorems
6.4.1 Weak Duality
6.4.2 Primal-Dual Methods
6.4.3 Strong Duality
6.5 A Basic Strong Duality Theorem
6.6 Another Proof
6.7 Proof of Gale's Strong Duality Theorem
6.8 Some Examples
6.8.1 The Diet Problem
6.8.2 The Transport Problem
6.9 The Simplex Method
6.10 Yet Another Proof
6.11 The Sherman{Morrison{Woodbury Identity
6.12 An Example of the Simplex Method
6.13 Another Example
6.14 Some Possible Di culties
6.14.1 A Third Example
6.15 Topics for Projects
6.16 Exercises

7. Matrix Games and Optimization
7.1 Chapter Summary
7.2 Two-Person Zero-Sum Games
7.3 Deterministic Solutions
7.3.1 Optimal Pure Strategies
7.4 Randomized Solutions
7.4.1 Optimal Randomized Strategies
7.4.2 An Exercise
7.4.3 The Min-Max Theorem
7.5 Symmetric Games
7.5.1 An Example of a Symmetric Game
7.5.2 Comments on the Proof of the Min-Max Theorem
7.6 Positive Games
7.6.1 Some Exercises
7.6.2 Comments
7.7 Example: The \Blu ng" Game
7.8 Learning the Game
7.8.1 An Iterative Approach
7.8.2 An Exercise
7.9 Non-Constant-Sum Games
7.9.1 The Prisoners' Dilemma
7.9.2 Two Payo Matrices Needed
7.9.3 An Example: Illegal Drugs in Sports

8. Differentiation
8.1 Chapter Summary
8.2 Directional Derivative
8.2.1 De nitions
8.3 Partial Derivatives
8.4 Some Examples
8.5 G^ateaux Derivative
8.6 Fr echet Derivative
8.6.1 The De nition
8.6.2 Properties of the Fr echet Derivative
8.7 The Chain Rule
8.8 Exercises

9. Convex Functions
9.1 Chapter Summary
9.2 Functions of a Single Real Variable
9.2.1 Fundamental Theorems
9.2.2 Proof of Rolle's Theorem
9.2.3 Proof of the Mean Value Theorem
9.2.4 A Proof of the MVT for Integrals
9.2.5 Two Proofs of the EMVT
9.2.6 Lipschitz Continuity
9.2.7 The Convex Case
9.3 Functions of Several Real Variables
9.3.1 Continuity
9.3.2 Di erentiability
9.3.3 Second Di erentiability
9.3.4 Finding Maxima and Minima
9.3.5 Solving F(x) = 0 through Optimization
9.3.6 When Is F(x) a Gradient?
9.3.7 Lower Semi-Continuity
9.3.8 The Convex Case
9.4 Sub-Di erentials and Sub-Gradients
9.5 Sub-Gradients and Directional Derivatives
9.5.1 Some De nitions
9.5.2 Sub-Linearity
9.5.3 Sub-Di erentials and Directional Derivatives
9.5.4 An Example
9.6 Functions and Operators
9.7 Convex Sets and Convex Functions
9.8 Exercises

10. Convex Programming
10.1 Chapter Summary
10.2 The Primal Problem
10.2.1 The Perturbed Problem
10.2.2 The Sensitivity Vector and the Lagrangian
10.3 From Constrained to Unconstrained
10.4 Saddle Points
10.4.1 The Primal and Dual Problems
10.4.2 The Main Theorem
10.4.3 A Duality Approach to Optimization
10.5 The Karush{Kuhn{Tucker Theorem
10.5.1 Su cient Conditions
10.5.2 The KKT Theorem: Saddle-Point Form
10.5.3 The KKT Theorem: The Gradient Form
10.6 On Existence of Lagrange Multipliers
10.7 The Problem of Equality Constraints
10.7.1 The Problem
10.7.2 The KKT Theorem for Mixed Constraints
10.7.3 The KKT Theorem for LP
10.7.4 The Lagrangian Fallacy
10.8 Two Examples
10.8.1 A Linear Programming Problem
10.8.2 A Nonlinear Convex Programming Problem
10.9 The Dual Problem
10.9.1 When Is MP = MD?
10.9.2 The Primal-Dual Method
10.9.3 Using the KKT Theorem
10.10 Nonnegative Least-Squares Solutions
10.11 An Example in Image Reconstruction
10.12 Solving the Dual Problem
10.12.1 The Primal and Dual Problems
10.12.2 Hildreth’s Dual Algorithm
10.13 Minimum One-Norm Solutions
10.13.1 Reformulation as an LP Problem
10.13.2 Image Reconstruction
10.14 Exercises

11. Iterative Optimization
11.1 Chapter Summary
11.2 The Need for Iterative Methods
11.3 Optimizing Functions of a Single Real Variable
11.4 Iteration and Operators
11.5 The Newton{Raphson Approach
11.5.1 Functions of a Single Variable
11.5.2 Functions of Several Variables
11.6 Approximate Newton{Raphson Methods
11.6.1 Avoiding the Hessian Matrix
11.6.2 The BFGS Method
11.6.3 The Broyden Class
11.6.4 Avoiding the Gradient
11.7 Derivative-Free Methods
11.7.1 Multi-Directional Search Algorithms
11.7.2 The Nelder{Mead Algorithm
11.7.3 Comments on the Nelder{Mead Algorithm

12. Solving Systems of Linear Equations
12.1 Chapter Summary
12.2 Arbitrary Systems of Linear Equations
12.2.1 Under-Determined Systems of Linear Equations
12.2.2 Over-Determined Systems of Linear Equations
12.2.3 Landweber's Method
12.2.4 The Projected Landweber Algorithm
12.2.5 The Split-Feasibility Problem
12.2.6 An Extension of the CQ Algorithm
12.2.7 The Algebraic Reconstruction Technique
12.2.8 Double ART
12.3 Regularization
12.3.1 Norm-Constrained Least-Squares
12.3.2 Regularizing Landweber's Algorithm
12.3.3 Regularizing the ART
12.4 Nonnegative Systems of Linear Equations
12.4.1 The Multiplicative ART
12.4.2 MART I
12.4.3 MART II
12.4.4 The Simultaneous MART
12.4.5 The EMML Iteration
12.4.6 Alternating Minimization
12.4.7 The Row-Action Variant of EMML
12.4.8 EMART I
12.4.9 EMART II
12.5 Regularized SMART and EMML
12.5.1 Regularized SMART
12.5.2 Regularized EMML
12.6 Block-Iterative Methods
12.7 Exercises

13. Conjugate-Direction Methods
13.1 Chapter Summary
13.2 Iterative Minimization
13.3 Quadratic Optimization
13.4 Conjugate Bases for RJ
13.4.1 Conjugate Directions
13.4.2 The Gram{Schmidt Method
13.5 The Conjugate Gradient Method
13.5.1 The Main Idea
13.5.2 A Recursive Formula
13.6 Krylov Subspaces
13.7 Extensions of the CGM
13.8 Exercises

14. Operators
14.1 Chapter Summary
14.2 Operators
14.3 Contraction Operators
14.3.1 Lipschitz-Continuous Operators
14.3.2 Nonexpansive Operators
14.3.3 Strict Contractions
14.3.4 Eventual Strict Contractions
14.3.5 Instability
14.4 Orthogonal-Projection Operators
14.4.1 Properties of the Operator PC
14.4.2 PC Is Nonexpansive
14.4.3 PC Is Firmly Nonexpansive
14.4.4 The Search for Other Properties of PC
14.5 Two Useful Identities
14.6 Averaged Operators
14.7 Gradient Operators
14.8 The Krasnosel'skii{Mann{Opial Theorem
14.9 A ne-Linear Operators
14.10 Paracontractive Operators
14.10.1 Linear and A ne Paracontractions
14.10.2 The Elsner{Koltracht{Neumann Theorem
14.11 Matrix Norms
14.11.1 Induced Matrix Norms
14.11.2 Condition Number of a Square Matrix
14.11.3 Some Examples of Induced Matrix Norms
14.11.4 The Euclidean Norm of a Square Matrix
14.12 Exercises

15. Looking Ahead
15.1 Chapter Summary
15.2 Sequential Unconstrained Minimization
15.3 Examples of SUM
15.3.1 Barrier-Function Methods
15.3.2 Penalty-Function Methods
15.4 Auxiliary-Function Methods
15.4.1 General AF Methods
15.4.2 AF Requirements
15.5 The SUMMA Class of AF Methods

Bibliography

Back Cover