Ebook: Handbook on Semidefinite, Conic and Polynomial Optimization

Semidefinite and conic optimization is a major and thriving research area within the optimization community. Although semidefinite optimization has been studied (under different names) since at least the 1940s, its importance grew immensely during the 1990s after polynomial-time interior-point methods for linear optimization were extended to solve semidefinite optimization problems.

Since the beginning of the 21st century, not only has research into semidefinite and conic optimization continued unabated, but also a fruitful interaction has developed with algebraic geometry through the close connections between semidefinite matrices and polynomial optimization. This has brought about important new results and led to an even higher level of research activity.

This Handbook on Semidefinite, Conic and Polynomial Optimization provides the reader with a snapshot of the state-of-the-art in the growing and mutually enriching areas of semidefinite optimization, conic optimization, and polynomial optimization. It contains a compendium of the recent research activity that has taken place in these thrilling areas, and will appeal to doctoralstudents, young graduates, and experienced researchers alike.

The Handbook’s thirty-one chapters are organized into four parts:

• Theory, covering significant theoretical developments as well as the interactions between conic optimization and polynomial optimization;
• Algorithms, documenting the directions of current algorithmic development;
• Software, providing an overview of the state-of-the-art;
• Applications, dealing with the application areas where semidefinite and conic optimization has made a significant impact in recent years.

---

Semidefinite and conic optimization is a major and thriving research area within the optimization community. Although semidefinite optimization has been studied (under different names) since at least the 1940s, its importance grew immensely during the 1990s after polynomial-time interior-point methods for linear optimization were extended to solve semidefinite optimization problems.

Since the beginning of the 21st century, not only has research into semidefinite and conic optimization continued unabated, but also a fruitful interaction has developed with algebraic geometry through the close connections between semidefinite matrices and polynomial optimization. This has brought about important new results and led to an even higher level of research activity.

This Handbook on Semidefinite, Conic and Polynomial Optimization provides the reader with a snapshot of the state-of-the-art in the growing and mutually enriching areas of semidefinite optimization, conic optimization, and polynomial optimization. It contains a compendium of the recent research activity that has taken place in these thrilling areas, and will appeal to doctoralstudents, young graduates, and experienced researchers alike.

The Handbook’s thirty-one chapters are organized into four parts:

• Theory, covering significant theoretical developments as well as the interactions between conic optimization and polynomial optimization;
• Algorithms, documenting the directions of current algorithmic development;
• Software, providing an overview of the state-of-the-art;
• Applications, dealing with the application areas where semidefinite and conic optimization has made a significant impact in recent years.

---

Semidefinite and conic optimization is a major and thriving research area within the optimization community. Although semidefinite optimization has been studied (under different names) since at least the 1940s, its importance grew immensely during the 1990s after polynomial-time interior-point methods for linear optimization were extended to solve semidefinite optimization problems.

Since the beginning of the 21st century, not only has research into semidefinite and conic optimization continued unabated, but also a fruitful interaction has developed with algebraic geometry through the close connections between semidefinite matrices and polynomial optimization. This has brought about important new results and led to an even higher level of research activity.

This Handbook on Semidefinite, Conic and Polynomial Optimization provides the reader with a snapshot of the state-of-the-art in the growing and mutually enriching areas of semidefinite optimization, conic optimization, and polynomial optimization. It contains a compendium of the recent research activity that has taken place in these thrilling areas, and will appeal to doctoralstudents, young graduates, and experienced researchers alike.

The Handbook’s thirty-one chapters are organized into four parts:

• Theory, covering significant theoretical developments as well as the interactions between conic optimization and polynomial optimization;
• Algorithms, documenting the directions of current algorithmic development;
• Software, providing an overview of the state-of-the-art;
• Applications, dealing with the application areas where semidefinite and conic optimization has made a significant impact in recent years.

Content:
Front Matter....Pages i-xi
Front Matter....Pages 23-23
The Approach of Moments for Polynomial Equations....Pages 25-60
Algebraic Degree in Semidefinite and Polynomial Optimization....Pages 61-75
Semidefinite Representation of Convex Sets and Convex Hulls....Pages 77-112
Convex Hulls of Algebraic Sets....Pages 113-138
Convex Relaxations and Integrality Gaps....Pages 139-169
Relaxations of Combinatorial Problems Via Association Schemes....Pages 171-199
Copositive Programming....Pages 201-218
Invariant Semidefinite Programs....Pages 219-269
A “Joint+Marginal” Approach in Optimization....Pages 271-295
An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization....Pages 297-337
Complementarity Problems Over Symmetric Cones: A Survey of Recent Developments in Several Aspects....Pages 339-375
Convexity and Semidefinite Programming in Dimension-Free Matrix Unknowns....Pages 377-405
Positivity and Optimization: Beyond Polynomials....Pages 407-434
Front Matter....Pages 435-435
Self-Regular Interior-Point Methods for Semidefinite Optimization....Pages 437-454
Elementary Optimality Conditions for Nonlinear SDPs....Pages 455-470
Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts....Pages 471-498
Exploiting Sparsity in SDP Relaxation of Polynomial Optimization Problems....Pages 499-531
Block Coordinate Descent Methods for Semidefinite Programming....Pages 533-564
Projection Methods in Conic Optimization....Pages 565-600
Introduction to Semidefinite, Conic and Polynomial Optimization....Pages 1-22
Front Matter....Pages 435-435
SDP Relaxations for Non-Commutative Polynomial Optimization....Pages 601-634
Semidefinite Programming and Constraint Programming....Pages 635-668
Front Matter....Pages 669-669
The State-of-the-Art in Conic Optimization Software....Pages 671-686
Latest Developments in the SDPA Family for Solving Large-Scale SDPs....Pages 687-713
On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0....Pages 715-754
PENNON: Software for Linear and Nonlinear Matrix Inequalities....Pages 755-791
Front Matter....Pages 793-793
SDP Relaxations for Some Combinatorial Optimization Problems....Pages 795-819
Computational Approaches to Max-Cut....Pages 821-847
Global Approaches for Facility Layout and VLSI Floorplanning....Pages 849-877
Euclidean Distance Matrices and Applications....Pages 879-914
Sparse PCA: Convex Relaxations, Algorithms and Applications....Pages 915-940
Back Matter....Pages 941-957

---

Semidefinite and conic optimization is a major and thriving research area within the optimization community. Although semidefinite optimization has been studied (under different names) since at least the 1940s, its importance grew immensely during the 1990s after polynomial-time interior-point methods for linear optimization were extended to solve semidefinite optimization problems.

Since the beginning of the 21st century, not only has research into semidefinite and conic optimization continued unabated, but also a fruitful interaction has developed with algebraic geometry through the close connections between semidefinite matrices and polynomial optimization. This has brought about important new results and led to an even higher level of research activity.

This Handbook on Semidefinite, Conic and Polynomial Optimization provides the reader with a snapshot of the state-of-the-art in the growing and mutually enriching areas of semidefinite optimization, conic optimization, and polynomial optimization. It contains a compendium of the recent research activity that has taken place in these thrilling areas, and will appeal to doctoralstudents, young graduates, and experienced researchers alike.

The Handbook’s thirty-one chapters are organized into four parts:

• Theory, covering significant theoretical developments as well as the interactions between conic optimization and polynomial optimization;
• Algorithms, documenting the directions of current algorithmic development;
• Software, providing an overview of the state-of-the-art;
• Applications, dealing with the application areas where semidefinite and conic optimization has made a significant impact in recent years.

Content:
Front Matter....Pages i-xi
Front Matter....Pages 23-23
The Approach of Moments for Polynomial Equations....Pages 25-60
Algebraic Degree in Semidefinite and Polynomial Optimization....Pages 61-75
Semidefinite Representation of Convex Sets and Convex Hulls....Pages 77-112
Convex Hulls of Algebraic Sets....Pages 113-138
Convex Relaxations and Integrality Gaps....Pages 139-169
Relaxations of Combinatorial Problems Via Association Schemes....Pages 171-199
Copositive Programming....Pages 201-218
Invariant Semidefinite Programs....Pages 219-269
A “Joint+Marginal” Approach in Optimization....Pages 271-295
An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization....Pages 297-337
Complementarity Problems Over Symmetric Cones: A Survey of Recent Developments in Several Aspects....Pages 339-375
Convexity and Semidefinite Programming in Dimension-Free Matrix Unknowns....Pages 377-405
Positivity and Optimization: Beyond Polynomials....Pages 407-434
Front Matter....Pages 435-435
Self-Regular Interior-Point Methods for Semidefinite Optimization....Pages 437-454
Elementary Optimality Conditions for Nonlinear SDPs....Pages 455-470
Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts....Pages 471-498
Exploiting Sparsity in SDP Relaxation of Polynomial Optimization Problems....Pages 499-531
Block Coordinate Descent Methods for Semidefinite Programming....Pages 533-564
Projection Methods in Conic Optimization....Pages 565-600
Introduction to Semidefinite, Conic and Polynomial Optimization....Pages 1-22
Front Matter....Pages 435-435
SDP Relaxations for Non-Commutative Polynomial Optimization....Pages 601-634
Semidefinite Programming and Constraint Programming....Pages 635-668
Front Matter....Pages 669-669
The State-of-the-Art in Conic Optimization Software....Pages 671-686
Latest Developments in the SDPA Family for Solving Large-Scale SDPs....Pages 687-713
On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0....Pages 715-754
PENNON: Software for Linear and Nonlinear Matrix Inequalities....Pages 755-791
Front Matter....Pages 793-793
SDP Relaxations for Some Combinatorial Optimization Problems....Pages 795-819
Computational Approaches to Max-Cut....Pages 821-847
Global Approaches for Facility Layout and VLSI Floorplanning....Pages 849-877
Euclidean Distance Matrices and Applications....Pages 879-914
Sparse PCA: Convex Relaxations, Algorithms and Applications....Pages 915-940
Back Matter....Pages 941-957
....