19
$\begingroup$

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?

$\endgroup$
4
  • 8
    $\begingroup$ I don't know why this question would be downvoted, because it's an interesting question and I hope there are some good answers. A simple answer is that we can't define a "second-order cone program" (SOCP) or a "semidefinite program" (SDP) without first knowing what the second-order cone is and what the positive semidefinite cone is. And SOCPs and SDPs are very important in convex optimization, for two reasons: 1) Efficient algorithms are available to solve them; 2) Many practical problems can be formulated as SOCPs or SDPs. $\endgroup$
    – littleO
    Apr 27, 2017 at 2:39
  • 1
    $\begingroup$ The word proper had various meanings when it comes to cones. $\endgroup$
    – copper.hat
    Apr 27, 2017 at 3:31
  • 4
    $\begingroup$ The question should state the definition of a proper cone, but I checked and in Boyd and Vandenberghe a "proper cone" is a cone that is closed, convex, solid (nonempty interior), and pointed (does not contain a line). I guess these are the properties you need when defining a generalized inequality. $\endgroup$
    – littleO
    Apr 27, 2017 at 3:45
  • 3
    $\begingroup$ The point of the proper cone is that it defines an order $\le$. $\endgroup$
    – copper.hat
    Apr 27, 2017 at 4:30

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for a clear explanation. I think in the book there is an explanation for why second-order cone and positive semidefinite is self-dual. $\endgroup$
    – MakaraPr
    Apr 27, 2017 at 5:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .