A First Course in Optimization

✍ Scribed by Charles L. Byrne

• Publisher: Taylor & Francis Group/CRC
• Year: 2014
• Tongue: English
• Leaves: 313
• Edition: 1
• Category: Library

✦ Synopsis

Features

Explains how to find exact and approximate solutions to systems of linear equations
Shows how to use linear programming techniques, iterative methods, and specialized algorithms in various applications
Discusses the importance of speeding up convergence
Presents the necessary mathematical tools and results to provide the proper foundation
Prepares readers to understand how iterative optimization methods are used in inverse problems
Includes exercises at the end of each chapter
Solutions manual available upon qualifying course adoption

Give Your Students the Proper Groundwork for Future Studies in Optimization

A First Course in Optimization is designed for a one-semester course in optimization taken by advanced undergraduate and beginning graduate students in the mathematical sciences and engineering. It teaches students the basics of continuous optimization and helps them better understand the mathematics from previous courses.

The book focuses on general problems and the underlying theory. It introduces all the necessary mathematical tools and results. The text covers the fundamental problems of constrained and unconstrained optimization as well as linear and convex programming. It also presents basic iterative solution algorithms (such as gradient methods and the Newton–Raphson algorithm and its variants) and more general iterative optimization methods.

This text builds the foundation to understand continuous optimization. It prepares students to study advanced topics found in the author’s companion book, Iterative Optimization in Inverse Problems, including sequential unconstrained iterative optimization methods.

✦ Table of Contents

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

✦ Subjects

Математика;Методы оптимизации;