Content deleted Content added
→Solvers and scripting (programming) languages: clean out external links per WP:EL, WP:NOTDIR |
→Relation with other optimization problems: Rewrite part about convex semialgebraic sets to make the relation to SOCPs clearer |
||
Line 43:
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>
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 == Examples ==
| |||