Semi-Infinite Programming

by Goberna, Miguel A.; Lopez, Marco A.

• ISBN13: 9781402000324
• ISBN10: 1402000324
• Format: Hardcover
• Copyright: 2001-11-01
• Publisher: Kluwer Academic Pub

Summary

Semi-infinite programming (SIP) deals with optimization problems in which either the number of decision variables or the number of constraints is finite. This book presents the state of the art in SIP in a suggestive way, bringing the powerful SIP tools close to the potential users in different scientific and technological fields. The volume is divided into four parts. Part I reviews the first decade of SIP (1962-1972). Part II analyses convex and generalised SIP, conic linear programming, and disjunctive programming. New numerical methods for linear, convex, and continuously differentiable SIP problems are proposed in Part III. Finally, Part IV provides an overview of the applications of SIP to probability, statistics, experimental design, robotics, optimization under uncertainty, production games, and separation problems. Audience: This book is an indispensable reference and source for advanced students and researchers in applied mathematics and engineering.

Table of Contents

Preface	xi
Contributing Authors	xv
Part I HISTORY
On the 1962-1972 Decade of Semi-Infinite Programming: A Subjective View	3	(42)
Ken O. Kortanek
Introduction: Origins of a theory	4	(3)
Generalized linear programming and the moment problem	7	(2)
Using the 1924 Haar result on inhomogeneous linear inequalities	9	(1)
Introducing an infinity into semi-infinite programming	10	(11)
A classification of duality states based on asymptotic consistency	21	(4)
Asymptotic Lagrange regularity	25	(1)
Applications to economics, game theory, and air pollution abatement	26	(5)
Algorithmic developments: ``Matching of the derivatives''	31	(2)
Epilog	33	(12)
References	34	(11)
Part II THEORY
About Disjunctive Optimization	45	(14)
Ivan I. Eremin
Introduction	45	(3)
Saddle points of disjunctive Lagrangian	48	(3)
Duality framework	51	(4)
An exact penalty function method	55	(4)
References	57	(2)
On Regularity and Optimality in Nonlinear Semi-Infinite Programming	59	(16)
Abdelhak Hassouni
Werner Oettli
Introduction	59	(1)
The linear case	60	(1)
The convex case	61	(5)
Convex approximants	66	(2)
The exchange method for semi-infinite convex minimization	68	(3)
Normal cones and complementary sets	71	(4)
References	74	(1)
Asymptotic Constraint Qualifications and Error Bounds for Semi-Infinite Systems of Convex Inequalities	75	(26)
Wu Li
Ivan Singer
Introduction	75	(2)
Preliminaries	77	(3)
Asymptotic constaraint qualifications. The sup-function method	80	(10)
Error bounds for semi-infinite systems of convex inequalities	90	(5)
Error bounds for semi-infinite systems of linear inequalities	95	(6)
References	99	(2)
Stability of the Feasiblle Set Mapping in Convex Semi-Infinite Programming	101	(20)
Marco A. Lopez
Virginia N. Vera de Serio
Introduction	101	(2)
Preliminaries	103	(1)
A distance between convex functions	104	(1)
Stability properties of the feasible set mapping	105	(16)
References	119	(2)
On Convex Lower Level Problems in Generalized Semi-Infinite Optimization	121	(14)
Jan-J. Ruckmann
Oliver Stein
Introduction	121	(2)
The local topology of M	123	(3)
A local first order description of M	126	(4)
First order optimality conditions	130	(2)
Final remarks	132	(3)
References	132	(3)
On Duality Theory of Conic Linear Problems	135	(34)
Alexander Shapiro
Introduction	135	(1)
Conic linear problems	136	(9)
Problem of moments	145	(7)
Semi-infinite programming	152	(3)
Continuous linear programming	155	(14)
References	164	(5)
Part III NUMERICAL METHODS
Two Logarithmic Barrier Methods for Convex Semi-Infinite Problems	169	(28)
Lars Abbe
Introduction	169	(1)
A bundle method using ε-subgradients	170	(2)
Description of the barrier method	172	(3)
Properties of the method	175	(6)
Numerical aspects	181	(1)
Numerical example	182	(3)
A regularized log-barrier method	185	(6)
Numerical results of the regularized method	191	(2)
Conclusions	193	(4)
References	194	(3)
First-Order Algorithms for Optimization Problems with a Maximum Eigenvalue/Singular Value Cost and Or Constraints	197	(24)
Elijah Polak
Introduction	197	(2)
Semi-Infinite Min-Max Problems	199	(7)
Rate of Convergence of Algorithm 2.2	206	(1)
Minimization of the Maximum Eigenvalue of a Symmetric Matrix	207	(4)
Problems with Semi-Infinite Constraints	211	(5)
Problems with Maximum Eigenvalue Constraints	216	(1)
Rate of Convergence of Algorithm 5.1	216	(1)
A Numerical Example	217	(2)
Conclusion	219	(2)
References	219	(2)
Analytic Center Based Cutting Plane Method for Linear Semi-Infinite Programming	221	(16)
Soon-Yi Wu
Shu-Cherng Fang
Chih-Jen Lin
Introduction	221	(2)
Analytic Center Based Cuts	223	(1)
Analytic Center Cutting Plane Method for LSIP	224	(6)
Convergence and Complexity	230	(7)
References	233	(4)
Part IV MODELING AND APPLICATIONS
On Some Applications of LSIP to Probability and Statistics	237	(18)
Marco Dall'Aglio
Introduction	237	(1)
De Finetti coherence	238	(8)
Constrained maximum likelihood estimation of a covariance matrix	246	(1)
LSIP in actuarial risk theory	247	(8)
References	254	(1)
Separation by Hyperlanes: A Linear Semi-Infinite Programming Approach	255	(16)
Miguel A. Goberna
Marco A. Lopez
Soon-Yi Wu
Introduction	255	(2)
Separation in normed spaces	257	(5)
Strong separation of compact sets in separable normed spaces	262	(3)
Strong separation of finite sets in the Hadamard space	265	(6)
References	269	(2)
A Semi-Infinite Optimization Approach to Optimal Spline Trajectory Planning of Mechanical Manipulators	271	(28)
Corrado Guarino Lo Bianco
Aurelio Piazzi
Introduction	271	(4)
Cubic spline trajectory planning under torque and velocity constraints	275	(2)
A feasibility result	277	(4)
Problem solution using an hybrid algorithm	281	(3)
Penalty computation via interval analysis	284	(6)
An Example	290	(3)
Conclusions	293	(6)
References	295	(4)
On Stability of Guaranteed Estimation Problems: Error Bounds for Information Domains and Experimental Design	299	(28)
Mikhail I. Gusev
Sergei A. Romanov
Introduction	299	(4)
Rate of convergence of information domains for problems with normally resolvable operator	303	(7)
Optimal placement of sensors for nonstationary system: Duality theorems	310	(5)
Optimal sensor placement: the stationary case	315	(3)
A sufficient number of sensors	318	(9)
References	324	(3)
Optimization Under Uncertainty and Linear Semi-Infinite Programming: A Survey	327	(22)
Teresa Leon
Enriqueta Vercher
Introduction	327	(2)
Fuzzy sets	329	(2)
Convex programming with set-inclusive constraints	331	(6)
Fuzzy mathematical programming	337	(4)
Linear semi-infinite programming	341	(4)
Numerical Results	345	(4)
References	346	(3)
Semi-Infinite Assignment and Transportation Games	349	(16)
Joaquin Sanchez-Soriano
Natividad Llorca
Stef Tijs
Judith Timmer
Introduction	349	(1)
Finite transportation and assignment games	350	(3)
Semi-infinite assignment games	353	(3)
Semi-infinite transportation problems and related games	356	(6)
Final remark	362	(3)
References	362	(3)
The Owen Set and the Core of Semi-Infinite Linear Production Situations	365
Stef Tijs
Judith Timmer
Natividad Llorca
Joaquin Sanchez-Soriano
Introduction	365
Finite linear production situations	366
Semi-infinite LP situations	370
Finite LTP situations	374
Semi-infinite LTP situations	379
Conclusions	385
References	386