Ebook: Handbook of Semidefinite Programming - Theory, Algorithms, and Applications

Semidefinite programming (SDP) is one of the most exciting and active research areas in optimization. It has and continues to attract researchers with very diverse backgrounds, including experts in convex programming, linear algebra, numerical optimization, combinatorial optimization, control theory, and statistics. This tremendous research activity has been prompted by the discovery of important applications in combinatorial optimization and control theory, the development of efficient interior-point algorithms for solving SDP problems, and the depth and elegance of the underlying optimization theory. The Handbook of Semidefinite Programming offers an advanced and broad overview of the current state of the field. It contains nineteen chapters written by the leading experts on the subject. The chapters are organized in three parts: Theory, Algorithms, and Applications and Extensions.

Table of Contents

Cover

INTRODUCTION

SEMIDEFINITE PROGRAMMING
OVERVIEW OF THE HANDBOOK
NOTATION

I THEORY

CONVEX ANALYSIS ON SYMMETRIC MATRICES
INTRODUCTION
SYMMETRIC MATRICES
ANALYSIS WITH SYMMETRIC MATRICES
Acknowledgements
THE GEOMETRY OF SEMIDEFINITE PROGRAMMING
INTRODUCTION
PRELIMINARIES
THE GEOMETRY OF CONE LP S MAIN RESULTS
SEMIDEFINITE COMBINATORICS
TWO ALGORITHMIC ASPECTS
LITERATURE
APPENDICES
DUALITY AND OPTIMALITY CONDITIONS
DUALITY OPTIMALITY CONDITIONS AND PERTURBATION ANALYSIS
PARAMETRIC LINEAR SEMIDEFINITE PROGRAMMING
SELF DUAL EMBEDDINGS
INTRODUCTION
PRELIMINARIES
THE EMBEDDING STRATEGY
SOLVING THE EMBEDDING PROBLEM
EXISTENCE OF THE CENTRAL PATH A CONSTRUCTIVE PROOF
OBTAINING MAXIMALLY COMPLEMENTARY SOLUTIONS
SEPARATING SMALL AND LARGE VARIABLES
REMAINING DUALITY AND FEASIBILITY ISSUES
EMBEDDING EXTENDED LAGRANGE SLATER DUALS
SUMMARY
ROBUSTNESS
INTRODUCTION
AFFINE PERTURBATIONS
RATIONAL DEPENDENCE
SPECIAL CASES
EXAMPLES
CONCLUDING REMARKS
ERROR ANALYSIS
INTRODUCTION
PRELIMINARIES
THE REGULARIZED BACKWARD ERROR
REGULARIZATION STEPS
INFEASIBLE SYSTEMS
SYSTEMS OF QUADRATIC INEQUALITIES

II ALGORITHMS

SYMMETRIC CONES POTENTIAL REDUCTION METHODS AND WORD BY WORD EXTENSIONS
INTRODUCTION
A remark about notation
SEMIDEFINITE PROGRAMMING CONE LP OVER SYMMETRIC CONES
EUCLIDEAN JORDAN ALGEBRAS
POTENTIAL REDUCTION ALGORITHMS FOR SEMIDEFINITE PROGRAMMING
POTENTIAL REDUCTION AND PRIMAL DUAL METHODS
INTRODUCTION
FUND
AMENTAL INGREDIENTS
WHAT ARE THE USES OF A POTENTIAL FUNCTION
KOJIMA SHINDOH HARA APPROACH
NESTEROV TODD APPROACH
SCALING NOTIONS OF PRIMAL DUAL SYMMETRY AND SCALE INVARIANCE
A POTENTIAL REDUCTION FRAMEWORK
PATH FOLLOWING METHODS
INTRODUCTION
THE CENTRAL PATH
SEARCH DIRECTIONS
PRIMAL DUAL PATH FOLLOWING METHODS
BUNDLE METHODS TO MINIMIZE THE MAXIMUM EIGENVALUE FUNCTION
INTRODUCTION
THE MAXIMUM EIGENVALUE FUNCTION
GENERAL SCHEME
THE PROXIMAL BUNDLE METHOD
THE SPECTRAL BUNDLE METHOD
THE MIXED POLYHEDRAL SEMIDEFINITE METHOD
A SECOND ORDER PROXIMAL BUNDLE METHOD
IMPLEMENTATIONS
NUMERICAL RESULTS

III APPLICATIONS and EXTENSIONS

COMBINATORIAL OPTIMIZATION
FROM COMBINATORIAL OPTIMIZATION TO SDP
SPECIFIC COMBINATORIAL OPTIMIZATION PROBLEMS
COMPUTATIONAL ASPECTS
COMBINATORIAL SDP AND ASSOCIATION SCHEMES
APPROXIMATION RESULTS THROUGH SDP
SEMIDEFINITE PROGRAMMING RELAXATIONS OF NONCONVEX QUADRATIC OPTIMIZATION
INTRODUCTION
GLOBAL QUADRATIC OPTIMIZATION VIA CONIC RELAXATION
QUADRATIC CONSTRAINTS
RELAXATIONS OF Q
P
SEMIDEFINITE PROGRAMMING IN SYSTEMS AND CONTROL THEORY
INTRODUCTION
CONTROL SYSTEM ANALYSIS AND DESIGN AN INTRODUCTION
ROBUSTNESS ANALYSIS AND DESIGN FOR LINEAR POLYTOPIC SYSTEMS USING QUADRATIC LYAPUNOV FUNCTIONS
ROBUST STABILITY ANALYSIS OF LFR SYSTEMS IN THE IQC FRAMEWORK
STABILIZING CONTROLLER DESIGN FOR LFR SYSTEMS
CONCLUSION
STRUCTURAL DESIGN
STRUCTURAL DESIGN GENERAL SETTING
SEMIDEFINITE REFORMULATION OF
FROM PRIMAL TO DUAL
FROM DUAL TO PRIMAL
EXPLICIT FORMS OF THE STANDARD TRUSS AND SHAPE PROBLEMS
CONCLUDING REMARKS
MOMENT PROBLEMS AND SEMIDEFINITE OPTIMIZATION
INTRODUCTION
SEMIDEFINITE RELAXATIONS FOR STOCHASTIC OPTIMIZATION PROBLEMS
OPTIMAL BOUNDS IN PROBABILITY
MOMENT PROBLEMS IN FINANCE
MOMENT PROBLEMS IN DISCRETE OPTIMIZATION
CONCLUDING REMARKS
DESIGN OF EXPERIMENTS IN STATISTICS
DESIGN OF REGRESSION EXPERIMENTS
SEMIDEFINITE PROGRAMMING IN EXPERIMENTAL DESIGN
MATRIX COMPLETION PROBLEMS
INTRODUCTION
WEIGHTED CLOSEST EUCLIDEAN DISTANCE MATRIX
WEIGHTED CLOSEST POSITIVE SEMIDEFINITE MATRIX
OTHER COMPLETION PROBLEMS
EIGENVALUE PROBLEMS AND NONCONVEX MINIMIZATION
INTRODUCTION
SELECTED EIGENVALUE PROBLEMS
GENERALIZATION OF NEWTONS METHOD
A METHOD FOR CONSTRAINED PROBLEMS
CONCLUSION
Acknowledgement
SEQUENTIAL QUADRATIC CONSTRAINED QUADRATIC PROGRAMMING FOR GENERAL NONLINEAR PROGRAMMING
INTRODUCTION
THE SIMPLEST CASE
MULTIPLE TRUST REGIONS
APPROXIMATIONS OF NONLINEAR PROGRAMS
QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING
CONCLUSION
Appendix A CONCLUSION AND FURTHER HISTORICAL NOTES
A INDEX