Murota K. Matrices and Matroids for Systems Analysis
Подождите немного. Документ загружается.
322 5. Polynomial Matrix and Valuated Matroid
Proof. In addition to the above argument note that the case = 0 corresponds
to an optimal M , for which (5.68) is vacuously true due to Theorem 5.2.42.
Under the condition (5.68) we define (M) to be the minimum value of
≥ 0 for which M is -optimal. The above argument shows, under (5.69),
that
(M)=−μ. (5.71)
The following lemma substantiates the step (i) of the algorithm.
Lemma 5.2.57. Assume (5.68) and (5.69),andletQ be a minimum-ratio
cycle. Either Q is admissible or else it induces a minimum-ratio cycle having
a smaller number of arcs than Q. In particular, a minimum-ratio cycle having
the smallest number of arcs is admissible.
Proof. We modify the proof of Lemma 5.2.44. Let
B
+
and B
−
be defined
by (5.64) and (5.65). Suppose that Q is not admissible, and assume without
loss of generality that (B
+
, B
+
) does not satisfy the unique-max condition.
Take a maximum-weight perfect matching M
in G(B
+
, B
+
)forM
+
.Put
Q
=(Q\A
+
)∪M
, which is a collection of disjoint cycles, say Q
=
l
j=1
Q
j
.
Then α(Q
)=α(Q) (since α(M
)=α(Q ∩ A
+
) = 0) and
γ(Q
)=γ(Q)+[γ(M
) − γ(Q ∩ A
+
)] (5.72)
holds. By the choice of M
we have γ(Q
) ≤ γ(Q), which implies
γ(Q
)/α(Q
) ≤ γ(Q)/α(Q)=μ. (5.73)
We claim that the equality holds in (5.73). In fact, (5.73) shows
γ(Q
)=
l
j=1
γ(Q
j
) ≤ μα(Q
)=μ
l
j=1
α(Q
j
),
whereas γ(Q
j
) ≥ μα(Q
j
) for all j by (5.68) and (5.70). With the equality in
(5.73) we obtain γ(Q
)=γ(Q) since α(Q
)=α(Q).
It then follows from (5.72) that
γ(Q ∩ A
+
)=γ(M
)=−6ω
+
(B
+
, B
+
). (5.74)
Hence, putting
M
= Q ∩ A
+
= {(u
i
,v
i
) | i =1, ···,m}
we have M
⊆ A
∗
, where
A
∗
= {(u, v) | u ∈ B
+
\ B
+
,v ∈ B
+
\ B
+
,ω
+
(B
+
,u,v) − 6p(u)+6p(v)=0},
5.2 Valuated Matroid 323
and 6p is the potential function in Lemma 5.2.32(1).
Since (B
+
, B
+
) does not satisfy the unique-max condition, there exist
distinct indices i
k
(k =1, ···,q; q ≥ 2) such that (u
i
k
,v
i
k+1
) ∈ A
∗
for k =
1, ···,q, where i
q+1
= i
1
. Then
ω
+
(B
+
,u
i
k
,v
i
k+1
)=6p(u
i
k
) − 6p(v
i
k+1
)(k =1, ···,q),
ω
+
(B
+
,u
i
k
,v
i
k
)=6p(u
i
k
) − 6p(v
i
k
)(k =1, ···,q),
q
k=1
γ(u
i
k
,v
i
k+1
)=
q
k=1
γ(u
i
k
,v
i
k
)
hold true, where the second equation is due to M
⊆ A
∗
.
For k =1, ···,q,letP (v
i
k+1
,u
i
k
) denote the path on Q from v
i
k+1
to
u
i
k
, and let Q
k
be the directed cycle formed by arc (u
i
k
,v
i
k+1
) and path
P (v
i
k+1
,u
i
k
). By a similar argument as in the proof of Lemma 5.2.44 we
obtain
q
k=1
(γ(Q
k
) − μα(Q
k
)) = q
(γ(Q) − μα(Q)) = 0
for some q
with 1 ≤ q
<q, which shows γ(Q
k
) − μα(Q
k
)=0foreachk.
Therefore Q
k
is a minimum-ratio cycle for k with α(Q
k
) > 0, while such k
exists since
q
k=1
α(Q
k
)=q
α(Q) > 0.
Lemma 5.2.58. Assume (5.68) and (5.69),andletQ be an admissible
minimum-ratio cycle. Then
M is an independent assignment with Ω(M)=
Ω(M ) − γ
M
(Q).
Proof. The same as the proof of Lemma 5.2.45, except that (5.74) is used.
Lemma 5.2.59. Assume (5.68) and (5.69),andletQ be an admissible
minimum-ratio cycle. Then (M ) ≤ (M) for M =(M \{a ∈ M | a ∈
Q ∩ M
◦
}) ∪ (Q ∩ A
◦
).
Proof.Put = (M), which is equal to −μ by (5.71). By the -optimality of
M,wehave
γ
p
(a) ≡ γ(a)+p(∂
+
a) − p(∂
−
a) ≥−α(a)(a ∈
˜
A)
for some p. Note that
γ
p
(a)=−α(a)(a ∈ Q). (5.75)
Denote by
˜
G
M
=(V,A) the auxiliary graph for M; with obvious additional
notations
A = A
◦
∪ M
◦
∪ A
+
∪ A
−
, γ,andα. We will show
γ
p
(a) ≡ γ(a)+p(∂
+
a) − p(∂
−
a) ≥−α(a)(a ∈ A) (5.76)
324 5. Polynomial Matrix and Valuated Matroid
for the same p. This is obvious for a ∈ M
◦
\ M
◦
since α(a) = 0 and its
reorientation
a ∈ Q ∩ A
◦
satisfies γ
p
(a)=0.
In what follows we show (5.76) for a ∈
A
+
; the proof for the remaining
case with a ∈
A
−
is similar. We abbreviate ω
+
, V
+
, B
+
and B
+
to ω, V , B
and
B respectively. Then (5.76) for a ∈ A
+
can be written as
ω(
B,u,v) ≤ p(u) − p(v)(u ∈ B,v ∈ V \ B) (5.77)
since ω(
B,u,v)=−∞ if (u, v) ∈ A
+
.
Recalling the definition
γ(a)=−ω(B, u,v)(a =(u, v) ∈ A
+
)
and noting α(a)=0(a ∈ A
+
) we see from (5.67) that
ω(B,u,v) ≤ p(u) − p(v)(u ∈ B, v ∈ V \ B). (5.78)
[Note that (u, v) ∈ A
+
implies ω(B,u,v)=−∞.] The equation (5.75) shows
that this is satisfied with equality for (u, v) ∈ Q ∩ A
+
. Hence
6ω(B,
B)=
u∈B\B
p(u) −
v∈B\B
p(v). (5.79)
For u ∈
B and v ∈ V \ B put B
= B − u + v. It follows from
the upper-bound lemma (Lemma 5.2.29), the unique-max lemma (Lemma
5.2.35), (5.78), and (5.79) that
ω(
B,u,v)
= ω(B
) − ω(B)
≤ 6ω(B, B
) − 6ω(B,B)
≤
⎡
⎣
u
∈B\B
p(u
) −
v
∈B
\B
p(v
)
⎤
⎦
−
⎡
⎣
u
∈B\B
p(u
) −
v
∈B\B
p(v
)
⎤
⎦
= p(u) − p(v).
Thus (5.77) is established. It may be remarked that the essence of (5.77) lies
in Lemma 5.2.38.
Combining Lemma 5.2.56 and Lemma 5.2.59 we see that the condition
(5.68) is preserved in updating an independent matching in the step (iii) of
the algorithm. That is, we have the following.
Lemma 5.2.60. Assume (5.68) and (5.69),andletQ be an admissible
minimum-ratio cycle. Then the condition (5.68) is satisfied by
M. 2
We have justified all the claims about the cycle-canceling algorithm with
minimum-ratio cycle selection.
5.2 Valuated Matroid 325
5.2.13 Augmenting Algorithms
This section describes a primal-dual-type augmenting algorithm for the val-
uated independent assignment problem, due to Murota [225]. The algorithm
is an extension of the well-established primal-dual algorithm for the ordinary
independent assignment problem and the weighted matroid intersection prob-
lem. The algorithm will be used in §6.2.6 for an analysis of mixed polynomial
matrices.
Algorithms. The augmenting algorithm for VIAP solves VIAP(k)fork =
0, 1, 2, ···with the aid of the auxiliary graph
˜
G
(M,B
+
,B
−
)
=(
˜
V,
˜
A) introduced
in §5.2.10. The vertex set
˜
V is given by
˜
V = V
+
∪ V
−
∪{s
+
,s
−
},
where s
+
and s
−
are new vertices referred to as the source vertex and the sink
vertex respectively, and the arc set
˜
A consists of eight disjoint components:
˜
A =(A
◦
∪ M
◦
) ∪ (A
+
∪ F
+
∪ S
+
) ∪ (A
−
∪ F
−
∪ S
−
)
with components defined (cf. (5.62)) by
A
◦
= {a | a ∈ A} (copy of A),
M
◦
= {a | a ∈ M } (a: reorientation of a),
A
+
= {(u, v) | u ∈ B
+
,v ∈ V
+
\ B
+
,B
+
− u + v ∈B
+
},
F
+
= {(u, s
+
) | u ∈ V
+
},
S
+
= {(s
+
,v) | v ∈ B
+
\ ∂
+
M},
A
−
= {(v, u) | u ∈ B
−
,v ∈ V
−
\ B
−
,B
−
− u + v ∈B
−
},
F
−
= {(s
−
,u) | u ∈ V
−
},
S
−
= {(v, s
−
) | v ∈ B
−
\ ∂
−
M}.
The arc length γ(a)=γ
(M,B
+
,B
−
)
(a)(a ∈
˜
A) is defined (cf. (5.63)) by
γ(a)=
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
−w(a)(a ∈ A
◦
)
w(
a)(a =(u, v) ∈ M
◦
, a =(v, u) ∈ M)
−ω
+
(B
+
,u,v)(a =(u, v) ∈ A
+
)
−ω
−
(B
−
,u,v)(a =(v, u) ∈ A
−
)
0(a ∈ F
+
∪ S
+
∪ F
−
∪ S
−
).
The following fact is most fundamental.
Lemma 5.2.61. Let (M,B
+
,B
−
) be a feasible solution to VIAP(k).The
problem VIAP(k +1) has a feasible solution if and only if there exists a
directed path from s
+
to s
−
in
˜
G
(M,B
+
,B
−
)
.
326 5. Polynomial Matrix and Valuated Matroid
Proof. First note that the graph
˜
G
(M,B
+
,B
−
)
does not depend on w nor on
ω
±
, except for the arc length. By Theorem 2.3.33 it suffices to prove the
claim that there exists a directed path from s
+
to s
−
in
˜
G
(M,B
+
,B
−
)
if and
only if there exists a directed path from S
+
to S
−
in the auxiliary graph
˜
G
M
of §2.3.5. This claim follows from general facts (i) and (ii) below valid for
I ⊆ B ∈Bin a matroid (V, I, B, cl):
(i) For v ∈ V \ B: v ∈ cl(I) ⇐⇒ ∃u ∈ B \ I : B −u + v ∈B,
(ii) For u ∈ I,v ∈ cl(I) \ I: I − u + v ∈I ⇐⇒ B − u + v ∈B.
Suppose that (M, B
+
,B
−
) is optimal for VIAP(k), and that VIAP(k +1)
is feasible. It follows from Lemma 5.2.61 that there is a (directed) path in
˜
G
(M,B
+
,B
−
)
from the source s
+
to the sink s
−
, and from Theorem 5.2.47 that
there is a shortest path from s
+
to s
−
with respect to γ. Then the following
theorem holds true (Murota [225]).
Theorem 5.2.62. Let (M, B
+
,B
−
) be optimal for VIAP(k) and P be a
shortest path, from the source s
+
to the sink s
−
in
˜
G
(M,B
+
,B
−
)
, having the
smallest number of arcs. Then (
M,B
+
, B
−
) defined by
M =(M \{a ∈ M | a ∈ P ∩ M
◦
}) ∪ (P ∩ A
◦
), (5.80)
B
+
=(B
+
\{∂
+
a | a ∈ P ∩ A
+
}) ∪{∂
−
a | a ∈ P ∩ A
+
}, (5.81)
B
−
=(B
−
\{∂
−
a | a ∈ P ∩ A
−
}) ∪{∂
+
a | a ∈ P ∩ A
−
} (5.82)
is optimal for VIAP(k +1).
Proof. The proof is given later.
With this theorem, we obtain the following algorithm of augmenting type
that solves VIAP(k)fork =0, 1, 2, ···. At the beginning of the algorithm we
set M = ∅ and find a maximum-weight base B
+
of M
+
with respect to ω
+
and a maximum-weight base B
−
of M
−
with respect to ω
−
. Obviously this
choice gives the optimal solution to VIAP(0).
Augmenting algorithm (outline)
Starting from the empty matching M and maximum-weight bases
B
+
and B
−
of M
+
and M
−
with respect to ω
+
and ω
−
, repeat
(i)–(ii) below for k =0, 1, 2, ···:
(i) Find a shortest path P having the smallest number of arcs
from s
+
to s
−
in
˜
G
(M,B
+
,B
−
)
with respect to the arc length
γ
(M,B
+
,B
−
)
.
[Stop if there is no path from s
+
to s
−
.]
(ii) Update (M,B
+
,B
−
)to(M,B
+
, B
−
) by (5.80), (5.81), (5.82).
Remark 5.2.63. The above algorithm is a natural extension of the primal-
dual algorithm for the ordinary independent assignment problem and the
weighted matroid intersection problem due to Iri–Tomizawa [133] and Lawler
[170, 171] (see also Frank [76]). 2
5.2 Valuated Matroid 327
The algorithm outlined above can be made more efficient by the explicit
use of a potential function p :
˜
V → R, the use of which has been invented
independently by Tomizawa [312] and by Edmonds–Karp [71] in the primal-
dual algorithm for the ordinary minimum-cost flow problem.
Suppose again that (M,B
+
,B
−
) is optimal for VIAP(k). By Theorem
5.2.47 there is a potential p :
˜
V → R such that
γ
p
(a) ≡ γ(a)+p(∂
+
a) − p(∂
−
a) ≥ 0(a ∈
˜
A). (5.83)
This condition is equivalent to the following set of conditions appearing in
Theorem 5.2.46(1):
w(a) − p(∂
+
a)+p(∂
−
a)
≤ 0(a ∈ A)
=0(a ∈ M)
(5.84)
B
+
is a maximum-weight base of M
+
with respect to ω
+
[p
+
], (5.85)
B
−
is a maximum-weight base of M
−
with respect to ω
−
[−p
−
], (5.86)
p(u) ≥ p(v)(u ∈ V
+
,v∈ B
+
\ ∂
+
M), (5.87)
p(u) ≤ p(v)(u ∈ V
−
,v∈ B
−
\ ∂
−
M), (5.88)
where p
±
denotes the restriction of p to V
±
and
ω
+
[p
+
](B)=ω
+
(B)+
v∈B
p
+
(v)=ω
+
(B)+
v∈B
p(v)(B ∈B
+
),
ω
−
[−p
−
](B)=ω
−
(B) −
v∈B
p
−
(v)=ω
−
(B) −
v∈B
p(v)(B ∈B
−
).
We maintain such a potential function p in addition to (M,B
+
,B
−
)and
seek a shortest path with respect to the modified arc length γ
p
, which is non-
negative by virtue of (5.83). At the beginning of the algorithm the potential
p is chosen as
p(v)=
0(v ∈ V
+
∪{s
+
})
−max
a∈A
w(a)(v ∈ V
−
∪{s
−
})
(5.89)
which is easily seen to be legitimate. In the general steps p is updated to
p(v)=p(v)+Δp(v)(v ∈
˜
V ) (5.90)
based on the length Δp(v) of the shortest path from the source s
+
to v with
respect to the modified arc length γ
p
.
Augmenting algorithm (with potential)
(Step 0)
(i) Set M = ∅.
(ii) Define p by (5.89).
328 5. Polynomial Matrix and Valuated Matroid
(iii) Find maximum-weight bases B
+
and B
−
of M
+
and M
−
with respect to ω
+
and ω
−
.
(Step 1) Repeat (i)–(iii) below for k =0, 1, 2, ···:
(i) Find a shortest path P having the smallest number of arcs
from s
+
to s
−
in
˜
G
(M,B
+
,B
−
)
with respect to the modified
arc length γ
p
of (5.83).
[Stop if there is no path from s
+
to s
−
.]
(ii) For each v ∈
˜
V compute the length Δp(v) of the shortest
path from s
+
to v in
˜
G
(M,B
+
,B
−
)
with respect to the modified
arc length γ
p
; Update p to p by (5.90).
(iii) Update (M,B
+
,B
−
)to(M,B
+
, B
−
) by (5.80), (5.81),
(5.82).
Remark 5.2.64. In the description of the algorithm above, we have assumed
that Δp(v) takes a finite value for all v in order to focus on the main ideas.
In actual implementations, however, this issue should be taken care of in an
appropriate manner. 2
Validity of the Augmenting Algorithm. We show that (
M,B
+
, B
−
, p)
satisfies the conditions (5.84)–(5.88). It then follows from Theorem 5.2.46
that (
M,B
+
, B
−
) is optimal for VIAP(k + 1). Theorem 5.2.62 also follows
from this.
First note that
M is a matching of size k + 1 and that
γ
p
(a) ≡ γ(a)+p(∂
+
a) − p(∂
−
a)
= γ
p
(a)+Δp(∂
+
a) − Δp(∂
−
a) ≥ 0(a ∈
˜
A) (5.91)
by the definition of Δp.
Lemma 5.2.65.
w(a) −
p(∂
+
a)+p(∂
−
a)
≤ 0(a ∈ A)
=0 (a ∈
M).
Proof. The first follows from (5.91) for a ∈ A
◦
, while the second is due to
γ
p
(a)+Δp(∂
+
a) − Δp(∂
−
a)=γ(a)+p(∂
+
a) − p(∂
−
a)=0 (a ∈ M ∪ P ).
Lemma 5.2.66.
p(u) ≥ p(v)(u ∈ V
+
,v ∈ B
+
\ ∂
+
M),
p(u) ≤ p(v)(u ∈ V
−
,v ∈ B
−
\ ∂
−
M).
5.2 Valuated Matroid 329
Proof. The inequality (5.91) for a =(u, s
+
), (v,s
+
), (s
+
,v) implies p(u) −
p(s
+
) ≥ 0andp(v) − p(s
+
) = 0. The proof for the second claim is similar.
Let
{(u
+
i
,v
+
i
) | i =1, ···,l
+
} = P ∩ A
+
,
{(v
−
i
,u
−
i
) | i =1, ···,l
−
} = P ∩ A
−
,
where l
+
= |P ∩ A
+
|, l
−
= |P ∩ A
−
|, and the indices are chosen so that
u
+
1
,v
+
1
, u
+
2
,v
+
2
, ···, u
+
l
+
,v
+
l
+
represents the order in which they appear on P ,
and similarly for v
−
l
−
,u
−
l
−
, ···, v
−
2
,u
−
2
, v
−
1
,u
−
1
.Wesee
B
+
= B
+
−{u
+
1
, ···,u
+
l
+
} + {v
+
1
, ···,v
+
l
+
}⊇∂
+
M,
B
−
= B
−
−{u
−
1
, ···,u
−
l
−
} + {v
−
1
, ···,v
−
l
−
}⊇∂
−
M.
Lemma 5.2.67.
(1) (B
+
, B
+
) and (B
−
, B
−
) satisfy the unique-max condition in M
+
and
M
−
respectively.
(2)
6ω(B
+
, B
+
)=
l
+
i=1
.
p(u
+
i
) − p(v
+
i
)
/
,
6ω(B
−
, B
−
)=−
l
−
i=1
.
p(u
−
i
) − p(v
−
i
)
/
.
Proof. We prove the case “+” only and omit the superscript “+”. By (5.91)
for a ∈ A
+
we have
ω(B,u
i
,v
j
) ≤ p(u
i
) − p(v
j
)(1≤ i, j ≤ l).
Here we have an equality if i = j and a strict inequality if i<jby the
definitions of
p and P . Then the unique-max property and the expression in
(2) follow from Lemma 5.2.32.
Lemma 5.2.68.
ω
+
[p
+
](B
+
) ≥ ω
+
[p
+
](B
+
1
)(B
+
1
∈B
+
),
ω
−
[−p
−
](B
−
) ≥ ω
−
[−p
−
](B
−
1
)(B
−
1
∈B
−
).
Proof. Again we prove the case “+” only. By Lemma 5.2.7 it suffices to show
ω[
p](B − u + v) ≤ ω[p](B)(u ∈ B,v ∈ V \ B).
Note first that
ω[
p](B − u + v) − ω[p](B)=ω(B − u + v) − ω(B) − p(u)+p(v). (5.92)
330 5. Polynomial Matrix and Valuated Matroid
Here we have
ω(
B − u + v) − ω(B) ≤ 6ω(B, B − u + v) ≤
u
∈B
p(u
) −
v
∈B−u+v
p(v
)
by the upper-bound lemma (Lemma 5.2.29) and (5.91) for a ∈ A
+
,and
ω(
B) − ω(B)=6ω(B,B)=
l
i=1
(p(u
i
) − p(v
i
))
by Lemma 5.2.67 and the unique-max lemma (Lemma 5.2.35). Therefore the
RHS of (5.92) is bounded by
u
∈B
p(u
) −
v
∈B−u+v
p(v
) −
l
i=1
(p(u
i
) − p(v
i
)) − p(u)+p(v)=0.
Thus we have shown (5.84) in Lemma 5.2.65, (5.85) and (5.86) in Lemma
5.2.68, (5.87) and (5.88) in Lemma 5.2.66. This completes the proof of The-
orem 5.2.62.
Notes. The concept of valuated matroids has been obtained by Dress–
Wenzel [54, 57] through a quantitative generalization of the exchange axiom
of matroids. Duality results for a pair of valuated matroids are established by
Murota [224, 230]. This direction is further pursued by Murota [227, 231, 234]
to arrive at the concept of “M-convex functions.” Besides the exchange axiom,
the concept of matroids can also be defined in terms of submodular functions,
and the equivalence between the exchange property and the submodularity is
one of the most fundamental facts in matroid theory, described in §2.3.2. In
harmony with the generalization of matroids to M-convex functions in terms
of the exchange axiom, the concept of submodular functions has been gener-
alized to that of “L-convex functions” by Murota [231]. Then the equivalence
between the exchange property and the submodularity is generalized to the
conjugacy between M-convex functions and L-convex functions. With these
concepts a discrete analogue of convex analysis (Rockafellar [280, 281, 282]),
called “discrete convex analysis,” has been developed by Murota [231]. See
Murota [232, 235, 236] for expositions on “discrete convex analysis” using
M-convex and L-convex functions.
6. Theory and Application of Mixed
Polynomial Matrices
This chapter is devoted to a study of the mathematical properties of mixed
polynomial matrices with particular emphasis on applications to control the-
oretic problems. Mathematically, the analysis of mixed polynomial matrices
relies heavily on the results in Chap. 4 and Chap. 5, in particular, the CCF
of LM-matrices and the properties of valuated matroids.
6.1 Descriptions of Dynamical Systems
Mixed polynomial matrices arise naturally from the description of dynamical
systems. The objective of this section is to collect relevant definitions and
concepts for later reference.
6.1.1 Mixed Polynomial Matrix Descriptions
In §3.1.2 as well as in §1.2.2 we have compared two kinds of descriptions
of linear time-invariant dynamical systems from the viewpoint of structural
analysis using mixed polynomial matrices. The first kind is the standard form:
dx
dt
= Ax + Bu, (6.1)
where x ∈ R
n
and u ∈ R
m
, and the other the descriptor form:
F
dx
dt
= Ax + Bu, (6.2)
where x ∈ R
n
, u ∈ R
m
,andF is usually a square matrix. It has been argued
by way of examples that the coefficient matrix [A −sF | B] of the frequency
domain representation of the descriptor form (6.2), with a suitable choice of
variables, can often be modeled by a mixed polynomial matrix.
Let us recall the definition of a mixed polynomial matrix. A matrix A(s)
of polynomials in s over a field F is called a mixed polynomial matrix with
respect to (K, F ), where K is a subfield of F ,ifA(s) is split into two parts:
A(s)=Q(s)+T (s) (6.3)
in such a way that
K. Murota, Matrices and Matroids for Systems Analysis,
Algorithms and Combinatorics 20, DOI 10.1007/978-3-642-03994-2
6,
c
Springer-Verlag Berlin Heidelberg 2010