Simplicial Algorithms for Minimizing Polyhedral Functions

by M. R. Osborne

• ISBN13: 9780521791335
• ISBN10: 0521791332
• Format: Hardcover
• Copyright: 2001-01-08
• Publisher: Cambridge University Press
• More Book Details

Summary

This book provides the first general account of the development of simplicial algorithms. These include the ubiquitous simplex method of linear programming, widely used in industrial optimization and strategic decision making. They also include methods important in data analysis, such as problems involving very large data sets. The theoretical development is based on a new way of representing the underlying geometry of polyhedra functions (functions whose graphs are made up of plane faces), and is capable of resolving problems which occur when combinatorially large numbers of faces intersect at each vertex.

Table of Contents

Preface	ix
Notation	xiii
Some Basic Convex Analysis	1	(42)
The Problem Domain	1	(4)
Properties of Convex Sets	5	(8)
Theorems of the Alternative	13	(2)
Convex Functions	15	(8)
Generalization of the Subdifferential	23	(3)
Conditions for Optimality	26	(7)
Conjugate Convex Functions and Duality	33	(10)
Fenchel Duality	36	(3)
Lagrangian Duality	39	(4)
Introduction to Polyhedral Functions	43	(48)
Introduction	43	(4)
Conjugacy Properties of Basic PCFs	47	(3)
Linear Programming Problems	50	(9)
Separable, Piecewise Linear Problems	59	(4)
Problems of Simple Structure	61	(1)
Problems of Complex Structure	62	(1)
Conjugacy and Duality in the Rank Regression Problem	63	(1)
Structure Functional Description of PCFs	64	(18)
Toward a Compact Notation	64	(2)
Introducting Structure Functionals	66	(7)
Representation of the Subdifferential	73	(9)
Testing for Optimality	82	(2)
Nonconvex Problems	84	(7)
Linear Programming Algorithms	91	(31)
Introduction	91	(3)
Selection of an Initial Feasible Point	94	(2)
The Basic Descent Algorithms	96	(13)
The Reduced Gradient Algorithm	96	(5)
The Projected Gradient Algorithm	101	(2)
Some Implementation Questions	103	(6)
Degeneracy	109	(10)
Resolution of Degeneracy	111	(2)
Numerical Experience	113	(2)
A Method without Degeneracy	115	(4)
Homotopy in Linear Programming	119	(3)
Piecewise Linear Separable Problems	122	(44)
Introduction	122	(3)
The Reduced Gradient Algorithm	125	(8)
A Special Case	131	(2)
Linesearch	133	(6)
Degeneracy	139	(1)
Numerical Examples	140	(7)
Experiments with Problems of Complex Structure	140	(4)
The Secant Algorithm for Problems of Simple Structure	144	(3)
Special Methods for Regression Quantiles	147	(12)
Development of the Basic Homotopy	147	(6)
Boundary Conditions on the Homotopy	153	(3)
Numerical Experience	156	(3)
A Nonconvex Problem	159	(7)
Rank Regression Problems	166	(30)
Introduction	166	(3)
Applications of Asymptotic Linearity	169	(4)
Secant Algorithm	169	(3)
Constructing an Initial Estimate	172	(1)
The Simplicial Algorithms	173	(12)
A Reduced Gradient Algorithm	173	(5)
Resolution of Degeneracy	178	(1)
Programming Considerations	179	(6)
The Nonconvex Case of Redescending Scores	185	(5)
Results of Computations	190	(6)
Polyhedral Constrained Optimization	196	(43)
Introduction	196	(3)
The Lasso	199	(12)
The Problem	199	(1)
Properties of the Lasso	200	(2)
The Descent Algorithm	202	(4)
Homotopy	206	(5)
Trust Region Methods	211	(8)
The Norm Constrained Trust Region Algorithm	211	(5)
Trust Region Properties for Small &kapa;	216	(1)
Necessary Conditions for l1 and l∞ Constraints	217	(2)
Problems in Lagrangian Form	219	(6)
Introduction	219	(2)
A Descent Algorithm	221	(4)
Computational Aspects	225	(14)
On Problem Scaling	225	(1)
Implementation	226	(6)
Numerical Results	232	(7)
Bibliography	239	(4)
Index	243