Second-order cone programming: Difference between revisions

Revision as of 09:22, 1 August 2025

Latest revision as of 19:41, 1 August 2025

(3 intermediate revisions by one other user not shown)

Line 12:

<math>\lVert x \rVert_2 </math> is the [[Euclidean norm]] and <math>^T</math> indicates [[transpose]].<ref name="boyd">{{cite book |last1=Boyd |first1=Stephen |last2=Vandenberghe |first2=Lieven |title=Convex Optimization |publisher=Cambridge University Press |year=2004 |isbn=978-0-521-83378-3 |url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |accessdate=July 15, 2019}}</ref>

The name "second-order cone programming" comes from the nature of the individual constraints, which are each of the form:

::<math>\lVert A_iA x + b_ib \rVert_2 \leq c_ic^T x + d_id</math>

These each define a subspace that is bounded by an inequality based on a [[Degree of a polynomial|second-order polynomislpolynomial]] function defined on the optimization variable <math>x</math>; this can be shown to define a [[convex cone]], hence the name "'''second-order cone'''".<ref>{{Cite journal |lastlast1=Jibrin |firstfirst1=Shafiu |last2=Swift |first2=James W. |date=2024 |title=On Second-Order Cone Functions |url=https://onlinelibrary.wiley.com/doi/abs/10.1155/2024/7090058 |journal=Journal of Optimization |language=en |volume=2024 |issue=1 |pages=7090058 |doi=10.1155/2024/7090058 |doi-access=free |issn=2314-6486}}</ref> 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]]<ref>{{cite journal|last1=Potra|first1=lorian A.|last2=Wright|first2=Stephen J.|date=1 December 2000|title=Interior-point methods|journal=Journal of Computational and Applied Mathematics|volume=124|issue=1–2|pages=281–302|doi=10.1016/S0377-0427(00)00433-7|bibcode=2000JCoAM.124..281P|doi-access=}}</ref> and in general, can be solved more efficiently than [[semidefinite programming]] (SDP) problems.<ref name="Fawzi" /> Some engineering applications of SOCP include filter design, antenna array weight design, truss design, and grasping force optimization in robotics.<ref name=":0">{{Cite journal|last1=Lobo|first1=Miguel Sousa|last2=Vandenberghe|first2=Lieven|last3=Boyd|first3=Stephen|last4=Lebret|first4=Hervé|date=1998|title=Applications of second-order cone programming|journal=Linear Algebra and Its Applications|language=en|volume=284|issue=1–3|pages=193–228|doi=10.1016/S0024-3795(98)10032-0|doi-access=free}}</ref> Applications in [[quantitative finance]] include [[portfolio optimization]]; some [[market impact]] constraints, because they are not linear, cannot be solved by [[quadratic programming]] but can be formulated as SOCP problems.<ref>{{cite web |title=Solving SOCP |url=https://docs.mosek.com/slides/2017/shanghai/talk.pdf}}</ref><ref>{{cite web |title=portfolio optimization |url=https://nmfin.tech/wp-content/uploads/2020/06/new-technologies-in-portfolio-optimization.20200612.pdf}}</ref><ref>{{cite book |last1=Li |first1=Haksun |title=Numerical Methods Using Java: For Data Science, Analysis, and Engineering |date=16 January 2022 |publisher=APress |pages=Chapter 10 |isbn=978-1484267967 }}</ref>