修士論文要旨(2014年度)
整数計画法を用いた非線形回路の特性解析と変動解析
Characteristic Analysis and Tolerance Analysis of Nonlinear Resistive Circuits Using Integer Programming
電気電子情報通信工学専攻 滝 裕至 Hiroshi Taki
1. ま え が き
集積回路の設計において，直流回路に対する駆動点特性 曲線や伝達特性曲線などの特性曲線を求めることは，回 路の性質を調べるうえで重要となる．また，非線形回路の 設計・解析において，非線形抵抗の素子特性が種々の原因 により変動を起こしたとき，回路全体の特性がどのよう に変動するかを見積もることは，より品質の高い，信頼 性の高い回路を開発する上で重要となる．これらの問題 に対し，単体法並びに双対単体法を用いた解析アルゴリ ズムが提案されているが，これらはインプリメンテーショ ンの際に数理計画法に関する専門的知識と複雑なプログ ラミングを必要とするため，初心者や非専門家にとって は必ずしも実装容易性に優れた方法ではなかった[1], [2]．
本論文では，整数計画法を用いたすべての直流動作点を 求めるアルゴリズムを，前述の特性解析と変動解析に拡 張することにより，実装容易性に優れた区分的線形抵抗 回路のすべての特性曲線を求める方法，並びに集合値写 像方程式(区分的台形方程式)のすべての解集合を近似的 に求める方法を提案する．
2. 0-1変数を用いた区分的線形関数の表現
0-1変数を用いて区分的線形関数を表現する方法には 様々な方法があるが，本論文では古くから提案されてい るδフォームを用いる[3]．
n個の区分的線形抵抗を含む抵抗回路は，一般に次のよ うな形の区分的線形方程式で記述することができる．
f(x)△=P g(x) +Qx−r= 0 (1)
ただし，x= (x1, x2,· · · , xn)T ∈Rnはn次元変数ベク トル，g(x) = [g1(x1), g2(x2),· · · , gn(xn)]T はRnから Rnへの区分的線形関数（ただし各成分は一変数関数），
P，Qはn×n定数行列，rはn次元定数ベクトルであ
る．また，f(x) = [f1(x), f2(x),· · · , fn(x)]T :Rn→Rn とする．式(1)のような形の方程式を混合方程式という．
混合方程式は定式化が困難であるという欠点があったが，
最近，SPICEの過渡解析を用いて混合方程式を簡単に導
出する方法が提案されている[4]．区分的線形関数gi(xi) はすべてK本の線分からなるものとする．変数xiに対 する初期領域の区間を[li, ui]とする．また区分的線形関 数gi(xi)の分点をli =ai0< ai1<· · ·< aiK =uiとし，
各分点での区分的線形関数gi(xi)の値をbij =gi(aij)と する．
式(1)に対し正の補助変数δij(i = 1,2,· · · , n;j = 1,2,· · · , K)，0-1 変 数 µij(i = 1,2,· · · , n;j = 1,2,· · · , K)を導入し，yi =gi(xi)とおく．ここで，次 のような混合整数計画問題を考える．
最大化：(任意の定数) 制約条件：
P y+Qx−r= 0 xi=ai0+
∑K j=1
δij
yi=bi0+
∑K j=1
bij−bij−1
aij−aij−1δij
∆i1µi1<=δi1<= ∆i1 ...
∆ij−1µij−1<=δij−1<= ∆ij−1µij−2
∆ijµij<=δij<= ∆ijµij−1
∆ij+1µij+1<=δij+1<= ∆ij+1µij
...
0<=δiK <= ∆iKµiK−1 i= 1,2,· · ·, n (2)
混合整数計画問題(2)の制約条件は式(1)及びx∈D と等価であるから，式(2)を解くことにより式(1)の解を 求めることができる．
v v
min
max
linear region v
図1 特性曲線の描画
整数計画問題は本質的に難しい(NP困難と呼ばれる) 問題のクラスに属するため，少し前までは実用規模の問 題を解くことは不可能とされていた．しかし近年の最適 化アルゴリズムの飛躍的な進化により，最先端のアルゴ リズムを実装した最適化ソルバーの性能は数年前に比べ て飛躍的に向上している．本研究は，このような整数計 画法の驚異的発展を背景とするものである．
3. IBM ILOG CPLEX
混合整数計画問題を解くためのソフトウェアについて説 明する．IBM ILOG CPLEX [5]（以下CPLEXと略記）
はIBM社が提供する，線形計画問題，混合整数計画問題，
二次計画問題などを解くことのできるアカデミックフリー の最適化ソフトウェアである．
CPLEXにはpopulateという混合整数計画問題用の解 析アルゴリズムが搭載されており，一度の解析で複数解 を求めることができる．また，解プール(solution pool) という機能もあり，この機能を併用することにより簡単 に全解探索を行うことができる．解プールは解析で得ら れた複数解を保存する機能であり，設定を変更すること で混合整数計画問題の制約条件を満たす解をすべて保存 することが可能となる[5]．
4. 整数計画法を用いた非線形回路の特性解析
4. 1 対象とする問題
本論文では1ポート非線形抵抗回路の特性曲線を求め る問題を考える．ただし回路には(n−2)個の非線形抵抗 が含まれるものとする．ポートの枝電圧と枝電流をそれぞ れv,iとすると，回路方程式は次のような形で表される．
f(x)△=P
g1(x1) ...
gn−2(xn−2) i
+Q
x1
... xn−2
v
−r= 0 (3)
そして，目的関数をvとし式(3)を式(2)に代入するこ とで得られる混合整数計画問題をCPLEXを用いて解く ことを考える．
4. 2 特性曲線の探索
CPLEXではpopulateによる解析を行った場合，離散 変数(整数変数)の値の組み合わせ一つにつき解を一つ出 力する．整数変数の組み合わせは各線形領域に一対一対 応する．目的関数をvとし，最大化を行うと各線形領域内 でvが最大の端点が求められる．この混合整数計画問題 を目的関数vの最大化，最小化の２回解くことで解曲線 が存在するすべての線形領域で解曲線の端点(図1参照) が求まるのでそれらを結ぶことで特性曲線を求めること ができる．
1 2 3 4 5 6 7 8 9
5 6 7 8 9 10
i [A]
v [V]
図2 特性曲線の端点(例題回路1,K=10)
1 2 3 4 5 6 7 8 9
5 6 7 8 9 10
i [A]
v [V]
図3 図2の端点を結ぶことで得られた特性曲線
1 2 3 4 5 6 7 8 9
5 6 7 8 9 10
i [A]
v [V]
図4 特性曲線(例題回路1,K=50)
5 K
30 K
+12 V +12 V
10.1 K 10.1 K 0.5 K
0.5 K
4 K 30 K
30 K
4 K
30 K
2 V
4 K
v 4 K
i
図5 例題回路2
5. 数 値 例
例題1 文献[6]の例題2で解かれている回路に対して N = 10とし，分割数はK = 50として本手法を適用し た．得られた結果を図4に示す．K= 50程度にするとか なり滑らかな曲線が得られることがわかる．計算時間は 10秒であった．
例題2文献[6]で例題として解かれている図5のトランジ スタ回路に対して本手法を適用した．分割数はK= 32と し，得られた結果を図6に示す．計算時間は7秒であった．
6. 整数計画法を用いた非線形回路の変動解析
6. 1 対象とする問題
非線形抵抗の素子特性が，「二つの区分的線形関数に挟 まれた非凸多角形」で表される集合値写像で与えられる 場合を考える．ただし，この集合値写像は区分的には縦 軸が平行な台形で表されるものとする．このような集合 値写像を区分的台形写像を呼ぶ．以下，式(1)のg(x)が このような区分的台形写像となる回路(区分的台形回路)
0.0002 0.0003 0.0004 0.0005 0.0006 0.0007 0.0008 0.0009 0.001
-4 -2 0 2 4 6 8 10 12
i [A]
v [V]
図6 特性曲線(例題回路2)
trapezoidal region solution set solution set
xq
xq
x x xpmin max
xp xpmin max
xp
p p
xq
qmin qmax
x x xq
min max
trapezoidal region
図7 解集合(変動領域)の描画
を考える．
ここで，式(2)のyiに関する制約式を次のような式に 置き換えた混合整数計画問題を考える．
yi>=bLi0+
∑K j=1
bLij−bLij−1 aLij−aLij−1δij
yi<=bUi0+
∑K j=1
bUij−bUij−1 aUij−aUij−1δij.
(4)
式(4)は区分的台形写像の上下の区分的線形関数を表す．
6. 2 変 動 解 析
変動領域を描画したい2次元平面を(xp, xq)-平面とす る．先ほど考えた混合整数計画問題をxpを目的関数とし て最大化・最小化で2回解き，次にxqを目的関数として 最大化・最小化で2回解く．このとき前述のCPLEXの 性質により，図7に示すように，解集合(変動領域)が存 在する各台形領域に対して，その解集合を含む最小の長 方形が得られる．したがって区分的台形方程式のすべて の解集合を近似的に求めることができる．
i(xi)
xi
g
図8 温度変動により得られる集合値写像
−7.0465
−7.0463
−7.0461
−7.0459
−7.0457
0.25 0.3 0.35 0.4 0.45 0.5
vbe[V]
vce[V]
図9 変動領域(例題回路3)
7. 数 値 例
例題3文献[2]で数値例1として解かれている回路につい て考える．温度を20±20℃に変動したときのEbers-Moll モデルの指数関数は図8のような集合値写像で与えられ る．これをK= 100の区分的台形写像で近似し，本手法 を適用した時の結果を図9に示す．
例題4文献[2]で数値例2として解かれている回路につい て考える．電圧-電流特性の変動幅を0.6，K= 100とし て区分的台形方程式で記述し，本手法を適用した時の結 果を図10に示す．この図で黒丸の点は変動がないときの 解(9個存在する)を表す．破線がSPICEを用いた感度解 析での結果である．
8. む す び
本論文では，整数計画法を用いた非線形回路の特性曲 線解析及び，変動解析法を提案した．本手法はインプリ メンテーションが容易であり，特性曲線解析ではCPLEX を2回適用するだけで，複数の特性曲線が存在する場合 でもすべての曲線を求めることができる．また変動解析
ではCPLEXを4回適用するだけで，複雑な形状の変動
領域を精密に求めることができる．
0 1 2 3 4
−1 0 1 2 3 4
x1 [V]
x2[V]
図10 変動領域(例題4)
文献(下線は研究業績)
[1] K. Yamamura and S. Tanaka, “Finding all solutions of piecewise-linear resistive circuits using the dual simplex method,” International Journal of Circuit Theory and Appli- cations, vol.30, no.6, pp.567–586, Nov. 2002.
[2] K.Yamamura and Y.Haga, “DC tolerance analysis of nonlin- ear circuits using set-valued functions,” Journal of Circuits, Systems, and Computers, vol.17, no.5, pp.785-796, Oct. 2008.
[3] G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1998.
[4] K. Yamamura and M. Tonokura, “Formulating hybrid equa- tions and state equations for nonlinear circuits using SPICE,”
Int. J. Circuit Theory Appl., vol. 41, issue 1, pp. 101–110, Jan. 2013.
[5] IBM, IBM ILOG CPLEX Optimization Studio;
http://www-03.ibm.com/software/products/en/
ibmilogcpleoptistud/
[6] 山村清隆，フィトラグナワン， 蓬田幸二，“線形計画法を用いた非 線形抵抗回路の特性曲線の探索，”信学論(A), vol.J83-A, no.6, pp.761-770, Jun. 2000.
[7] K. Horiuchi, “Functional analysis of nonlinear system fluctua- tions,” IEICE Trans., vol.E74, no.6, pp.1353–1367, June 1991.
[8] K. Yamamura and N. Tamura, “Finding all solutions of sep- arable systems of piecewise-linear equations using integer programming,” J. Computational and Applied Mathematics, vol.236, issue 11, pp.2844–2852, May 2012.
[9] 高木謙吾，滝裕至，前田礼維，山村清隆， 整数計画法を用いた区 分的線形抵抗回路の完全解析， 2013年電子情報通信学会ソサイエ ティ大会講演論文集，A-2-3, Sept. 2013.
[10] E. Yukawa, H. Taki, S. Kinami, and K. Yamamura, “An algo- rithm for finding all DC solutions of nonlinear circuits using polygonal LP test,” Proc. 2013 IEEE Workshop on Nonlinear Circuit Networks, pp.51–54, Dec. 2013.
[11] 石黒俊，滝裕至，山村清隆，“整数計画法を用いた非線形抵抗回路の 特性解析と変動解析，”第27回 回路とシステム淡路島ワークショッ プ論文集，pp.318-323, Aug. 2014.
[12] K. Yamamura and H. Taki, “Characteristic Analysis and Tol- erance Analysis of Nonlinear Resistive Circuits Using Integer Programming,” Proc. 12th IEEE Asia Pacific Conference on Circuits and Systems, Nov. 2014.【発表者】
[13] 岡本大輝，滝裕至，山村清隆，“整数計画法を用いた非線形回路の混 合方程式及び状態方程式の導出，” 2015年電子情報通信学会総合大 会，A-2-32, Mar. 2015発表予定.
