# A First Course in Optimization

## Preview

## Book Description

*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

**Optimization without Calculus **Chapter Summary

The Arithmetic Mean-Geometric Mean Inequality

An Application of the AGM Inequality: the Number e

Extending the AGM Inequality

Optimization Using the AGM Inequality

The Holder and Minkowski Inequalities

Cauchy's Inequality

Optimizing using Cauchy's Inequality

An Inner Product for Square Matrices

Discrete Allocation Problems

**Geometric Programming **Chapter Summary

An Example of a GP Problem

Posynomials and the GP Problem

The Dual GP Problem

Solving the GP Problem

Solving the DGP Problem

Constrained Geometric Programming

**Basic Analysis **Chapter Summary

Minima and Infima

Limits

Completeness

Continuity

Limsup and Liminf

Another View

Semi-Continuity

**Convex Sets **Chapter Summary

The Geometry of Real Euclidean Space

A Bit of Topology

Convex Sets in RJ

More on Projections

Linear and Affine Operators on RJ

The Fundamental Theorems

Block-Matrix Notation

Theorems of the Alternative

Another Proof of Farkas' Lemma

Gordan's Theorem Revisited

**Vector Spaces and Matrices **Chapter Summary

Vector Spaces

Basic Linear Algebra

LU and QR Factorization

The LU Factorization

**Linear Programming **Chapter Summary

Primal and Dual

Converting a Problem to PS Form

Duality Theorems

The Basic Strong Duality Theorem

Another Proof

Proof of Gale's Strong Duality Theorem

Some Examples

The Simplex Method

Yet Another Proof

The Sherman–Morrison–Woodbury Identity

An Example of the Simplex Method

Another Example

Some Possible Difficulties

Topics for Projects

**Matrix Games and Optimization **Chapter Summary

Two-Person Zero-Sum Games

Deterministic Solutions

Randomized Solutions

Symmetric Games

Positive Games

Example: The "Bluffing" Game

Learning the Game

Non-Constant-Sum Games

**Differentiation **Chapter Summary

Directional Derivative

Partial Derivatives

Some Examples

Gâteaux Derivative

Fréchet Derivative

The Chain Rule

**Convex Functions **Chapter Summary

Functions of a Single Real Variable

Functions of Several Real Variables

Sub-Differentials and Sub-Gradients

Sub-Gradients and Directional Derivatives

Functions and Operators

Convex Sets and Convex Functions

**Convex Programming **Chapter Summary

The Primal Problem

From Constrained to Unconstrained

Saddle Points

The Karush–Kuhn–Tucker Theorem

On Existence of Lagrange Multipliers

The Problem of Equality Constraints

Two Examples

The Dual Problem

Nonnegative Least-Squares Solutions

An Example in Image Reconstruction

Solving the Dual Problem

Minimum One-Norm Solutions

**Iterative Optimization**Chapter Summary

The Need for Iterative Methods

Optimizing Functions of a Single Real Variable

The Newton–Raphson Approach

Approximate Newton–Raphson Methods

Derivative-Free Methods

Rates of Convergence

Descent Methods

Optimizing Functions of Several Real Variables

Auxiliary-Function Methods

Projected Gradient-Descent Methods

Feasible-Point Methods

Quadratic Programming

Simulated Annealing

**Solving Systems of Linear Equations **Chapter Summary

Arbitrary Systems of Linear Equations

Regularization

Nonnegative Systems of Linear Equations

Regularized SMART and EMML

Block-Iterative Methods

**Conjugate-Direction Methods**Chapter Summary

Iterative Minimization

Quadratic Optimization

Conjugate Bases for RJ

The Conjugate Gradient Method

Krylov Subspaces

Extensions of the CGM

**Operators **

Chapter Summary

Operators

Contraction Operators

Orthogonal-Projection Operators

Two Useful Identities

Averaged Operators

Gradient Operators

Affine-Linear Operators

Paracontractive Operators

Matrix Norms

**Looking Ahead **Chapter Summary

Sequential Unconstrained Minimization

Examples of SUM

Auxiliary-Function Methods

The SUMMA Class of AF Methods

Bibliography

Index

*Exercises appear at the end of each chapter.*

## Reviews

"This book, split in fifteen chapters, presents a thorough introduction to optimization for undergraduate and graduate courses in science and engineering and forms a useful toolkit of optimization techniques across several domains. … Throughout this very interesting book, a number of solved and unsolved exercises provide the reader with all the necessary tools to understand the techniques and their applicability in real-life problems."

—Zentralblatt MATH1312