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