Content deleted Content added
mNo edit summary |
No edit summary |
||
Line 7:
<math>Fx = g \ </math>
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>. Here <math>x\in\mathbb{R}^n</math> is the optimization variable. 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 quadratic program]]. SOCPs can b solved with great efficiency by [[interior point methods]].
==Example: Robust Linear Programming==
Consider a linear program in inequality form
:minimize <math>\ c^T x \ </math> subject to
: <math>a_i^T(x) \leq b_i, \quad i = 1,\dots,m </math>
where the parameters <math>a_i \ </math> are independent Gaussian random vectors with mean <math>\bar{a}_i</math> and covariance <math>\Sigma_i \ </math>. We require that each constraint <math>a_i^T x \leq b_i </math> should hold with a probability exceeding <math>\eta</math>, where <math>\eta\geq0.5</math>, i.e. <math>P(a_i^T x \leq b_i ) \geq \eta </math>. This problem can be expressed as the SOCP
:minimize <math>\ c^T x \ </math> subject to
: <math>\bar{a}_i^T (x) + \Phi^{-1}(\eta) \lVert \Sigma_i^{1/2} x \rVert_2 \leq b_i , \quad i = 1,\dots,m </math>
[[Category:Optimization]]
| |||