An Introduction to Optimization, 2nd Edition

by Edwin K. P. Chong (Colorado State University); Stanislaw H. Zak (Purdue University)

• ISBN13: 9780471391265
• ISBN10: 0471391263
• Edition: 2nd
• Format: Hardcover
• Copyright: 2001-08-01
• Publisher: Wiley-Interscience

Summary

An Instructor's Manual presenting detailed solutions to all the problems in the book is available from the Wiley editorial department.

Author Biography

EDWIN K. P. CHONG, PhD, is Professor of Electrical and Computer Engineering at Colorado State University, Fort Collins, Colorado. He was an Associate Editor for the IEEE Transactions on Automatic Control and received the 1998 ASEE Frederick Emmons Terman Award.

Table of Contents

Preface	xiii
Part I Mathematical Review
Methods of Proof and Some Notation	1	(4)
Methods of Proof	1	(2)
Notation	3	(2)
Exercises	4	(1)
Vector Spaces and Matrices	5	(16)
Real Vector Spaces	5	(5)
Rank of a Matrix	10	(4)
Linear Equations	14	(2)
Inner Products and Norms	16	(5)
Exercises	19	(2)
Transformations	21	(18)
Linear Transformations	21	(1)
Eigenvalues and Eigenvectors	22	(3)
Orthogonal Projections	25	(1)
Quadratic Forms	26	(5)
Matrix Norms	31	(8)
Exercises	35	(4)
Concepts from Geometry	39	(10)
Line Segments	39	(1)
Hyperplanes and Linear Varieties	39	(3)
Convex Sets	42	(2)
Neighborhoods	44	(1)
Polytopes and Polyhedra	45	(4)
Exercises	47	(2)
Elements of Calculus	49	(24)
Sequences and Limits	49	(6)
Differentiability	55	(2)
The Derivative Matrix	57	(2)
Differentiation Rules	59	(1)
Level Sets and Gradients	60	(4)
Taylor Series	64	(9)
Exercises	68	(5)
Part II Unconstrained Optimization
Basics of Set-Constrained and Unconstrained Optimization	73	(18)
Introduction	73	(2)
Conditions for Local Minimizers	75	(16)
Exercises	83	(8)
One-Dimensional Search Methods	91	(22)
Golden Section Search	91	(4)
Fibonacci Search	95	(8)
Newton's Method	103	(3)
Secant Method	106	(2)
Remarks on Line Search Methods	108	(5)
Exercises	109	(4)
Gradient Methods	113	(26)
Introduction	113	(2)
The Method of Steepest Descent	115	(7)
Analysis of Gradient Methods	122	(17)
Convergence	122	(7)
Convergence Rate	129	(5)
Exercises	134	(5)
Newton's Method	139	(12)
Introduction	139	(3)
Analysis of Newton's Method	142	(3)
Levenberg-Marquardt Modification	145	(1)
Newton's Method for Nonlinear Least-Squares	146	(5)
Exercises	149	(2)
Conjugate Direction Methods	151	(16)
Introduction	151	(2)
The Conjugate Direction Algorithm	153	(5)
The Conjugate Gradient Algorithm	158	(3)
The Conjugate Gradient Algorithm for Non-Quadratic Problems	161	(6)
Exercises	164	(3)
Quasi-Newton Methods	167	(20)
Introduction	167	(1)
Approximating the Inverse Hessian	168	(3)
The Rank One Correction Formula	171	(5)
The DFP Algorithm	176	(4)
The BFGS Algorithm	180	(7)
Exercises	184	(3)
Solving Ax = b	187	(32)
Least-Squares Analysis	187	(9)
Recursive Least-Squares Algorithm	196	(3)
Solution to Ax = b Minimizing ∥x∥	199	(2)
Kaczmarz's Algorithm	201	(3)
Solving Ax = b in General	204	(15)
Exercises	212	(7)
Unconstrained Optimization and Neural Networks	219	(18)
Introduction	219	(2)
Single-Neuron Training	221	(3)
Backpropagation Algorithm	224	(13)
Exercises	234	(3)
Genetic Algorithms	237	(18)
Basic Description	237	(6)
Chromosomes and Representation Schemes	238	(1)
Selection and Evolution	238	(5)
Analysis of Genetic Algorithms	243	(5)
Real-Number Genetic Algorithms	248	(7)
Exercises	250	(5)
Part III Linear Programming
Introduction to Linear Programming	255	(32)
A Brief History of Linear Programming	255	(2)
Simple Examples of Linear Programs	257	(6)
Two-Dimensional Linear Programs	263	(1)
Convex Polyhedra and Linear Programming	264	(3)
Standard Form Linear Programs	267	(5)
Basic Solutions	272	(4)
Properties of Basic Solutions	276	(3)
A Geometric View of Linear Programs	279	(8)
Exercises	282	(5)
Simplex Method	287	(34)
Solving Linear Equations Using Row Operations	287	(7)
The Canonical Augmented Matrix	294	(1)
Updating the Augmented Matrix	295	(2)
The Simplex Algorithm	297	(6)
Matrix Form of the Simplex Method	303	(4)
The Two-Phase Simplex Method	307	(3)
The Revised Simplex Method	310	(11)
Exercises	315	(6)
Duality	321	(18)
Dual Linear Programs	321	(7)
Properties of Dual Problems	328	(11)
Exercises	333	(6)
Non-Simplex Methods	339	(26)
Introduction	339	(1)
Khachiyan's Method	340	(3)
Affine Scaling Method	343	(5)
Basic Algorithm	343	(4)
Two-Phase Method	347	(1)
Karmarkar's Method	348	(17)
Basic Ideas	348	(1)
Karmarkar's Canonical Form	349	(2)
Karmarkar's Restricted Problem	351	(1)
From General Form to Karmarkar's Canonical Form	352	(4)
The Algorithm	356	(4)
Exercises	360	(5)
Part IV Nonlinear Constrained Optimization
Problems with Equality Constraints	365	(32)
Introduction	365	(1)
Problem Formulation	366	(2)
Tangent and Normal Spaces	368	(6)
Lagrange Condition	374	(10)
Second-Order Conditions	384	(3)
Minimizing Quadratics Subject to Linear Constraints	387	(10)
Exercises	391	(6)
Problems with Inequality Constraints	397	(20)
Karush-Kuhn-Tucker Condition	397	(9)
Second-Order Conditions	406	(11)
Exercises	410	(7)
Convex Optimization Problems	417	(22)
Introduction	417	(2)
Convex Functions	419	(8)
Convex Optimization Problems	427	(12)
Exercises	433	(6)
Algorithms for Constrained Optimization	439	(16)
Introduction	439	(1)
Projections	439	(2)
Projected Gradient Methods	441	(4)
Penalty Methods	445	(10)
Exercises	451	(4)
References	455	(7)
Index	462