修士論文 要旨

構造化ディスクリプターシステムの最小可制御性問題
数理情報学専攻 48-206224
指導教員

2.2

1 はじめに

寺崎 峻
佐藤 一宏 講師

構造化ディスクリプターシステム

ディスクリプターシステムの F, A, B が一般行列とし電力網や神経ネットワークなどのような，大規模ネッて与えられるとき，式 (1) を構造化ディスクリプター

トワークシステムに対する制御理論が近年注目されてシステムという．構造化ディスクリプターシステムにいる．その中でも，状態間の作用を有向グラフで表現対する構造可解性と構造可制御性は，それぞれ式 (2)，する構造化システムに対する研究が広く行われている．

式 (3) が一般ランクの意味で成り立つこととして定義す

特に，最小可制御性問題は最小の入力数で構造化システる．一般行列とそのランクについての詳細は [2] を参照

ムを構造可制御にする問題であり，効率的な解法が提案されたい．

されている [1, 3]．

構造化ディスクリプターシステム (1) 及びその構造本研究では，2 種類の最小可制御性問題を構造化ディ可制御性を効率的に判定するために，二部グラフ及びスクリプターシステムに拡張し，1 つは NP 困難な問題

その DM 分解を用いた解析 [2] が知られている．構造であることを示した．さらに，もう 1 つの問題に入力制化ディスクリプターシステム (1) に対応する二部グラフ

約を導入し，最適解が存在するための条件及び最適解をG = (V + , V − ; E) は以下のように定義される;{V + := X ∪ U, V − := {e1 , . . . , en },E := EA ∪ EF ∪ EB求める効率的なアルゴリズムを構成した．

2 準備
2.1

こ こ で X = {x1 , . . . , xn } は 状 態 頂 点 集 合 ，U =ディスクリプターシステム

本研究では，ディスクリプターシステムと呼ばれる微{u1 , . . . , um } は入力頂点集合，EA := {(ej , xi ) | Aij ̸=0}，EF := {(ej , xi ) | Fij ̸= 0}，EB = {(ej , ui ) | Bij ̸=分代数方程式

F ẋ(t) = Ax(t) + Bu(t)(1)0} であり，EF に属す辺を s-辺と呼ぶ．ei ∈ V − は方程
式頂点であり，ディスクリプターシステム (1) の第 i 行を考える．ただし，F, A ∈ Rn×n , B ∈ Rn×m である．

目の方程式に対応している．二部グラフ G の DM 分解

微分代数方程式に一意な解が存在するとき，式 (1) は可を考え，部分グラフ Gk (k = 0, . . . , b, ∞) を G の DM解であるという．システムの可解性及び可制御性は以成分とする．Gk (k = 1, . . . , b) は整合成分，G0 と G∞

下の命題によって判定可能である．

は不整合成分と呼ぶ．また，ν(G) を G の最大マッチン

命題 1 (可解性 [4]). ディスクリプターシステム (1) がグのサイズとする．さらに，G の重要な部分グラフとし可解であるための必要十分条件はrank(A − sF ) = n(2)て，GA = (X, V − ; EA )，GA−sF = (X, V − ; EA ∪ EF )，G[A|B] = (X, V − ; EA ∪ EB ) を定義する．このとき，構造化ディスクリプターシステム (1) の構造可制御性は，がある s ∈ C に対して成り立つことである．

以下によって特徴づけられる．

定義 2 (可制御性). 許容な初期条件を満たす x∗ ∈ Rn

命題 4 (構造可制御性 [2]). 構造化ディスクリプターシに対して，ある入力 u : R

ステム (1) が構造可制御であるための必要十分条件は，m→ R と時刻 T ≥ 0 が存在∗

して，x(T ) = x となるとき，ディスクリプターシステ

1) ν(GA−sF ) = n

ム (1) は可制御であるという．

2) ν(G[A|B] ) = n
命題 3 (可制御性 [4]). ディスクリプターシステム (1)3) G のすべての整合成分は s-辺を含まないが可制御であるための必要十分条件は，rank [A − zF | B] = n(∀z ∈ C)(3)である．行列 D(s) = [A − sF | B] はモーダル可制御行列と呼ばれる．

3 最小可制御性問題 (MCP)
以降では，入力ゲイン B が未知の構造化ディスクリプターシステム F ẋ(t) = Ax(t) を考え，システム

構造化ディスクリプターシステムの最小可制御性問題 (寺崎 峻)(F, A) は構造可解性を満たすと仮定する．いま，R ={e1 , . . . , en } を方程式の添字集合とし，F を R の部分集合とする．F が要素 ei を持つとき，ディスクリプ
ターシステム (1) の第 ei 行目の方程式には入力できないことを意味する．この F を禁止方程式集合，ei ∈ Fを禁止方程式と呼ぶ．このとき，ディスクリプターシス
テム (F, A) に対する入力制約付き MCP0 及び MCP1
は次のように定式化される:

Algorithm 1 制約付き MCP0 に対するアルゴリズム
1: if 定理 5 の条件 a) が満たされない then2:

3: end if
4: 問題 (4) の最適解を M ∗ とする (存在しない場合，実行不可能)．
5: 入力頂点集合 U := {u1 , . . . , unD } の各入力頂点に各方程式頂点 V − \ ∂ − M ∗ を接続する．ただし nD(制約付き MCP0)minimize B ∈ G n×m

subject to

制約付き MCP0 は実行不可能．

は定理 6 の式 (5) で与えられる．
6: GA−sF の極大整合 s 成分の F に属していない方程mシステム (F, A, B) は構造可制御,式頂点と U を接続する．

B の fi ∈ F 行目は全て 0 ベクトル

(MCP1)

 minimize∥b∥0 subject toシステム (F, A, B = diag(b)) は構造可制御b ∈ Gn存在すると仮定する．このとき，問題 (4) の最適値を

ただし，G n×m は n × m の一般行列全体の集合を表し，∥b∥0 は b の非ゼロ要素数を表す．MCP0 と MCP1m∗ とすると，制約付き MCP0 の最適値 nD との間に以下の関係式が成り立つ．

nD = max{n − m∗ , 1}の違いはその入力ゲイン B の制約の違いに現れている．
具体的には，MCP0 では各入力頂点が複数の状態頂点に接続可能であるのに対して，MCP1 では各入力頂点はただ一つの状態頂点にしか接続することができない．

3.1(5)

問題 (4) は交互道アルゴリズムにより最適解を求めることが可能である．また，Algorithm 1 に示すように，
問題 (4) の最適解及び GA−sF の DM 分解を用いるこ

制約付き MCP0 に対する結果

制約付き MCP0 に最適解が存在するための必要十分条件は以下で与えられる．とで制約付き MCP0 の最適解を構成できる．
定理 7. Algorithm 1 は制約付き MCP0 の最適解を出定理 5. 構造化ディスクリプターシステム (F, A) は可解性の仮定 (2) を満たすとする．このとき，制約付きMCP0 に最適解が存在するための必要十分条件は以下

力し，その時間計算量は O(|V | + |E|

3.2√|V |) である．

MCP1 に対する結果集合被覆問題のインスタンスを MCP1 に帰着させるの条件が同時に成り立つことである．

ことにより，以下の結果を得る．

a). GA−sF の任意の極大整合 s 成分 Gi の頂点集合 Vi定理 8. 構造化ディスクリプターシステム (F, A) は可に対して，ある e ∈ Vi ∩ Vb). 次の最適化問題
 maximize
subject to−が存在し e ̸∈ F ．

解性の仮定 (2) を満たすとする．このとき構造化ディスクリプターシステム (F, A) に対する MCP1 は NP 困

|M |M は GA のマッチング,F ⊆ ∂−M難である．

(4)が実行可能．ただし GA = (X, V − ; EA ) である．
ここで，GA−sF の極大整合 s 成分とは，s-辺を持つ整合成分の中で DM 分解の意味で極大なものである．
問題 (4) の最適解を用いることで，制約付き MCP0の最適値を計算することが可能である．
定理 6. 構造化ディスクリプターシステム (F, A) は可解性の仮定 (2) を満たし，制約付き MCP0 の最適解が

参考文献[1] Yang-Yu Liu, Jean-Jacques Slotine, and Albert-László
Barabási. Controllability of complex networks. nature,Vol. 473, No. 7346, pp. 167–173, 2011.
[2] Kazuo Murota. Matrices and matroids for systems
analysis. Springer Science & Business Media, 2009.
[3] Alex Olshevsky. Minimum input selection for structural controllability. In 2015 IEEE American Control
Conference (ACC), pp. 2218–2223, 2015.
[4] 池田雅夫. Descriptor 形式に基づくシステム理論. 計測と制御, Vol. 24, No. 7, pp. 597–604, 1985.