ConceptTheory & Algos
Semidefinite programming
A generalization of linear programming where the optimization is over the cone of positive semidefinite matrices.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Certificate1Cholesky factor diagonal element in SDP1Eigenvalue minimization1Global optimization via SOS1Goemans-Williamson algorithm1Goemans-Williamson random Hyperplane rounding1Goemans-Williamson SDP rounding algorithm1Linear matrix inequality1Robust stability analysis1SDP relaxation for max-cut1Semidefinite program (SDP) duality1Semidefinite programming (SDP) for polynomials1
Lecturers
3Each in their own terms, from the easiest level.
Russ Tedrake
An optimization class featuring a linear objective, linear constraints, and positive semidefinite matrix constraints.Nikhil Bansal
A type of mathematical optimization problem where a linear objective function is minimized over the intersection of the cone of positive semidefinite matrices with an affine space.
Lectures that assume it
9- Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
- Geometric Interpretation of Duality, Sensitivity & Theorems of Alternatives
- Advanced Topics and Applications
- Hardness of Random 3XOR and 3Sat
- NP-Hardness of Approximation
- Duality Theory
- Computing Lyapunov Functions II
- Robust Control & Policy Search
- Majority Is Stablest Theorem
Connections
21The lectures that define it or assume it, and the concepts next to it.
Concepts9
- Linear programming
- Ellipsoid algorithm
- Linear algebra
- Optimization
- Certificate
- Cholesky factor diagonal element in SDP