Example(Facility Location Problem) of SOCPs

E.g. #1

Example:

min⁡x⃗∑i=1m∣∣Aix⃗−b⃗i∣∣2\begin{split} \min_{\vec{x}} \sum_{i=1}^m ||A_i\vec{x} - \vec{b}_i||_2 \end{split}

Let ∣∣Aix⃗−b⃗i∣∣2=yi||A_i \vec{x} - \vec{b}_i||_2 = y_i

min⁡x⃗∑i=1myis.t.∣∣Aix⃗−bi⃗∣∣2=yi\min_{\vec{x}} \sum_{i=1}^m y_i \\ \text{s.t.} \\ ||A_i\vec{x}-\vec{b_i}||_2 = y_i

Relaxation:

min⁡x⃗,yi∑i=1myis.t.∣∣Aix⃗−bi⃗∣∣2≤yi\min_{\vec{x}, y_i} \sum_{i=1}^m y_i \\ \text{s.t.} \\ ||A_i\vec{x}-\vec{b_i}||_2 \le y_i

E.g. #2

min⁡x⃗{max⁡i=1,…,m∣∣Aix⃗−bi∣∣2}\min_{\vec{x}} \{ \max_{i=1, \dots, m} ||A_i\vec{x}-b_i||_2 \}

⇒

min⁡x⃗,yys.t.∣∣Aix⃗−b⃗i∣∣2≤y,∀i=1,…,m\min_{\vec{x}, y} y \\ \text{s.t.} \\ ||A_i \vec{x} - \vec{b}_i||_2 \le y, \forall i = 1,\dots, m

Facility Location Problem