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.
— Weak Duality —
Weak duality is a direct consequence of the definition of the dual cone:
Theorem. Let and be a feasible points for (P) and (D) respectively. Then .
Proof: Since and , we have
That is, . Similarly, and implies . Together, we have .
In the special case of linear programming, it is easy to see how the dual program simply minimizes the upper bounds on which are provided by the primal constraints. In this way, weak duality should probably be viewed as the motivation for the definition rather than a theorem which follows from the definition.
— Strong Duality —
Strong duality posits that the optimal value of (P) equals that of (D), and is not nearly as immediate. While it appears difficult to geometrically intuit what is happening in the ambient spaces (it’s hard enough trying to visualize the adjoint of ), if we lift to higher dimensions, the result follows directly from Farka’s Lemma. A simplified and intuitive version of this lemma states that every vector is either a member of a closed convex cone or there exists a hyperplane separating the vector from the cone.
For example, suppose is the vector and is the closed convex cone. Then Farka’s Lemma states that either , or there exists a vector such that and for every , that is, the hyperplane orthogonal to separates from . Notice that , and so having this be nonnegative for every is equivalent to having . This is summarized in the following:
Farka’s Lemma. Suppose is a closed convex cone. Then , is feasible if and only if every with satisfies .
Theorem. (P) is feasible and has bounded optimal value if and only if (D) is feasible and has bounded optimal value .
Proof: Let’s put our problem into a simple form where Farka’s Lemma applies. We’ll start with (P), though the symmetry in the problem means the same type of arguments apply when starting with (D). Let (P) be feasible with finite optimal value . Then
We also claim that
Indeed, otherwise, there would be some vector such that and , and so for any which is feasible in (P), we would have that is also feasible in (P) for any , but then would exceed for large, contradicting the assumption.
Let for some . Then
(The case corresponds to the previous display.) Equivalently,
In this lifted space, we apply Farka’s Lemma to get that the following is feasible:
The first row yields , meaning (D) is feasible. The second row yields , but by weak duality. We conclude , thereby implying strong duality.
— Complementary Slackness —
The concept of complimentary slackness comes directly from strong duality. For feasible and feasible , weak duality gives
or equivalently, . By strong duality, and are optimal if and only if these inequalities are equal. That is,
In this way, the primal variable is complementary to the dual constraint just as the dual variable is complementary to the primal constraint . These orthogonality relations are sometimes helpful when expressing the optimal (called the dual certificate) in terms of the optimal .