Handbook of Semidefinite Programming - Theory, Algorithms, and Applications (INTERNATIONAL SERIES IN OPERATIONS RESEARCH AND) (International Series in Operations Research & Management Science)

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 Cover 1 INTRODUCTION 24 SEMIDEFINITE PROGRAMMING 24 OVERVIEW OF THE HANDBOOK 25 NOTATION 28 I THEORY 32 CONVEX ANALYSIS ON SYMMETRIC MATRICES 36 INTRODUCTION 36 SYMMETRIC MATRICES 37 ANALYSIS WITH SYMMETRIC MATRICES 39 Acknowledgements 50 THE GEOMETRY OF SEMIDEFINITE PROGRAMMING 52 INTRODUCTION 52 PRELIMINARIES 54 THE GEOMETRY OF CONE LP S MAIN RESULTS 60 SEMIDEFINITE COMBINATORICS 77 TWO ALGORITHMIC ASPECTS 83 LITERATURE 85 APPENDICES 86 DUALITY AND OPTIMALITY CONDITIONS 90 DUALITY OPTIMALITY CONDITIONS AND PERTURBATION ANALYSIS 90 PARAMETRIC LINEAR SEMIDEFINITE PROGRAMMING 115 SELF DUAL EMBEDDINGS 134 INTRODUCTION 134 PRELIMINARIES 136 THE EMBEDDING STRATEGY 139 SOLVING THE EMBEDDING PROBLEM 144 EXISTENCE OF THE CENTRAL PATH A CONSTRUCTIVE PROOF 147 OBTAINING MAXIMALLY COMPLEMENTARY SOLUTIONS 148 SEPARATING SMALL AND LARGE VARIABLES 151 REMAINING DUALITY AND FEASIBILITY ISSUES 154 EMBEDDING EXTENDED LAGRANGE SLATER DUALS 159 SUMMARY 160 ROBUSTNESS 162 INTRODUCTION 162 AFFINE PERTURBATIONS 165 RATIONAL DEPENDENCE 169 SPECIAL CASES 174 EXAMPLES 178 CONCLUDING REMARKS 185 ERROR ANALYSIS 186 INTRODUCTION 186 PRELIMINARIES 188 THE REGULARIZED BACKWARD ERROR 194 REGULARIZATION STEPS 199 INFEASIBLE SYSTEMS 204 SYSTEMS OF QUADRATIC INEQUALITIES 206 II ALGORITHMS 214 SYMMETRIC CONES POTENTIAL REDUCTION METHODS AND WORD BY WORD EXTENSIONS 218 INTRODUCTION 218 A remark about notation 220 SEMIDEFINITE PROGRAMMING CONE LP OVER SYMMETRIC CONES 221 EUCLIDEAN JORDAN ALGEBRAS 222 POTENTIAL REDUCTION ALGORITHMS FOR SEMIDEFINITE PROGRAMMING 237 POTENTIAL REDUCTION AND PRIMAL DUAL METHODS 258 INTRODUCTION 258 FUND 262 AMENTAL INGREDIENTS 262 WHAT ARE THE USES OF A POTENTIAL FUNCTION 266 KOJIMA SHINDOH HARA APPROACH 271 NESTEROV TODD APPROACH 273 SCALING NOTIONS OF PRIMAL DUAL SYMMETRY AND SCALE INVARIANCE 276 A POTENTIAL REDUCTION FRAMEWORK 282 PATH FOLLOWING METHODS 290 INTRODUCTION 290 THE CENTRAL PATH 293 SEARCH DIRECTIONS 301 PRIMAL DUAL PATH FOLLOWING METHODS 305 BUNDLE METHODS TO MINIMIZE THE MAXIMUM EIGENVALUE FUNCTION 330 INTRODUCTION 330 THE MAXIMUM EIGENVALUE FUNCTION 332 GENERAL SCHEME 333 THE PROXIMAL BUNDLE METHOD 336 THE SPECTRAL BUNDLE METHOD 338 THE MIXED POLYHEDRAL SEMIDEFINITE METHOD 341 A SECOND ORDER PROXIMAL BUNDLE METHOD 343 IMPLEMENTATIONS 348 NUMERICAL RESULTS 352 III APPLICATIONS and EXTENSIONS 362 COMBINATORIAL OPTIMIZATION 366 FROM COMBINATORIAL OPTIMIZATION TO SDP 366 SPECIFIC COMBINATORIAL OPTIMIZATION PROBLEMS 369 COMPUTATIONAL ASPECTS 377 COMBINATORIAL SDP AND ASSOCIATION SCHEMES 377 APPROXIMATION RESULTS THROUGH SDP 380 SEMIDEFINITE PROGRAMMING RELAXATIONS OF NONCONVEX QUADRATIC OPTIMIZATION 384 INTRODUCTION 384 GLOBAL QUADRATIC OPTIMIZATION VIA CONIC RELAXATION 386 QUADRATIC CONSTRAINTS 410 RELAXATIONS OF Q 418 P 418 SEMIDEFINITE PROGRAMMING IN SYSTEMS AND CONTROL THEORY 444 INTRODUCTION 444 CONTROL SYSTEM ANALYSIS AND DESIGN AN INTRODUCTION 445 ROBUSTNESS ANALYSIS AND DESIGN FOR LINEAR POLYTOPIC SYSTEMS USING QUADRATIC LYAPUNOV FUNCTIONS 450 ROBUST STABILITY ANALYSIS OF LFR SYSTEMS IN THE IQC FRAMEWORK 454 STABILIZING CONTROLLER DESIGN FOR LFR SYSTEMS 459 CONCLUSION 464 STRUCTURAL DESIGN 466 STRUCTURAL DESIGN GENERAL SETTING 466 SEMIDEFINITE REFORMULATION OF 470 FROM PRIMAL TO DUAL 476 FROM DUAL TO PRIMAL 481 EXPLICIT FORMS OF THE STANDARD TRUSS AND SHAPE PROBLEMS 483 CONCLUDING REMARKS 488 MOMENT PROBLEMS AND SEMIDEFINITE OPTIMIZATION 492 INTRODUCTION 492 SEMIDEFINITE RELAXATIONS FOR STOCHASTIC OPTIMIZATION PROBLEMS 496 OPTIMAL BOUNDS IN PROBABILITY 506 MOMENT PROBLEMS IN FINANCE 519 MOMENT PROBLEMS IN DISCRETE OPTIMIZATION 530 CONCLUDING REMARKS 532 DESIGN OF EXPERIMENTS IN STATISTICS 534 DESIGN OF REGRESSION EXPERIMENTS 534 SEMIDEFINITE PROGRAMMING IN EXPERIMENTAL DESIGN 551 MATRIX COMPLETION PROBLEMS 556 INTRODUCTION 556 WEIGHTED CLOSEST EUCLIDEAN DISTANCE MATRIX 557 WEIGHTED CLOSEST POSITIVE SEMIDEFINITE MATRIX 565 OTHER COMPLETION PROBLEMS 567 EIGENVALUE PROBLEMS AND NONCONVEX MINIMIZATION 570 INTRODUCTION 570 SELECTED EIGENVALUE PROBLEMS 571 GENERALIZATION OF NEWTONS METHOD 574 A METHOD FOR CONSTRAINED PROBLEMS 577 CONCLUSION 585 Acknowledgement 585 SEQUENTIAL QUADRATIC CONSTRAINED QUADRATIC PROGRAMMING FOR GENERAL NONLINEAR PROGRAMMING 586 INTRODUCTION 586 THE SIMPLEST CASE 587 MULTIPLE TRUST REGIONS 589 APPROXIMATIONS OF NONLINEAR PROGRAMS 593 QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING 595 CONCLUSION 597 Appendix A CONCLUSION AND FURTHER HISTORICAL NOTES 671 A INDEX 677

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.