Learn Semidefinite Programming

Ten exams must fit into two time slots. If two courses share students, putting their exams at the same time creates a clash. Some pairs share many more students than others. Which exams should go in each slot?

For ten exams, we can check every schedule. That gives us a rare luxury: while learning a sophisticated method, we can still verify the final answer exactly. Then we will ask what survives when exhaustive search no longer does.

The route is unexpected. We will turn two-way choices into vectors, store their geometry in a positive semidefinite matrix, optimize over those matrices, and round the result back into a timetable. The computation will produce both a schedule and a bound on every schedule we did not inspect.

By the end, you will be able to formulate small semidefinite programs, derive and check dual bounds, interpret matrix solutions geometrically, implement a rounding algorithm, and state what floating-point solver output does—and does not—establish.

The course arc

Pose the decision. Build the exam-conflict graph and define a weighted cut.
Establish a baseline. Search all small schedules and express the discrete problem algebraically.
Learn the geometry. Work with Gram matrices, the PSD cone, rank, and affine slices.
Model with SDPs. Recognize standard form and solve correlation and localization problems that have nothing to do with cuts.
Return to the schedule. Relax signs into vectors and understand why the SDP gives a bound.
Certify and compute. Derive the dual, inspect a primal-dual algorithm, and audit numerical output.
Finish the pipeline. Round the SDP geometry into a schedule and compare it with exact search.

Why one recurring problem?

Max-Cut is the thread, not the definition of semidefinite programming. A stable example lets us revisit the same decision from combinatorics, geometry, duality, algorithms, and numerical analysis without inventing new notation each time.

The correlation and sensor-localization chapters are deliberate detours. They show which ideas belong to SDP generally: PSD variables, linear matrix constraints, low-rank geometry, dual certificates, and numerical tolerances. Short “Go further” notes point to primary papers, course notes, or official Julia documentation when a learner wants more depth.

The standard of evidence

A feasible timetable is an achievable answer. A dual-feasible point can bound all possible answers. A solver status alone establishes neither. Throughout the course, claims are paired with residuals, tolerances, or an exact small-instance check.

Build the problem from its data.

--- title: "Learn Semidefinite Programming" --- Ten exams must fit into two time slots. If two courses share students, putting their exams at the same time creates a clash. Some pairs share many more students than others. Which exams should go in each slot? For ten exams, we can check every schedule. That gives us a rare luxury: while learning a sophisticated method, we can still verify the final answer exactly. Then we will ask what survives when exhaustive search no longer does. The route is unexpected. We will turn two-way choices into vectors, store their geometry in a positive semidefinite matrix, optimize over those matrices, and round the result back into a timetable. The computation will produce both a schedule and a bound on every schedule we did not inspect. By the end, you will be able to formulate small semidefinite programs, derive and check dual bounds, interpret matrix solutions geometrically, implement a rounding algorithm, and state what floating-point solver output does—and does not—establish. ## The course arc 1. **Pose the decision.** Build the exam-conflict graph and define a weighted cut. 2. **Establish a baseline.** Search all small schedules and express the discrete problem algebraically. 3. **Learn the geometry.** Work with Gram matrices, the PSD cone, rank, and affine slices. 4. **Model with SDPs.** Recognize standard form and solve correlation and localization problems that have nothing to do with cuts. 5. **Return to the schedule.** Relax signs into vectors and understand why the SDP gives a bound. 6. **Certify and compute.** Derive the dual, inspect a primal-dual algorithm, and audit numerical output. 7. **Finish the pipeline.** Round the SDP geometry into a schedule and compare it with exact search. ## Why one recurring problem? Max-Cut is the thread, not the definition of semidefinite programming. A stable example lets us revisit the same decision from combinatorics, geometry, duality, algorithms, and numerical analysis without inventing new notation each time. The correlation and sensor-localization chapters are deliberate detours. They show which ideas belong to SDP generally: PSD variables, linear matrix constraints, low-rank geometry, dual certificates, and numerical tolerances. Short “Go further” notes point to primary papers, course notes, or official Julia documentation when a learner wants more depth. ::: {.callout-note} ## The standard of evidence A feasible timetable is an achievable answer. A dual-feasible point can bound all possible answers. A solver status alone establishes neither. Throughout the course, claims are paired with residuals, tolerances, or an exact small-instance check. ::: [Build the problem from its data](chapters/00-build-the-problem.qmd).