This post aims at providing some intuition into cone programs from different perspectives; in particular:
- Equivalence of different formulations of cone programs
- Fenchel duality
- Primal-dual optimality conditions (OC)
- OCs as variational inequalities
- Homogeneous self-dual embeddings (HSDEs)
- OCs for HSDEs
Cones and their properties
A set in a vector space is called a cone if for every and it is closed
under addition. is said to be a pointed cone if and imply . Pointed cones define the partial ordering:
The polar of a cone is a cone defined as
If is closed, then and the indicators of and are conjugate to each other, that is
The dual cone of is defined as
If is a closed, convex cone, then and .
This result is known as the extended Farkas’ lemma.
Interesting examples of conex are
- the set of positive semidefinite matrices which is a closed, convex, pointed cone,
- the icecream cone , and
- polyhedral cones , for some matrix .
The conjugate of a function is defined as
If , then . For all , if , .
The subdifferential of a convex function at a point is
The subdifferential of the indicator function of a convex set is
This function is called the normal cone of .
Moreau’s Theorem establishes an important duality correspondence between a cone and its polar cone :
For all , the following are equivalent:
- , , , ,
A cone program is an optimization problem of the form
The constraint can be equivalently written as (i) , that is , or (ii) for . Problem is often written as
In the literature, we often encounter the following standard formulation for a cone program
These two formulations — problems and — are equivalent in the sense that we may transform one into the other.
For instance, starting from the second one, we clearly see that the constraints can be interpreted as (i) belongs to an affine space defined as and (ii) , that is, is contained in a cone. Essentially, must be in the intersection of a cone and an affine space.
Take so that and let be a matrix that spans the kernel of (which has dimension ), that is for all .
Then and the requirement that is written as , so the problem becomes
which is in the form of .
Conversely, can be written in the form of problem .
The dual of problem can be derived using the Fenchel duality framework.
Define and . Then, problem can be written as
whose Fenchel dual is
The conjugates of and are [note: The conjugate of is derived as follows: , so .]
and the Fenchel dual problem is
Let be the optimal value of and
be the optimal value of . Then, strong duality holds if the primal or the dual problem are strictly feasible and then .
Overall, we may derive the following optimality conditions for a pair to be a primal-dual optimal pair
These optimality conditions can be seen as the following conditions on
Here note that the equality is equivalent to zero duality gap, that is .
Optimality conditions from a different perspective
The optimality conditions of (using the splitting we introduced in the previous section) are simply
and, provided that has a nonempty relative interior, this is equivalent to
We have and
Since is a nonempty convex cone, we have (book of Hiriart-Urruty and Lemaréchal, Example 5.2.6 (a))
This yields the primal-dual optimality conditions we stated above.
Unboundedness and infeasibility
Infeasibility and unboundedness (dual infeasibility) conditions are provided by the so-called theorems of the alternative. The weak theorems of the alternative, state that
- (Primal feasibility). At most one of the following two systems is solvable
- (i.e., or for some )
- , and
- (Dual feasibility). At most one of the following two systems is solvable
The primal-dual optimality conditions we stated previously together with these
feasibility conditions make the whole picture.
Homogeneous Self-Dual Embeddings
Consider the following feasibility problem in and
Note that for and , the above equations collapse to the
primal-dual optimality conditions. Second, due to the skew-symmetry of the above system, any solution and satisfies
which leads to , but since we already know that , it is , i.e., at least one of the two must be zero.
If and , then is a solution. If and , then the problem is either primal- or dual-infeasible. If , no definitive conclusion can be drawn.
Let us define and . Then, the self-dual embedding becomes
where . The problem can now be cast as an optimization problem
Furthermore, this is equivalent to the variational inequality
This, then, becomes
Operator splitting algorithms to solve cone programs.