Second-order cone programming: Difference between revisions

Revision as of 18:59, 3 March 2023

Latest revision as of 19:41, 1 August 2025

(44 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Convex optimization problem}}

{{Technical|date=October 2011}}

Line 9 ⟶ 10:

where the problem parameters are <math>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}</math>, and <math>g \in \mathbb{R}^p</math>. <math>x\in\mathbb{R}^n</math> is the optimization variable.

<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 "second-order cone" in SOCP arises from the constraints, which are equivalent to requiring the affine function <math>(A x + b, c^T x + d)</math> to lie in the second-order [[Convex_cone|cone]] in <math>\mathbb{R}^{n_i + 1}</math>.<ref name="boyd"/>

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

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=free}}</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>

::<math>\lVert A x + b \rVert_2 \leq c^T x + d</math>

== Second-order cone ==

These each define a subspace that is bounded by an inequality based on a [[Degree of a polynomial|second-order polynomial]] 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 |last1=Jibrin |first1=Shafiu |last2=Swift |first2=James W. |date=2024 |title=On Second-Order Cone Functions |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=free}}</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>

== Second-order conecones ==

The standard or unit second-order cone of dimension <math>n+1</math> is defined as

:<math>\mathcal{C}_{n+1}=\left\{ \begin{bmatrix} x \\ t \end{bmatrix} \Bigg| x \in \mathbb{R}^n,

t\in \mathbb{R}, |\|x|\|_2\leq t \right\}</math>.

The second-order cone is also known by the names '''quadratic cone''' or '''ice-cream cone''' or '''Lorentz cone'''. For example, the standard second-order cone in <math>\mathbb{R}^3</math> is

The second-order cone is also known by ''quadratic cone'', ''ice-cream cone'', or ''Lorentz cone''. The second-order cone in <math>\mathbb{R}^3</math> is :<math>\left\{(x,y,z) \Big| \sqrt{x^2 + y^2} \leq z \right\}</math>.

The set of points satisfying a second-order cone constraint is the inverse image of the unit second-order cone under an affine mapping:

:<math>\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i \Leftrightarrow

\begin{bmatrix} A_i \\ c_i^T \end{bmatrix} x + \begin{bmatrix} b_i \\ d_i \end{bmatrix} \in

\mathcal{C}_{n_i+1}</math>

Line 29 ⟶ 38:

and hence is convex.

The second-order cone can be embedded in the cone of the [[positive semidefinite matrices]] since

:<math>||x||\leq t \Leftrightarrow \begin{bmatrix} tI & x \\ x^T & t \end{bmatrix} \succcurlyeq 0,</math>

i.e., a second-order cone constraint is equivalent to a [[linear matrix inequality]]. The nomenclature here can be confusing; (Herehere <math>M\succcurlyeq 0 </math> means <math>M </math> is a semidefinite matrix).: Similarly,that weis alsoto have,say

:<math>\lVertx^T A_iM x +\geq b_i0 \rVert_2text{ \leqfor c_i^Tall } x + d_i \Leftrightarrowin \mathbb{R}^n</math>

which is not a linear inequality in the conventional sense.

Similarly, we also have,

:<math>\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i \Leftrightarrow

\begin{bmatrix} (c_i^T x+d_i)I & A_i x+b_i \\ (A_i x + b_i)^T & c_i^T x + d_i \end{bmatrix} \succcurlyeq 0</math>.

Line 42 ⟶ 57:

When <math>A_i = 0</math> for <math>i = 1,\dots,m</math>, the SOCP reduces to a [[linear program]]. When <math>c_i = 0 </math> for <math>i = 1,\dots,m</math>, the SOCP is equivalent to a convex quadratically constrained linear program.

Convex [[quadratically constrained quadratic program]]s can also be formulated as SOCPs by reformulating the objective function as a constraint.<ref name=":0" /> [[Semidefinite programming]] subsumes SOCPs as the SOCP constraints can be written as [[linear matrix inequality|linear matrix inequalities]] (LMI) and can be reformulated as an instance of semidefinite program.<ref name=":0" /> The converse, however, is not valid: there are positive semidefinite cones that do not admit any second-order cone representation.<ref name="Fawzi">{{Cite journal|last=Fawzi|first=Hamza|date=2019|title=On representing the positive semidefinite cone using the second-order cone|journal=Mathematical Programming|language=en|volume=175|issue=1–2|pages=109–118|doi=10.1007/s10107-018-1233-0|issn=0025-5610|arxiv=1610.04901|s2cid=119324071}}</ref> In fact, while any

Any closed convex [[semialgebraic set]] in the plane can be written as a feasible region of a SOCP,.<ref>{{cite arXiv|last=Scheiderer|first=Claus|date=2020-04-08|title=Second-order cone representation for convex subsets of the plane|class=math.OC|eprint=2004.04196}}</ref> 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 athe feasible region of a SDP (nor, <em>a fortiori</em>, as the feasible region of a SOCP).<ref>{{Cite journal|last=Scheiderer|first=Claus|date=2018|title=Spectrahedral Shadows|journal=SIAM Journal on Applied Algebra and Geometry|language=en|volume=2|issue=1|pages=26–44|doi=10.1137/17M1118981|issn=2470-6566|doi-access=free}}</ref>

== Examples ==

Line 73 ⟶ 90:

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.<ref>{{Cite journal |last=Alzalg |first=Baha M. |date=2012-10-01 |title=Stochastic second-order cone programming: Applications models |url=https://www.sciencedirect.com/science/article/pii/S0307904X11008547 |journal=Applied Mathematical Modelling |language=en |volume=36 |issue=10 |pages=5122–5134 |doi=10.1016/j.apm.2011.12.053 |issn=0307-904X|url-access=subscription }}</ref>

=== Other examples ===

Other modeling examples are available at the MOSEK modeling cookbook.<ref>{{Cite web |title=MOSEK Modeling Cookbook - Conic Quadratic Optimization |url=https://docs.mosek.com/modeling-cookbook/cqo.html}}</ref>

==Solvers and scripting (programming) languages==

Line 82 ⟶ 102:

!License

!Brief info

|-

|[[ALGLIB]]||free/commercial|| A dual-licensed C++/C#/Java/Python numerical analysis library with parallel SOCP solver.

|-

|[[AMPL]]||commercial|| An algebraic modeling language with SOCP support

Line 91 ⟶ 113:

|[[FICO Xpress]]||commercial||

|-

|[[Gurobi Optimizer]]||commercial||

|-

|[[MATLAB]]||commercial||The <code>coneprog</code> function solves SOCP problems<ref>{{cite web | title=Second-order cone programming solver - MATLAB coneprog | website=MathWorks | date=2021-03-01 | url=https://www.mathworks.com/help/optim/ug/coneprog.html | access-date=2021-07-15}}</ref> using an interior-point algorithm<ref>{{cite web | title=Second-Order Cone Programming Algorithm - MATLAB & Simulink | website=MathWorks | date=2021-03-01 | url=https://www.mathworks.com/help/optim/ug/cone-programming-algorithm.html | access-date=2021-07-15}}</ref>

Line 99 ⟶ 121:

|[[NAG Numerical Library]]||commercial|| General purpose numerical library with SOCP solver

|}

== See also ==

* [[Power cone]]s are generalizations of quadratic cones to powers other than 2.<ref>{{Cite web |title=MOSEK Modeling Cookbook - the Power Cones |url=https://docs.mosek.com/modeling-cookbook/powo.html}}</ref>

==References==