where the problem parameters are , and . is the optimization variable. is the Euclidean norm and indicates transpose.[1]
The name "second-order cone programming" comes from the nature of the individual constraints, which are each of the form:
These each define a subspace that is bounded by an inequality based on a second-order polynomial function defined on the optimization variable ; this can be shown to define a convex cone, hence the name "second-order cone".[2] By the definition of convex cones, their intersection can also be shown to be a convex cone, although not necessarily one that can be defined by a single second-order inequality. See below for a more detailed treatment.
i.e., a second-order cone constraint is equivalent to a linear matrix inequality. The nomenclature here can be confusing; here means is a semidefinite matrix: that is to say
which is not a linear inequality in the conventional sense.
Similarly, we also have,
.
Relation with other optimization problems
A hierarchy of convex optimization problems. (LP: linear program, QP: quadratic program, SOCP second-order cone program, SDP: semidefinite program, CP: cone program.)
When for , the SOCP reduces to a linear program. When for , the SOCP is equivalent to a convex quadratically constrained linear program.
Convex quadratically constrained quadratic programs can also be formulated as SOCPs by reformulating the objective function as a constraint.[5]Semidefinite programming subsumes SOCPs as the SOCP constraints can be written as linear matrix inequalities (LMI) and can be reformulated as an instance of semidefinite program.[5] The converse, however, is not valid: there are positive semidefinite cones that do not admit any second-order cone representation.[4]
Any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP,.[9] However, it is known that there exist convex semialgebraic sets of higher dimension that are not representable by SDPs; that is, there exist convex semialgebraic sets that can not be written as the feasible region of a SDP (nor, a fortiori, as the feasible region of a SOCP).[10]
We refer to second-order cone programs as deterministic second-order cone programs since data defining them are deterministic. Stochastic second-order cone programs are a class of optimization problems that are defined to handle uncertainty in data defining deterministic second-order cone programs.[11]
Other examples
Other modeling examples are available at the MOSEK modeling cookbook.[12]
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.