2.7 Semidefinite Optimization Formulation
23
after also noting that all the permutations of i, j, k lead to this same quadratic
expression once expanded.
We next turn to the objective function (2.35) and seek to express betweenness
using the γ ij variables. This is straightforward after we observe that department k is
between i and j if and only if γ ki γ kj = −1, and if and only if
1−γ ki γ kj
2
= 1. Using
this observation, we can express (2.35) in terms of the γ variables:
i
⎛
⎜
⎜
⎝
1
2
(( i + j ) +
n
k=1
k =i,j
k
1 − γ ki γ kj
2
⎞
⎟
⎟
⎠ .
If we want to avoid the occurrence of indices ij with i > j, using our earlier
observation that γ ij = −γ ji allows us to rewrite the objective function in the
following form:
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k γ ik γ jk
⎤
⎦ .
We can now write a fully quadratic formulation of the SRFLP:
minimize
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k γ ik γ jk
⎤
⎦
(2.58)
s.t. γ ij γ jk − γ ij γ ik − γ ik γ jk = −1, 1 ≤ i < j < k ≤ n,
(2.59)
γ
2
ij = 1, 1 ≤ i < j ≤ n.
(2.60)
We next use this fully quadratic formulation to obtain a rank-constrained SDO
formulation of the SRFLP. Since SDO is an optimization problem over matrices, we
need to define a matrix variable. Let us define the column vector
g := (γ 12 , γ 13 , . . . , γ 1n , γ 23 , . . . , γ n−1 n )
T ,
and hence the rank-one matrix
Γ := g g
T .
(2.61)
By construction, we have that Γ p,q = γ p γ q for every pair p, q of departments.
Note that the matrix Γ is indexed by pairs of departments, like the variable Y
in Sect. 2.6.1. Using this fact, we can linearize the formulation (2.58)–(2.60) by
expressing every quadratic term in terms of entries of Γ .
23
after also noting that all the permutations of i, j, k lead to this same quadratic
expression once expanded.
We next turn to the objective function (2.35) and seek to express betweenness
using the γ ij variables. This is straightforward after we observe that department k is
between i and j if and only if γ ki γ kj = −1, and if and only if
1−γ ki γ kj
2
= 1. Using
this observation, we can express (2.35) in terms of the γ variables:
i
⎛
⎜
⎜
⎝
1
2
(( i + j ) +
n
k=1
k =i,j
k
1 − γ ki γ kj
2
⎞
⎟
⎟
⎠ .
If we want to avoid the occurrence of indices ij with i > j, using our earlier
observation that γ ij = −γ ji allows us to rewrite the objective function in the
following form:
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k γ ik γ jk
⎤
⎦ .
We can now write a fully quadratic formulation of the SRFLP:
minimize
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k γ ik γ jk
⎤
⎦
(2.58)
s.t. γ ij γ jk − γ ij γ ik − γ ik γ jk = −1, 1 ≤ i < j < k ≤ n,
(2.59)
γ
2
ij = 1, 1 ≤ i < j ≤ n.
(2.60)
We next use this fully quadratic formulation to obtain a rank-constrained SDO
formulation of the SRFLP. Since SDO is an optimization problem over matrices, we
need to define a matrix variable. Let us define the column vector
g := (γ 12 , γ 13 , . . . , γ 1n , γ 23 , . . . , γ n−1 n )
T ,
and hence the rank-one matrix
Γ := g g
T .
(2.61)
By construction, we have that Γ p,q = γ p γ q for every pair p, q of departments.
Note that the matrix Γ is indexed by pairs of departments, like the variable Y
in Sect. 2.6.1. Using this fact, we can linearize the formulation (2.58)–(2.60) by
expressing every quadratic term in terms of entries of Γ .