Second-order cone programming

Article summary

A second-order cone program (SOCP) is a convex optimization problem of the form :minimize \ f^T x \ :subject to :: \lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m :: Fx = g \ where the problem parameters are f \in \mathbb{R}^n, \ A_i \in \mathbb{R}^{{n_i}\times n}, \ b_i \in \mathbb{R}^{n_i}, \ c_i \in \mathbb{R}^n, \ d_i \in \mathbb{R}, \ F \in \mathbb{R}^{p\times n} , and g \in \mathbb{R}^p . x\in\mathbb{R}^n is the optimization variable. \lVert x \rVert_2 is the Euclidean norm and ^T indicates transpose. The name "second-order cone programming" comes from the nature of the individual constraints, which are each of the form: :: \lVert A x + b \rVert_2 \leq c^T x + d These each define a subspace that is bounded by an inequality based on a second-order polynomial function defined on the optimization variable x ; this can be shown to define a convex cone, hence the name "second-order cone". 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. SOCPs can be solved by interior point methods and in general, can be solved more efficiently than semidefinite programming (SDP) problems.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.