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:

- , , , ,
- ,

## Cone programs

A *cone program* is an optimization problem of the form

with .

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 .

## Fenchel duality

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

which 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

or equivalently

We have and

or

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
- and
- and

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

and .

This, then, becomes

## Up next

Operator splitting algorithms to solve cone programs.