Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms

By Jiming Peng, Cornelis Roos and Tamás Terlaky

Research on interior-point 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 so-called small-update and large-update 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 primal-dual IPMs based on the notion of the self-regularity of a function.


The authors deal with linear optimization, nonlinear complementarity problems, semidefinite optimization, and second-order conic optimization problems. The framework also covers large classes of linear complementarity problems and convex optimization. The algorithm considered can be interpreted as a path-following method or a potential reduction method. Starting from a primal-dual strictly feasible point, the algorithm chooses a search direction defined by some Newton-type system derived from the self-regular 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 self-regular functions, the authors establish that the complexity of large-update 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.

• Language: English
• Publisher: Princeton University Press
• Release date: Jan 10, 2009
• ISBN: 9781400825134

Book preview

Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms

Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms

Jiming Peng

Cornelis Roos

and

Tamás Terlaky

PRINCETON UNIVERSITY PRESS

PRINCETON AND OXFORD

Copyright © 2002 by Princeton University Press

Published by Princeton University Press,

41 William Street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press,

3 Market Place, Woodstock, Oxfordshire OX20 1SY

All Rights Reserved

Library of Congress Cataloging-in-Publication Data applied for

Peng, Jiming, Roos, Cornelis and Terlaky, Tamás

Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms /

Jiming Peng, Cornelis Roos and Tamás Terlaky

p. cm.

Includes bibliographical references and index

eISBN: 978-1-40082-513-4

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library

This book has been composed in Times and Abadi

Printed on acid-free paper

www.pup.princeton.edu

Printed in the United States of America

Contents

Preface

Acknowledgements

Notation

List of Abbreviations

Chapter 1. Introduction and Preliminaries

1.1 Historical Background of Interior-Point Methods

1.1.1 Prelude

1.1.2 A Brief Review of Modern Interior-Point Methods

1.2 Primal-Dual Path-Following Algorithm for LO

1.2.1 Primal-Dual Model for LO, Duality Theory and the Central Path

1.2.2 Primal-Dual Newton Method for LO

1.2.3 Strategies in Path-following Algorithms and Motivation

1.3 Preliminaries and Scope of the Monograph

1.3.1 Preliminary Technical Results

1.3.2 Relation Between Proximities and Search Directions

1.3.3 Contents and Notational Abbreviations

Chapter 2. Self-Regular Functions and Their Properties

2.1 An Introduction to Univariate Self-Regular Functions

2.2 Basic Properties of Univariate Self-Regular Functions

2.3 Relations Between S-R and S-C Functions

Chapter 3. Primal-Dual Algorithms for Linear Optimization Based on Self-Regular Proximities

3.1 Self-Regular Functions in and Self-Regular Proximities for LO

3.2 The Algorithm

3.3 Estimate of the Proximity After a Newton Step

3.4 Complexity of the Algorithm

3.5 Relaxing the Requirement on the Proximity Function

Chapter 4. Interior-Point Methods for Complementarity Problems Based on Self Regular Proximities

4.1 Introduction to CPs and the Central Path

4.2 Preliminary Results on p*(k) Mappings

4.3 New Search Directions for p*(k) CPs

4.4 Complexity of the Algorithm

4.4.1 Ingredients for Estimating the Proximity

4.4.2 Estimate of the Proximity After a Step

4.4.3 Complexity of the Algorithm for CPs

Chapter 5. Primal-Dual Interior-Point Methods for Semidefinite Optimization Based on Self-Regular Proximities

5.1 Introduction to SDO, Duality Theory and Central Path

5.2 Preliminary Results on Matrix Functions

5.3 New Search Directions for SDO

5.3.1 Scaling Schemes for SDO

5.3.2 Intermezzo: A Variational Principle for Scaling

5.3.3 New Proximities and Search Directions for SDO

5.4 New Polynomial Primal-Dual IPMs for SDO

5.4.1 The Algorithm

5.4.2 Complexity of the Algorithm

Chapter 6. Primal-Dual Interior-Point Methods for Second-Order Conic Optimization Based on Self-Regular Proximities

6.1 Introduction to SOCO, Duality Theory and The Central Path

6.2 Preliminary Results on Functions Associated with Second-Order Cones

6.2.1 Jordan Algebra, Trace and Determinant

6.2.2 Functions and Derivatives Associated with Second-Order Cones

6.3 New Search Directions for SOCO

6.3.1 Preliminaries

6.3.2 Scaling Schemes for SOCO

6.3.3 Intermezzo: A Variational Principle for Scaling

6.3.4 New Proximities and Search Directions for SOCO

6.4 New IPMs for SOCO

6.4.1 The Algorithm

6.4.2 Complexity of the Algorithm

Chapter 7. Initialization: Embedding Models for Linear Optimization, Complementarity Problems, Semidefinite Optimization and Second-Order Conic Optimization

7.1 The Self-Dual Embedding Model for LO

7.2 The Embedding Model for CP

7.3 Self-Dual Embedding Models for SDO and SOCO

Chapter 8. Conclusions

8.1 A Survey of the Results and Future Research Topics

References

Notation

List of Abbreviations

Acknowledgments

In the preparation of this monograph we greatly appreciated the support and stimulating discussions with many colleagues from all over the world.

First, we are indebted to Akiko Yoshise (University of Tsukuba, Japan) who made invaluable contributions to chapter 4 of this work. Our joint work resulted in some joint publications in this area.

Special thanks are due to those colleagues who helped us to clean the manuscript and to improve the presentation. Michael Saunders (Stanford University, USA), as always, made an extremely careful reading of an earlier version of the manuscript and provided us with countless corrections and suggestions for improvement. Jánáos Mayer (University of Zürich, Switzerland) gave numerous remarks and suggestions after a critical reading of large parts of the first draft of the monograph. Florian Jarre (University of Düsseldorf), Francois Glineur (Faculté Polytechnique de Mous, Belgium) and Florian Potra (University of Maryland) also gave us invaluable comments to improve the monograph. We kindly acknowledge the stimulating and encouraging discussions with Yurii Nesterov (CORE, C.U. Louvain-laNeuve), Arkadii Nemirovskii (TECHNION, Haifa), Erling Andersen (EKA Consulting, Copenhagen) about various aspects of the self-regular paradigm. Their generous help is acknowledged here. In spite of our efforts and the invaluable support of our colleagues some typos