I'm reading Convex Optimization from Prof. Boyd and I got some question on the important usage of proper cone in convex optimization. Other than generalized inequalities, is there any other use of proper cone in convex optimization?
[Math] Why concept of proper cone is important in convex optimization
convex optimization
Related Solutions
Consider two sets: $$C_1=\left\{(x_1,x_2)\,|\,x_1\geq 0,~x_2=0\right\}$$ $$C_2=\left\{(x_1,x_2)\,|\,x_1,x_2\geq 0\right\}$$ $C_1$ and $C_2$ are both closed, convex cones, but only $C_2$ has a non-empty interior. It's simply the standard set definition: a set has a non-empty interior if it includes points that are not on its boundary. The point $(1,1)$ is on the interior of $C_2$, but every point in $C_1$ is of the form $(x_1,0)$, which is on its boundary, so $C_1$ has no interior.
There are some good reasons why it is worthwhile to focus on cones with non-empty interiors. Boyd et. al. define a "proper" cone as a cone that is closed and convex, has a non-empty interior, and contains no straight lines. The dual of a proper cone is also proper. For example, the dual of $C_2$, which is proper, happens to be itself. The dual of $C_1$, on the other hand, is $$C_1^*=\left\{(x_1,x_2)\,|\,x_1\geq 0\right\}$$ Note that $C_1$ has a non-empty interior; $C_1^*$ has a non-empty interior, but contains straight lines. Proper cones establish partial orderings that mimic a lot of the useful properties of standard inequalities. See the discussion of "generalized inequalities" in that book, or even elsewhere on Math.SE.
From a practical standpoint, algorithms to solve problems involving cone constraints (e.g., barrier methods) generally depend on the cones being proper. Cones that have an empty interior or contain straight lines can generally be represented by combinations of equations and constraints involving proper cones.
First, what basically distinguishes the definitions of convex, affine and cone, is the domain of the coefficients and the constraints that relate them.
Let us starts by the first part: any subspace is affine, which means, if we have:
$x_1, x_2 \in V$, where $V$ is a subspace; therefore any linear combination of these two vectors must lie in $V$. That is, if we have two coefficients $\theta_1, \theta_2 \in \mathcal{R}$, then, $\theta_1x_1 + \theta_2x_2 \in V$.
The definition of affine sets tells us if $x_1,x_2$ are in an affine set, their linear combination must also lie in the same set, with the condition the coefficients must sum to 1, that is $\theta_1 + \theta_2 = 1$. Now, assume we have chosen $\theta_2 = 1- \theta_1$, therefore the combination $\theta_1x_1 + (1 - \theta_1)x_2 \in V$
Therefore any subspace is affine, since we have the freedom to choose the coefficients to sum to 1.
Now why a subspace is a convex cone.
Notice that, if we choose the coeficientes $\theta_1, \theta_2 \in \mathcal{R}_+$, we actually define a cone, and if the coefficients sum to 1, it is convex, therefore it is a convex cone.
Best Answer
A standard form linear program (LP) is an optimization problem of the form \begin{align} \text{minimize} & \quad c^T x \\ \text{subject to} & \quad Ax = b , \\ & \quad x \geq 0. \end{align}
If we express the constraint $x \geq 0$ as $x \in \Omega$, where $\Omega$ is the nonnegative orthant (which is a closed convex cone), then we can see a way to generalize the standard form LP to a larger class of problems. A "cone program" is an optimization problem of the form \begin{align} \text{minimize} & \quad \langle c, x \rangle \\ \text{subject to} & \quad Ax = b , \\ & \quad x \in C, \end{align} where $C$ is a closed convex cone. (Now $C$ does not have to be the nonnegative orthant.)
There are two especially interesting cases:
1) $C$ is a second-order cone, or more generally $C = C_1 \times \cdots \times C_m$ where each $C_i$ is a second-order cone. In this case, our cone program is called a "second-order cone program" (SOCP).
2) $C$ is a positive semidefinite cone, or more generally $C = C_1 \times \cdots \times C_m$ where each $C_i$ is a positive semidefinite cone. In this case, our cone program is called a "semidefinite program" (SDP).
Why are these two cases especially interesting? For two reasons:
1) Many practical problems can be expressed as SOCPs or as SDPs. (See the Boyd and Vandenberghe textbook for many examples, as well as tricks for expressing convex optimization problems as SOCPs or SDPs.)
2) Efficient algorithms (interior point methods) for solving linear programs can be generalized, yielding efficient algorithms for solving SOCPs and SDPs.
And what is so special about the second-order cone and the positive semidefinite cone that makes it possible to solve them so efficiently with interior point methods? It has to do with the fact that these cones, like the nonnegative orthant, are "self-dual" and "symmetric". But hopefully somebody else can provide more details about this point. One good reference for this material is the lecture "Symmetric cones" in Vandenberghe's 236c notes: http://www.seas.ucla.edu/~vandenbe/ee236c.html
Another viewpoint is that if we want to develop convex optimization theory in the setting of a real inner product space, we must figure out what the statement $x \leq y$ should mean. And this leads us to discover the concept of a convex cone.