9
where
11 1
,, ,,and
ni ni m ni m
ii i i
RR RRK
×× ××
∈∈ ∈∈
cxAb is a second-order cone of dimension n
i
.
□ We note an analogy between SOCP and LP: both involve a linear objective function and a set of linear
equality constraints. While the variable x in an LP problem is constrained to the region
{: }≥ 0xx which is
a convex cone, each variable vector x
i
in an SOCP problem is constrained to the second-order cone K
i
.
♦ The dual SOCP problem assumes the form
(
D)
maximize
subject to: for 1, 2,...,
for 1, 2,...,
T
T
iii
ii
iq
iq
+= =
∈=
by
Ay s c
s
□ We also notice a similar analogy between the dual SOCP and dual LP problems.
♦ Now if we let
, and
T
i
T
i
ii
T
i
i
d
⎡⎤
⎤
=− = =
⎢⎥
⎥
⎦
⎣⎦
b
xyA c
c
A
then the dual SOCP problem can be expressed as
(
D’)
minimize
subject to: for 1, 2,...,
T
TT
iii i
di q+≤ + =
bx
Ax c bx
□ An example: Linear fractional problem
1
1
minimize
subject to: 0 for 1, 2,...,
0 for 1, 2,...,
p
T
i
ii
T
ii
T
ii
c
cip
diq
=
+
+> =
+≥ =
∑
ax
ax
bx
By introducing auxiliary constraints
1
i
T
ii
c
+ax
i.e.,
()1
T
ii i
c
δ
≥ax
the linear fractional problem can be formulated as
1
minimize
subject to: ( ) 1 for 1, 2,...,
0
0
p
i
i
T
ii i
i
T
ii
cip
d
δ
δ
δ
=
+≥ =
≥
+≥
∑
ax
bx
We can show that
2
,0,0wuvu v≤≥≥ if and only if
2w
uv
uv
⎡⎤
+
⎢⎥
−
⎣⎦