SelfRegularity: A New Paradigm for PrimalDual InteriorPoint Algorithms
A New Paradigm for PrimalDual InteriorPoint Algorithms
Creator  
Publisher 
20021027

ISBN  9781400825134, 140082513X, 9780691091938, 0691091935,

Language 
English

Category  
Subject  Algoritmen.  gtt Controleleer.  gtt Electronic books. Interiorpoint methods. Interiorpoint methods.  fast  (OCoLC)fst00976414 Mathematical optimization. Mathematical optimization.  fast  (OCoLC)fst01012099 MATHEMATICS  Applied.  bisacsh MATHEMATICS  Optimization.  bisacsh Mathematische programmering.  gtt Programming (Mathematics) Programming (Mathematics)  fast  (OCoLC)fst01078701 Zelfregulering.  gtt 
Description
Research on interiorpoint methods (IPMs) has dominated the field of mathematical programming for the last two decades. Two contrasting approaches in the analysis and implementation of IPMs are the socalled smallupdate and largeupdate methods, although, until now, there has been a notorious gap between the theory and practical performance of these two strategies. This book comes close to bridging that gap, presenting a new framework for the theory of primaldual IPMs based on the notion of the selfregularity of a function. The authors deal with linear optimization, nonlinear complementarity problems, semidefinite optimization, and secondorder conic optimization problems. The framework also covers large classes of linear complementarity problems and convex optimization. The algorithm considered can be interpreted as a pathfollowing method or a potential reduction method. Starting from a primaldual strictly feasible point, the algorithm chooses a search direction defined by some Newtontype system derived from the selfregular proximity. The iterate is then updated, with the iterates staying in a certain neighborhood of the central path until an approximate solution to the problem is found. By extensively exploring some intriguing properties of selfregular functions, the authors establish that the complexity of largeupdate IPMs can come arbitrarily close to the best known iteration bounds of IPMs. Researchers and postgraduate students in all areas of linear and nonlinear optimization will find this book an important and invaluable aid to their work.