Mathematical Theory of Optimization

by Du, Dingzhu; Pardalos, Panos M.; Wu, Weili

• ISBN13: 9781402000157
• ISBN10: 1402000154
• Format: Hardcover
• Copyright: 2001-10-01
• Publisher: Kluwer Academic Pub

Summary

This book provides an introduction to the mathematical theory of optimization. It emphasizes the convergence theory of nonlinear optimization algorithms and applications of nonlinear optimization to combinatorial optimization. It includes recent developments in global convergence, the Powell conjecture, semidefinite programming, and relaxation techniques for designs of approximation solutions of combinatorial optimization problems. Audience: The book can be a textbook or useful reference for undergraduate and graduate students in applied mathematics, operations research, and computer science.

Table of Contents

Preface	xi
Optimization Problems	1	(22)
Introduction	1	(7)
Floorplanning	8	(7)
Satisfiability	15	(8)
Linear Programming	23	(18)
Simplex Method	23	(8)
Duality	31	(2)
From Linear to Nonlinear	33	(8)
Blind Man's Method	41	(10)
Unconstrained Optimization	42	(1)
Global Convergence	43	(2)
Zangwill's Theorem	45	(6)
Hitting Walls	51	(14)
Linearly Constrainted Optimization	51	(3)
Projection on Walls	54	(5)
Rosen's Gradient Projection Method	59	(6)
Slope and Path Length	65	(16)
The First Slope Lemma	66	(2)
A Property of Line Searches	68	(4)
Consequences of the First Slope Lemma	72	(9)
Average Slope	81	(18)
The Second Slope Lemma	81	(4)
The Global Convergence of Rosen's Method	85	(8)
The Third Slope Lemma	93	(6)
Inexact Active Constraints	99	(26)
Gradient Projection	99	(6)
Rotating Tangent Plane	105	(7)
Reduced Gradient	112	(13)
Efficiency	125	(8)
Rate of Convergence	125	(2)
Linear Rate	127	(3)
Kantorovich Inequality	130	(3)
Variable Metric Methods	133	(18)
Newton's Method	133	(4)
Quasi-Newton Methods	137	(6)
Huang's Family	143	(8)
Powell's Conjecture	151	(16)
Inverse and Eigenvalues	151	(3)
Powell's Conjecture	154	(7)
Goldfarb's Method	161	(6)
Minimax	167	(20)
Optimality Condition	167	(8)
Steiner Trees	175	(3)
Solution of Gilbert-Pollak's Conjecture	178	(9)
Relaxation	187	(14)
Vertex Cover and MIN 2SAT	187	(6)
General Cover Problem	193	(2)
Rounding with Duality	195	(6)
Semidefinite Programming	201	(14)
Spectrahedron	201	(2)
Duality	203	(2)
Semidefinite Relaxation	205	(10)
Interior Point Methods	215	(12)
Affine Scaling	215	(2)
Primal-Dual Affine Scaling	217	(3)
Central Path	220	(7)
From Local to Global	227	(18)
Convex Envelopes	228	(1)
Global Optimization Approaches to Discrete Problems	229	(1)
Nonconvex Quadratic Programming	230	(15)
Concave Quadratic Programming	231	(2)
Pardalos-Rosen Algorithm	233	(8)
Indefinite Quadratic Programming	241	(4)
Historical Notes	245	(10)
Bibliography	255	(16)
Index	271