多角形 LP テストと領域縮小を用いた非線形回路の全解探索法

修士論文要旨

(2012

年度

)

多角形 ^LP テストと領域縮小を用いた非線形回路の全解探索法

Finding All DC Solutions of Nonlinear Circuits Using the Polygonal LP Test and Narrowing Techniques

電気電子情報通信工学専攻 森 祥太

Shota MORI 1.

ま え が き

非線形方程式のすべての解を求める問題は多くの科学 技術分野で発生する重要な問題の一つである．同時にこ の問題は

,

問題の次元

n

の増加とともに計算時間指数関数 的に増大してしまう非常に難しい問題である

.

本研究室では

,

これまでに線形計画法を用いた強力な解 の非存在判定テストとしてＬＰテストが提案された

.

ＬＰ テストとは

,

非線形方程式を線形計画問題に置き換え

,

そ れに単体法を適用することで解の非存在判定を行う方法 である

.

さらに

,

その改良として線形計画法の双対定理を 利用した双対ＬＰテストが提案された

.

また

,

ＬＰテスト のバリエーションの一つとして平行四辺形を用いたＬＰ テストが提案された

.

この手法は非線形方程式が緩やかな 場合

,

ＬＰテストが強力になり従来より効率的に全解探索 を行える

.

しかし，制約条件が増えてしまい計算効率が落 ちてしまうことも少なくない．本稿では制約条件を増や すことなく，平行四辺形

LP

テストをより効率的に行う手 法を提案する．

2.

基本となるアルゴリズム

2. 1 LPテスト

n

個の非線形抵抗を含む直流回路は一般に次の非線形 方程式であらわせる．

f(x)

=

⁴ P g(x)

+

Qx

+

s

=

0

(1)

こ こ で ，x= (x1

, x

2

, · · · , x

n

)

^T

∈

Rⁿ は

n

次 元 変 数 ベ ク ト ル ，s= (s1

, s

2

, · · · , s

n

)

^T

∈

Rⁿ は 定 数 ベ ク ト ル ，P お よ び Q は

n × n

定 数 行 列 ，g(x)=

[g

1

(x

1

), g

2

(x

2

), · · · , g

n

(x

n

)]

^T は一変数の非線形関数で ある．

y

i

= g

i

(x

i

)

を導入し，

a

i

< = x

i

< = b

i における

g

i

(x

i

)

の

最小値、最大値を

c

i

, d

iとすると

c

i

< = y

i

< = d

iとなる．こ れらの線形等式，線形不等式を制約条件とする次のよう な線形計画問題を考える．

最大化：任意の定数 制約条件：

P y

+

Qx

+

s

=

0

a

i

< = x

i

< = b

i

(2)

c

i

< = y

i

< = d

i

ただし，

i = 1, 2, · · · , n

である．

式

(1)

の領域

X = ([a

1

, b

1

], · · · , [a

i

, bi])

内の解は

y

i

= g

i

(x

i

)

とおいているため，式

(2)

の制約条件を満たす．し たがって，式

(2)

に実行可能領域が存在しなければ，領域

X

に式

(1)

の解は存在しない．式

(2)

に実行可能領域が 存在するか否かは式

(2)

に単体法を適用することにより判 定できる．単体法を適用し対象としている区間に実行可 能領域が存在しない場合，その区間には式

(1)

の解が存在 しないため解析対象から除去できる．このような解の非 存在判定法を

LP

テストと呼ぶ．また，非線形関数を長方 形領域で囲っているため長方形

LP

テストとも呼ばれる．

2. 2 双対LPテスト

双対

LP

テストとは，線形計画法の双対単体法を用いる ことで，上記で述べた

LP

テストと同様の効果を少ない計 算量で実現できる方法である．領域を分割する前の実行 可能タブローを再利用し，領域を分割した後の実行可能 タブローを作る．このタブローにおいて基底変数の値が 全て非負の場合，ピボット演算を一回も行わず，双対

LP

テストは終了となる．もし，すべての値が非負でなくて も数回のピボット演算でほとんどの場合判定を行える．

2. 3 平行四辺形LPテスト

非線形関数を平行四辺形を用いてより厳密に囲み，解の

xi

) (_i

i gx

y=

xi )

(_i

i gx

y=

図1 平行四辺形ＬＰテストのイメージ

非存在判定能力を強力にすることを目的とする

LP

テス トを平行四辺形

LP

テストと呼ぶ．

点

(a

_i

,g

_i

(c

_i

)),(b

_i

,g

_i

())

を通る直線の傾きを

R

_iとする．

傾き

R

iの

g

i

(x

i

)

と接する直線の切片をそれぞれ

β

i

,β

iと する．このとき平行四辺形

LP

テストを行うための線形計 画問題は次のように表すことができる．

最大化：任意の定数 制約条件：

P y

+

Qx

+

s

=

0

(3)

y

i

> = R

i

x

i

+ β

i

(4)

y

i

< = R

i

x

i

+ β

i

(5)

a

i

< = x

i

< = b

i

(6)

ただし，

i = 1, 2, · · · , n

である．

2. 4 制約条件を増やさずに切り替える方法

この節では

,

非線形関数を長方形で囲んだ領域から平行 四辺形で囲んだ領域に変換する際

,

制約条件を同数のまま で変換するために

,

どのような変数変換が必要になるのか を述べる

.

) (i

i gx

y=

ai

bi xi

Ri

ͼẨ

γi

βi

βi

) (_i

i gx

y=

ai

bi xi

xi

yi

γi

図2 従来法による平行四辺形LPテスト

x − y

座標を図

2

のように

x

i

= x

i

− a

i  

(7)

y

i

= y

i

− γ

i

− R

i

x

i

(8)

と取る

.

すると非線形方程式を平行四辺形で囲むのに必 要な制約条件は

x

i

< = b

i

− a

i

(9)

y

i

< = β

i

− β

i

(10)

x

i

> = 0 y

i

> = 0 (11)

このような

x

i

,y

iの取り方をすることで

,

非線形関数の 囲み方を長方形から平行四辺形に切り替える際

,

タブロー のサイズを増やすことなく平行四辺形

LP

テストを行う ことができる

.

2. 5 LP 縮 小

LPnarrowing

とは単体法のフェーズ を用いて解の非

存在判定と領域縮小を同時に行う手法である．

LP

テストと同様の制約条件を持ち，

x

iを最小化する次 のような問題を考える．

最小化：

x

i

制約条件：

P y

+

Qx

+

s

=

0

a

i

< = x

i

< = b

i

i = 1, 2, 3, · · · , n (12) c

i

< = y

i

< = d

i

i = 1, 2, 3, · · · , n

この問題に単体法フェーズ を適用して得られる

x

iの 最小値を

x

^∗_i とする．式

(1)

の解は式

(3)

の実行可能領 域内に含まれる．実行可能領域における

x

iの最小値は

x

^∗_i であるため式

(1)

の解は区間

[a

i

,x

^∗_i

)

内に存在しない．

そのため，解析区間を

[x

^∗_i

,b

i

]

に縮小できる．この操作を

i = 1, 2, 3, · · · , n

へ適用し縮小する．

同様にして，

x

iの最大化問題 最大化：

x

i

制約条件：

P y

+

Qx

+

s

=

0

a

i

< = x

i

< = b

i

i = 1, 2, 3, · · · , n (13) c

i

< = y

i

< = d

i

i = 1, 2, 3, · · · , n

に単体法フェーズ を適用し最適解を用いて区間の上限 値を縮小する．

このような縮小法を

LP

縮小と呼ぶ．

3.

提 案 手 法

3. 1 制約を増やさない平行四辺形LPテストの効率化 平行四辺形

LP

テストを行う式

(3)

〜

(6)

に対し

¯

y

_j

= y

_j

− R

_j

x

_j 

j = 1, 2, · · · , n (14)

のような変数変換することを考える．

式

(3)

に式

(14)

を代入すると

Py¯

+

Qx¯

+

s

=

0

(15)

となる．ここで行列

Q ¯

の各要素は

Q ¯ =







Q

11

+ P

11

R

1

· · · Q

1n

+ P

1n

R

n

.. . . .. .. . Q

n1

+ P

n1

R

1

· · · Q

nn

+ P

nn

R

n







(16)

である．

次に式

(12),(13)

に式

(14)

を代入すると

¯

y

i

> = β

i

(17)

¯

y

i

< = β

i

(18)

となる．

式

(15),(17),(18)

より変数変換後の平行四辺形

LP

テス トを行う線形計画問題は

最大化：任意の定数 制約条件：

Py

¯ + ¯

Qx

+

s

=

0

(19) a

i

< = x

i

< = b

i

i = 1, 2, · · · , n (20) β

i

< = ¯ y

i

< = β

i

i = 1, 2, · · · , n (21)

となり，制約条件を増やすことなく平行四辺形

LP

テスト を行え

,

変数変換を少なくできる．

3. 2 非線形性の判定

ここでは，非線形性を知る指標の一つとして二次導関数 について述べる．

微分の定義は，

dy dx = lim

∆x→0

f(x + ∆x) − f (x)

∆x (22)

である．式

(22)

を

dy

dx = lim

∆x→0

f(x) − f (x − ∆x)

∆x (23)

dy dx = lim

∆x→0

f(x + ∆x) − f (x − ∆x)

2∆x (24)

このように書き換えても同じ意味である．式

(24)

を用い て２階微分の式を考える．

d

²

y dx

²

= d

dx dy dx

= d dx f

⁰

(x)

= lim

∆x→0

f

⁰

(x + ∆x) − f

⁰

(x − ∆x)

2∆x (25)

分子を式

(22)

，

(23)

を用いて書き換えると

∆x→0

lim

f(x+∆x)−f(x)

∆x

−

f(x)−f(x−∆x)

∆x

2∆x (26)

∆x→0

lim 1

∆x

²

µ

f (x + ∆x) − f (x − ∆x)

2 − f (x)

¶

(27)

式

(27)

から，

f

⁰⁰

(x) > 0

のとき，

f (x)

は

f (x + ∆x)

と

f (x − ∆x)

の平均値より小さい．

f

⁰⁰

(x) < 0

のとき，

f (x)

は

f (x + ∆x)

と

f (x − ∆x)

の平均値より大きい．

f

⁰⁰

(x) = 0

のとき，

f (x)

は

f (x + ∆x)

と

f (x − ∆x)

の 平均値と等しい．これより，二次導関数は関数の凸性を知 るための指標であることがわかる．本研究では，このよ うな二次導関数の性質を利用し非線形性の強弱の判定を する．

3. 3 提案アルゴリズム

前節で述べた制約を増やさない平行四辺形囲みを

LP

縮 小に導入する．さらに非線形性の判定を導入し，非線形 性が弱いと判定された場合長方形から平行四辺形へと切 り替える．本研究では非線形性の判定に非線形関数の二 次導関数を用いて，この値が設定した値より小さい場合 非線形性が弱いと判断し，平行四辺形へと切り替える．

4.

数 値 例

アルゴリズムは

C

言語

(

倍精度

)

と

CPLEX

を用いて

Dell Precision T7400(CPU:Intel Xeon 3.4GHz)

上に実 装した．数値例において，従来法とは長方形

LP

縮小であ り，提案法

1

とは，制約を増やさない平行四辺形のみの

LP

縮小であり，提案法

2

とは長方形と制約を増やさない 平行四辺形

LP

縮小を併用した手法のことである．

4. 1 トンネルダイオード回路

n

個のトンネルダイオードを含む非線形回路を表す次の ような

n

変数の非線形方程式

2.5x

³_i

− 10.5x

²_i

+ 11.8x

i

− i +

Xn j=1

x

j

= 0 (28)

i = 1, 2, · · · , n

を考える．初期領域を

([−10, 10], · · · , [−10, 10])

^T として 解析した結果を表

1

〜

2

に示す．

表1 解析時間(s)

n 長方形 提案法1 提案法2

100 1 1 1

200 8 9 9

300 27 25 30

400 73 63 81

500 252 160 182

600 508 304 318

700 592 406 370

800 1498 892 918

900 3360 2154 1976

1000 4482 3122 2746

表2 解 析 領 域

n 長方形 提案法1 提案法2

100 27 21 27

200 31 33 31

300 27 25 29

400 35 27 27

500 31 29 31

600 27 27 27

700 17 17 17

800 27 27 27

900 41 39 41

1000 39 37 39

4. 2 不動点問題 不動点問題

2nx

i

− (

Xn j=1

x

³_j

+ i) = 0 (29)

i = 1, 2, · · · , n

に対して初期領域

([−2.5, 2.5], · · · , [−2.5, 2.5])

^T，として 解析した結果を表

3

〜

4

に示す．

5.

む す び

本論文では，変数変換と非線形性の判定を用いて長方形 と平行四辺形を併用する手法を提案した．本手法を用い ることにより，非線形関数に適した囲みが選択され効率 的に全解探索できることを示した．

表3 解析時間(s)

n 長方形 提案法1 提案法2

100 0.24 0.25 0.24

200 2 2 2

300 7 10 7

400 19 27 20

500 62 96 61

600 139 177 143

700 250 291 251

800 403 495 408

900 592 741 599

1000 831 1023 830

表4 解 析 領 域

n 長方形 提案法1 提案法2

100 9 7 9

200 9 7 9

300 9 7 9

400 9 7 9

500 9 7 9

600 9 7 9

700 9 7 9

800 9 7 9

900 9 7 9

1000 9 7 9

文 献

[1] K.Yamamura,K.Suda,N.Tamura,“LP narrowing: A new strat- egy for finding all solutions of nonliner equations,” Applied Mathamatics and Computation- , vol215, no.1, pp.405–413, Sept.2009.

[2] K.Yamamura,H.Kawata, A.ToKue,“Interval solution of non- liner equations using liner programing,” BIT-Numerical Mathematics-, vol.38, no1,pp.186–199, Sept.2009.

[3] L.V.Kolev,“A new method for global solution of systems of nonlinear equations,” Reliable Computing, vol.4 , no.2 , pp.125–146 ,Apr.1998.

[4] K. Yamamura and T.Fujioka,“Finding all solution of nonlin- ear equations using the dual simplex method,”J.computational and Applied Mathematics,vol.152, no.1-2, pp.578–595,March 2003.

[5] V. Chv´atal,“Liner Programming,” W.H.Freeman Campany, New York, p.158,1983.

[6] K. Suda and K. Yamamura,“LP narrowing: A new strategu for finding all solutions of nonliner equations,”Proc.Int.Symp.Nonliner Theory and its Applications, Vancouver, Canada, pp.246–

249,2007.

[7] K. Suda and K. Yammura and N. Tamura,“LP narrowing: An efficient algorithm for finding all solutions of nonliner equa- tions,” Proc.2007 IEEE Workshop on Nonliner Circuit Net- works, Tokushima, Japan,pp19–22, Dec.2007.

[8] 山村清隆,田中克昌,“双対単体法を用いた弱非線形方程式の全解探 索法,”電気情報通信学会論文誌(A), vol.j88-A, no.7, pp.833-839, Jul. 2005.