Self-Regularity ：A New Paradigm for Primal-Dual Interior-Point Algorithms ( Princeton Series in Applied Mathematics )

Publication subTitle ：A New Paradigm for Primal-Dual Interior-Point Algorithms

Publication series ：Princeton Series in Applied Mathematics

Author： Peng Jiming;Roos Cornelis;Terlaky Tamás  

Publisher： Princeton University Press‎

Publication year： 2009

E-ISBN: 9781400825134

P-ISBN(Paperback): 9780691091921

Subject： K712.43 南北战争（1861~1865年）

Keyword： 数理科学和化学

Language： ENG

Access to resources Favorite

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Description

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 student

Chapter

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 Rn++ 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

Index

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

R

S

T

V

W

Y

Z

The users who browse this book also browse