I’m pretty excited about Afonso‘s latest research developments (namely, this and that), and I’ve been thinking with Jesse Peterson about various extensions, but we first wanted to sort out the basics of linear and semidefinite programming. Jesse typed up some notes and I’m posting them here for easy reference:

Many optimization problems can be viewed as a special case of cone programming. Given a closed convex cone in , we define the dual cone as

Examples: The positive orthant and the positive semidefinite cone are both self-dual, and the dual of a subspace is its orthogonal complement. Throughout we assume we have , , closed convex cone , closed convex cone , and linear operator . We then have the **primal** and **dual** programs

Notice when and are both the positive orthant, this is a standard linear program. Further, considering the space of real symmetric matrices as , when and is the positive semidefinite cone, this is a standard semidefinite program. We consider several standard results (weak duality, strong duality, complementary slackness) in terms of the general cone program.

Continue reading Cone Programming Cheat Sheet