Comments
Description
Transcript
iNorm＼アイノルム1（ N 個の二乗ノルムに関する新しい評価関数）
Copyright ©NS Solutions Corporation, All rights reserved.
2014/3/3 初版
iNorm ＼アイノルム1（
N 個の二乗ノルムに関する新しい評価関数）
新日鉄住金ソリューションズ株式会社
エンベデッド・ユビキタスシステムセンター
貝塚 洋，川﨑智基
[ オリジナリティと記載範囲 ]
本資料の内容はすべて新日鉄住金ソリューションズ株式会社のオリジナルである． iNorm881 の具体的な
関数形は非公開とする．
[ 目次 ]
1.
記号と最大ノルム類似度 .............................................................................................................................................2
2.
iNorm の構造 .........................................................................................................................................................4
2.1. 一般論 ............................................................................................................................................................................ 4
2.2. iNorm881 ..................................................................................................................................................................... 6
3.
iNorm の効用（ iNorm を利用して効果的に求解できる問題）..................................................................9
3.1. 二乗ノルムに関するミニマックス問題 ..................................................................................................................... 9
3.1.1.
問題の内容...................................................................................................................................................... 9
3.1.2.
iNorm による定式化 ................................................................................................................................... 9
3.1.3.
評価実験結果（ iNorm の効用）.............................................................................................................. 11
3.1.3.1. “ iNorm881 による線形制約凸非線形計画問題”と“補助変数νを利用した凸 2 次制約凸 2 次計画問題”との
比較...................................................................................................................................................................................................11
3.1.3.2. “
f ( z ) = iNorm881 ( z , λ = 1) とした場合”と“ f ( z ) = Q1 (z ) とした場合”との比較............................ 15
3.2. 平均二乗ノルム評価と最大ノルム評価の間に存在する評価関数で最適化する問題 ......................................... 17
3.2.1.
問題の内容.................................................................................................................................................... 17
3.2.2.
iNorm による定式化 ................................................................................................................................. 17
3.2.3.
評価実験結果（ iNorm の効用）.............................................................................................................. 18
3.3. 操作量 X から見た評価点の“制御困難さ”を定量的に評価する問題................................................................. 20
3.3.1.
問題の内容.................................................................................................................................................... 20
3.3.2.
iNorm による定式化 ................................................................................................................................. 20
3.3.3.
評価実験結果（ iNorm の効用）.............................................................................................................. 21
4.
結論............................................................................................................................................................................. 22
5.
付録............................................................................................................................................................................. 24
5.1. 非線形計画問題の求解におけるダンピングファクターの機能 ............................................................................ 24
5.2. 評価実験に使用した問題........................................................................................................................................... 25
1
新日鉄住金ソリューションズ株式会社の登録商標．
1
Copyright ©NS Solutions Corporation, All rights reserved.
1. 記号と最大ノルム類似度
本論説で使用する記号と最大ノルム類似度の定義をまとめておく．
•
R n ・・・n 次元実ベクトル空間
•
R n×m ・・・n 行 m 列の実行列
•
x :=
n
∑x
i =1
•
(x ∈ R ) ・・・ x の二乗ノルム
2
n
i
x ∞ := max xi
1≤i ≤ n
(x ∈ R )・・・ x の最大ノルム
n
• 最大ノルム類似度・・・ z ∈ R に関する下記の性質を有する関数 f ( z )
N
⋅ f ( z )は変数zの置換に対して不変． すなわち，
z
任意の置換 1
z1′
2
⋅ f (r , r , L , r ) = r
⋅ f (r ,0, L ,0 ) = αr 2
z2 L z N
に対して，f (z1 , z 2 ,L , z N ) ≡ f (z1′ , z 2′ , L, z ′N )
z 2′ L z ′N
(0 < α ≤ 1
はrに無関係な定数 )
が z ∈ R に関して凸関数であれば， f ( z ) の等ノルム曲面（一般的には超曲面）は N 次元ユークリッド
N
空間で凸形状となる．そこで，“原点から一番遠い，最大ノルム z
max (z ) = r
2
1≤i ≤ N
i
0
2
∞
の等ノルム曲面（すなわち，
で定まる曲面）
であるN 次元超立方体の頂点”
をP1 とする．
このとき，
点P1 を通る f ( z )
の等ノルム曲面（ f ( z ) = f (r0 , r0 , L , r0 ) = r0 で定まる曲面）と z1 軸との交点を P2 とするとき，
2
最大ノルム類似度 :=
r0
r
= 0 = α ≤1
r0
OP2
α
Q r0 2 = f (r ,0,L ,0) = αr 2
r0
∴ OP2 = r =
α
と定義する．この最大ノルム類似度は，
『 f ( z ) の最大ノルム類似度が 1 に収束すれば，f ( z ) は“一様に”
最大ノルム z
∞
に収束する』と言えるので便利な指標である．
2
Copyright ©NS Solutions Corporation, All rights reserved.
f(z) = f(r0,r0,…,r0) = r02
の等ノルム曲面
zN
r0/α1/2
最大ノルム類似度
= r0/(r0/α1/2)
= α1/2
P1
r0
r
最大ノルム2 = r02
の等ノルム曲面
P2
0
r0
z1
r0/α1/2
図 1.1 最大ノルム類似度
□
[ 凸結合の場合の最大ノルム類似度 ]
⋅ f ( z ), g (z )は変数zの置換に対して不変．
⋅ f (r , r , L , r ) = g (r , r , L , r ) = r 2
⋅ f (r ,0, L ,0 ) = αr 2 ,
g (r ,0, L ,0 ) = βr 2
(0 < α , β ≤ 1
はrに無関係な定数 )
を満足する z ∈ R に関する関数 f ( z ), g ( z ) に対して，
N
凸結合 λf ( z ) + (1 − λ )g ( z )
=
(0 ≤ λ ≤ 1)
の最大ノルム類似度
λα + (1 − λ )β
= λ ( fの最大ノルム類似度 ) + (1 − λ )(gの最大ノルム類似度 )
2
2
となる．□
3
Copyright ©NS Solutions Corporation, All rights reserved.
2. iNorm の構造
2.1. 一般論
iNorm の構造を示す．
[ iNorm の構造 ]
iNorm p ( z , λ ) :=
∑ {w (z, λ )z }
N
i =1
2
i
i
⇐
{z }の関数重み付き平均
2
i
where
z1
z
z := 2 ∈ R N
M
zN
• 0 ≤ λ ≤ 1,
• wi ( z , λ ) ≥ 0,
{ }
N
∑ w (z, λ ) = 1
i =1
⇐ iNorm p ( z , λ )は zi の凸結合となる
2
i
• wi (αz , λ ) = wi ( z , λ ) (∀α > 0)
⇐ 重み関数はzに関してスケール不変
第j要素
第i要素
• wi z1 , L , zi −1 , z j , zi +1 , L , z j −1 , zi , z j +1 , L , z N = w j (z1 , z2 , L , z N )
⇐ 重み関数の対称性
• iNorm p ( z , λ )
1 N 2
= N ∑ zi
i =1
≅ max zi 2
1≤i ≤ N
( )
(λ = 0)
p
最大ノルム類似度 ≥
1000
(λ = 1)
{z }の平均値～{z }の最大値の間を
2
⇐
(i ≠ j )
2
i
i
λを調整することで任意に補間できる
• iNorm p ( z , λ ) はzの凸関数(∀λ ) (解析的な証明は未完 )
⇐ 最適化計算が容易
このように定義すれば，自動的に下記が成立する．
⋅ iNorm p ( z , λ )は変数zの置換に対して不変． すなわち，
z z L zN
に対して，iNorm p ( z , λ )( z1 , z 2 ,L , z N ) ≡ iNorm p (z , λ )(z1′ , z ′2 , L, z ′N )
任意の置換 1 2
z1′ z ′2 L z ′N
⋅ iNorm p (r , r , L , r , λ ) = r 2
⋅ iNorm p (r ,0,L ,0, λ ) = αr 2
(α := w1 (1,0,L,0, λ ))
⋅ iNorm p ( z , λ )の最大ノルム類似度 = iNorm p (1,0, L ,0, λ )
□
上記のような iNorm p ( z, λ ) とはどんな関数形をしているのであろうか？議論を簡潔にするために，
4
Copyright ©NS Solutions Corporation, All rights reserved.
λ = 1 の場合を考える．関数形をイメージアップするために，z に関する関数
N
(
Q1 ( z ) := ∑ wi(Q1 ) ( z ) ⋅ zi
i =1
2
)
2
N
zi 2
= ∑ N
× zi =
2
i =1
∑ z j
j =1
N
4
∑z
i
∑z
j
i =1
N
j =1
2
where
(Q1 )
wi
(z ) :=
zi
2
N
∑z
j =1
を考えてみよう． Q1 ( z ) の重み wi
2
j
(Q1 )
(Q1 )
wi
(z ) =
zi
2
N
∑z
j =1
2
(z ) は
大きくなる
=
小さくなる
j
(ziが相対的に大きい場合 )
(ziが相対的に小さい場合 )
のように作用するので iNorm p ( z , λ = 1) が必要とする“平準化機構（すなわち最大ノルムに近いこと）
”を
備えている．また，重み関数に必要な要件
• wi ( z , λ ) ≥ 0,
N
∑ w (z, λ ) = 1
i =1
i
• wi (αz , λ ) = wi (z , λ ) (∀α > 0)
もすべて満たしている． しかし， Q1 ( z ) は z に関する凸関数ではない．図 2.1 に Q1 ( z ) （N = 2）の等ノル
ム曲面を示しておく．
図 2.1
Q1 ( z ) （N = 2）の等ノルム曲面
“ Q1 ( z ) は z に関する凸関数ではない”という事実の悪影響は
5
Copyright ©NS Solutions Corporation, All rights reserved.
『 Q1 ( z ) を利用して定式化されたミニマックス問題
z1 S1 x + b1
M
Q
M =
1
min
x
z N S N x + bN
subject to
l1 x u1
l ≤ Ax ≤ u
2 2
(線形制約)
は，評価関数が非凸関数となるので局所最適解が多数存在する最適化問題となる．その結果，最適化
計算が収束せず，最適化計算を強制的に中断して求めた暫定解も Q1 ( z ) の代わりに凸関数である
iNorm881 (z ,1) を利用した場合の最適解より平準化能力が低かった．後述の図 3.3 に実験結果を示す』
という形で顕在化する．したがって，iNorm p であるための要件の 1 つである『 iNorm p は z に関して凸関
数である』という性質は重要である．
iNorm p を具体的に構成することは難しい．いくつかのコメントをしておく．
(1) iNorm p は一つではなく無数の種類が存在する．しかしその多くは，N が無限大になったときに最大ノ
ルム類似度が 0 に単調収束する（この場合には p = 0 となる）
．すなわち N が大きい場合には平準化能
力が消滅し， iNorm p の意味を失ってしまう．p を正とできる iNorm p の構成は一段と困難な問題であ
る．□
(2) 今回構成に成功した iNorm881 ( z , λ ) は，いくつかの数値的な検証と部分的な解析的状況に関して凸性を
検証したのみで，凸性の解析的証明は今後の課題として残されている．しかしその証明は難しい．最大
ノルム類似度を下げれば証明できる場合もあるが，最大ノルム類似度を下げることは実用上意味がない．
□
2.2. iNorm881
今回構成に成功した iNorm p は
iNorm881 ( z , λ ) :=
∑ {w( ) (z, λ )z } (0 ≤ λ ≤ 1)
N
2
881
i =1
i
i
である． iNorm881 ( z , λ ) の最大ノルム類似度は
(1 − λ )1 4
{
}
1
14 1 2
+ 1 − (1 − λ )
+ 7 ≥
N
9 N
{1 − (1 − λ ) }⋅ 79 > 0.881917
14
1 − (1 − λ )
14
である．iNorm881 ( z , λ ) のすばらしい特徴は， N → ∞ になっても最大ノルム類似度が 0 に単調収束せず，
6
Copyright ©NS Solutions Corporation, All rights reserved.
{1 − (1 − λ ) }⋅ 79 > 0.881917
14
1 − (1 − λ ) 以上に留まることである．λに対する最大ノルム類似度の下
14
限値を表 2-1 にまとめておく．
表 2-1 λに対する最大ノルム類似度の下限値
{1 − (1 − λ ) }⋅ 79
λ
14
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
0.0000
0.1422
0.2054
0.2576
0.3054
0.3518
0.3990
0.4496
0.5076
0.5834
0.8819
特に iNorm881 ( z , λ = 1) の最大ノルム類似度は
1 2
7
+ 7 ≥
= 0.881917 L
9 N
9
である． iNorm881 ( z , λ = 1) の最大ノルム類似度と等ノルム曲面(N = 2, 3 の場合)を示しておく．
表 2-2 平均二乗ノルム
N
2
4
8
16
32
64
100
128
256
512
1024
2048
4096
8192
↓
∞
1
N
N
∑z
i =1
2
i
と iNorm881 ( z , λ = 1) の最大ノルム類似度
平均二乗ノルム
0.7071
0.5000
0.3536
0.2500
0.1768
0.1250
0.1000
0.0884
0.0625
0.0442
0.0313
0.0221
0.0156
0.0110
↓
0
7
iNorm881 ( z , λ = 1)
0.9669
0.9428
0.9254
0.9129
0.9039
0.8975
0.8944
0.8930
0.8898
0.8875
0.8858
0.8847
0.8839
0.8833
↓
0.8819
Copyright ©NS Solutions Corporation, All rights reserved.
図 2-2
図 2-2
iNorm881 ( z , λ = 1) （N = 2）の等ノルム曲面（最大ノルム類似度 = 0.9669）
( max )
(z ) （N = 3）の等ノルム曲面（最大ノルム類似度 = 0.9519）
iNorm881 ( z , λ = 1) = iNorm881
8
Copyright ©NS Solutions Corporation, All rights reserved.
3. iNorm の効用（ iNorm を利用して効果的に求解できる問題）
3.1. 二乗ノルムに関するミニマックス問題
3.1.1. 問題の内容
[ 二乗ノルムに関するミニマックス問題 ]
min max ( S x + b
x
1≤ i ≤ N
i
i
2
)+ ρ x
2
subject to
l1 x u1
l ≤ Ax ≤ u
2 2
where
決定すべき変数 x ∈ R m
所与のデータ Si ∈ R n× m , bi ∈ R n
所与の上下限値 l1 , u1 ∈ R m , l2 , u2 ∈ R n L
所与の線形制約行列 A ∈ R n L × m
調整パラメータ ρ ≥ 0
□
ここで調整パラメータ ρ は，ダンピングファクターとも呼ばれ，非線形計画問題を線形化して求解する場
合に重宝するパラメータである（概要は付録 5.1 に記載する）
．
3.1.2. iNorm による定式化
iNorm p は
( )
iNorm p ( z , λ = 1) ≅ max zi
1≤i ≤ N
2
p
最大ノルム類似度 ≥
1000
なる性質を有するので，下記の定式化（ iNorm881 を利用）によって“二乗ノルムに関するミニマックス問
題”に対する明確な意味をもつ近似最適解を求めることができる．
[ iNorm881 による線形制約凸非線形計画問題 ]
z1 S1 x + b1
iNorm
M
881 M =
min
x
z N S N x + bN
subject to
l1 x u1
l ≤ Ax ≤ u
2 2
2
,
λ
1
ρ
x
=
+
(線形制約)
□
一方で，
“二乗ノルムに関するミニマックス問題”は補助変数を導入することで下記のような凸 2 次制約
9
Copyright ©NS Solutions Corporation, All rights reserved.
凸 2 次計画問題になる．この問題を解けばミニマックス問題に対する厳密解が求まる．
[ 補助変数νを利用した凸 2 次制約凸 2 次計画問題 ]
min (ν + ρ x
2
x
)
subject to
l1 x u1
l ≤ Ax ≤ u
2 2
Si x + bi
2
≤ν
(線形制約)
(凸2次制約)
(i = 1,2,L, N )
□
10
Copyright ©NS Solutions Corporation, All rights reserved.
3.1.3. 評価実験結果（ iNorm の効用）
3.1.3.1. “ iNorm881 による線形制約凸非線形計画問題”と“補助変数νを利用した凸 2 次制約凸 2 次計画
問題”との比較
付録 5.2 に記載した最適化問題 A（決定変数数 m = 512 個，制約数 = 50×512 = 25,600 制約，評価
点数 N = 512 評価点 ）
に対して，
“ iNorm881 による線形制約凸非線形計画問題
（ f ( z ) = iNorm881 ( z , λ = 1)
とした場合）
”と“補助変数νを利用した凸 2 次制約凸 2 次計画問題”との求解性能を比較した．
“ iNorm881 による線形制約凸非線形計画問題”の場合に，数理計画法パッケージ Numerical Optimizer2
の準ニュートン法（2 階微係数を準ニュートン法によって求める内点法）を利用して，最適化問題 A を，
（ケースその１） 制約条件がない場合
（ケースその２） 制約条件がある場合
について解いた．
“補助変数νを利用した凸 2 次制約凸 2 次計画問題”の求解には，数理計画法パッケージ
Numerical Optimizer に準備されている SolveQP（2 階微係数を準ニュートン法によって求める内点法）を
利用した．
表 3.1 計算時間などの計数値
（制約条件がない場合）
収束判定定数3
求解状態
評価関数値
内点法の反復回数
処理時間(sec)
（制約条件がある場合）
収束判定定数
求解状態
評価関数値
内点法の反復回数
処理時間(sec)
iNorm881 ( z , λ = 1)
1E－6
OPTIMAL
2.8679
47
525
iNorm881 ( z , λ = 1)
1E－6
OPTIMAL
2.9602
68
793
補助変数νを利用した凸 2 次制約凸 2 次計画問題
1E－6
OPTIMAL
3.3109
44
3249
1E－4
1E－2
実験せず
補助変数νを利用した凸 2 次制約凸 2 次計画問題
1E－6
OPTIMAL
3.3656
410
26624
1E－4
OPTIMAL
3.3659
296
19154
1E－2
NON_ OPTIMAL
3.9167
119
8014
iNorm881 ( z , λ = 1) を利用して得られるミニマックス問題の解は近似解である．しかし，図 3.4 に示した
精度を有する近似解（制約条件ありの場合，λ:1.0 のグラフ）が，
“補助変数νを利用した凸 2 次制約凸 2
次計画問題”の 1/30 程度の時間（ iNorm881 ( z , λ = 1) では約 13 分間，
“補助変数νを利用した凸 2 次制約凸
2 次計画問題”では約 7.4 時間4）で求めることができる．これは“ iNorm881 による線形制約凸非線形計画
問題を利用したミニマックス問題の解法”の大きな特徴・利点である．
株式会社 NTT データ数理システム社製
数理計画法パッケージ Numerical Optimizer のパラメータファイル nuopt.prm の中で指定した crit:eps
の値．
4 “補助変数νを利用した凸 2 次制約凸 2 次計画問題”
の求解時間が長くなる理由は，線形制約と同時に 512
個の凸 2 次制約式が存在するためだと思われる．
2
3
11
Copyright ©NS Solutions Corporation, All rights reserved.
しかし，
“補助変数νを利用した凸 2 次制約凸 2 次計画問題”において求解時間が非常に長い理由は，厳
密解を求めているからだとも考えることができる．そこで，
“補助変数νを利用した凸 2 次制約凸 2 次計画
問題”
において，
収束判定定数を大きくして内点法の反復を途中で切り上げることで近似解を求めてみよう．
収束判定を 1E－4 に緩めても 1E－6 の場合と見分けがつかない最適解が得られる．このことは，表 3.1 に
示した評価関数値（＝最悪値）が 1E－4 の場合と 1E－6 の場合とで一致していることからわかる（最適解
の平準化能力を示す図は省略）
．しかし，収束判定を 1E－2 まで大きくしてしまうと，求まった解は最適解
とは判定されず，実際にその精度は図 3.1 に示すように iNorm881 ( z , λ = 1) での最適解（λ:1.0 のグラフ）
より悪い．しかも求解時間は iNorm881 ( z , λ = 1) を利用した場合より 10 倍必要であった．
したがって，
“補助変数νを利用した凸 2 次制約凸 2 次計画問題の収束判定定数を大きくして近似解を求
める手法“は下記の欠陥をもつ．
(1) 収束判定定数をどの程度大きくするかの指針がない．収束判定定数を大きくし過ぎると最適解が見つか
らなくなり，暫定解の平準化能力も低い．
(2) 凸 2 次制約式の数 N（= 評価点数）が多くなると“ iNorm881 による線形制約凸非線形計画問題”の場
合より求解時間が大幅に遅くなる．N = 512 の場合には，20 倍程度遅くなる例がある．
4.5000E+00
4.0000E+00
3.5000E+00
λ：1.0
minν
minν(1E-2)
3.0000E+00
2.5000E+00
2.0000E+00
data151
data181
data211
data241
data271
data301
data331
data361
data391
data421
data451
data481
data511
data1（大）
data31
data61
data91
data121
1.5000E+00
図 3.1 最適解の平準化能力
2
2
• 縦軸は評価点ごとの Si xopt + bi の値 ，横軸は評価点を Si xopt + bi 値の大きい順に並べた．
• ・λ: 1.0 ・・・
“ iNorm881 による線形制約凸非線形計画問題”による最適解．収束判定定数は 1E－6．
・minν・・・
“通常の補助変数νを利用した凸 2 次制約凸 2 次計画問題”で求解したミニマックス問題
の厳密解．収束判定定数は 1E－6．
・minν(1E－2)・・・
“通常の補助変数νを利用した凸 2 次制約凸 2 次計画問題”で求解したミニマック
ス問題の近似解（NON_ OPTIMAL）
．収束判定定数は 1E－2．
12
Copyright ©NS Solutions Corporation, All rights reserved.
別のデータによる比較実験結果も含めて，実験結果をまとめておく．表 3.2 からわかるように，
“ iNorm881 ( z , λ = 1) による線形制約凸非線形計画問題”を利用すれば，
“補助変数νを利用した凸 2 次制約
凸 2 次計画問題”よりも，5 倍～33 倍高速にミニマックス問題の近似最適解を求めることができている．
表 3.2 計算時間などの計数値
• 下記すべての計算において，収束判定定数 = 1E－6 とした．
• 付録 5.2 に記載した最適化問題 A（決定変数数 m = 512 個，制約数 = 50×512 = 25,600 制約，評価点
数 N = 512 評価点 ）を，データを変更して求解した．
データ
#1
（表 3.1
と同一）
#2
制約条件
評価項目
求解状態
評価関数値
なし
内点法の反復回数
処理時間(sec)
求解状態
評価関数値
あり
内点法の反復回数
処理時間(sec)
求解状態
評価関数値
なし
内点法の反復回数
処理時間(sec)
求解状態
評価関数値
あり
（その 1） 内点法の反復回数
処理時間(sec)
求解状態
評価関数値
あり
（その 2） 内点法の反復回数
処理時間(sec)
iNorm881 ( z , λ = 1)
補助変数νを利用
した凸2次制約凸2
次計画問題
OPTIMAL
2.8679
47
525
OPTIMAL
2.9602
68
793
OPTIMAL
194.7
45
508
OPTIMAL
238.3
41
535
OPTIMAL
194.7
61
729
OPTIMAL
3.3109
44
3249
OPTIMAL
3.3656
410
26624
OPTIMAL
213.7
174
11114
OPTIMAL
257.8
53
3872
OPTIMAL
213.7
49
3616
13
処理時間比率
補助変数法
iNorm881
6.2
33.6
21.9
7.2
5.0
Copyright ©NS Solutions Corporation, All rights reserved.
データ#2 に関する最適解の平準化能力を図示する．
4.0000E+02
4.0000E+02
3.5000E+02
3.5000E+02
3.0000E+02
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
2.5000E+02
2.0000E+02
1.5000E+02
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
3.0000E+02
2.5000E+02
2.0000E+02
1.0000E+02
1.5000E+02
5.0000E+01
0.0000E+00
）
大
（
1
at
ad
9
2
taa
d
7
5
taa
d
5
8
taa
d
3
1
1
at
ad
1
4
1
at
ad
9
6
1
at
ad
7
9
1
at
ad
5
2
2
at
ad
3
5
2
at
ad
1
8
2
at
ad
9
0
3
at
ad
7
3
3
at
ad
5
6
3
at
ad
3
9
3
at
ad
1
2
4
at
ad
9
4
4
at
ad
7
7
4
at
ad
1.0000E+02
5
0
5
at
ad
）
大
（
1
at
ad
4
taa
d
7
taa
d
0
1
taa
d
3
1
taa
d
6
1
taa
d
9
1
taa
d
2
2
taa
d
5
2
taa
d
8
2
taa
d
1
3
taa
d
4
3
taa
d
7
3
taa
d
0
4
taa
d
3
4
taa
d
6
4
taa
d
9
4
taa
d
(a) データ#2 の制約条件なしの場合
3.5000E+02
3.1000E+02
3.0000E+02
3.0000E+02
2.5000E+02
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
2.0000E+02
1.5000E+02
1.0000E+02
5.0000E+01
0.0000E+00
2.9000E+02
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
2.8000E+02
2.7000E+02
2.6000E+02
2.5000E+02
）
大
（
1
at
ad
9
2
taa
d
7
5
taa
d
5
8
taa
d
3
1
1
at
ad
1
4
1
at
ad
9
6
1
at
ad
7
9
1
at
ad
5
2
2
at
ad
3
5
2
at
ad
1
8
2
at
ad
9
0
3
at
ad
5
6
3
at
ad
7
3
3
at
ad
3
9
3
at
ad
1
2
4
at
ad
9
4
4
at
ad
7
7
4
at
ad
2.4000E+02
5
0
5
at
ad
）
大
（
1
at
ad
4
at
ad
7
at
ad
0
1
taa
d
3
1
taa
d
6
1
taa
d
9
1
taa
d
2
2
taa
d
5
2
taa
d
8
2
taa
d
1
3
taa
d
4
3
taa
d
7
3
taa
d
0
4
taa
d
3
4
taa
d
6
4
taa
d
9
4
taa
d
(b) データ#2 の制約条件あり（その 1）の場合
3.0000E+02
3.5000E+02
2.8000E+02
3.0000E+02
2.6000E+02
2.5000E+02
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
2.0000E+02
1.5000E+02
1.0000E+02
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
2.2000E+02
2.0000E+02
1.8000E+02
1.6000E+02
1.4000E+02
5.0000E+01
0.0000E+00
2.4000E+02
1.2000E+02
）
大
（
1a
ta
d
9
2a
atd
7
5a
atd
5
8a
atd
3
1
1a
ta
d
1
4
1a
ta
d
9
6
1a
ta
d
7
9
1a
ta
d
5
2
2a
ta
d
3
5
2a
ta
d
1
8
2a
ta
d
9
0
3a
ta
d
7
3
3a
ta
d
5
6
3a
ta
d
3
9
3a
ta
d
1
2
4a
ta
d
9
4
4a
ta
d
7
7
4
taa
d
1.0000E+02
5
0
5
taa
d
） a4
大 at
（ d
1
at
ad
a7
atd
0
1
at
ad
3
1
at
ad
6
1
at
ad
9
1
at
ad
2
2
at
ad
5
2
at
ad
8
2
at
ad
1
3
at
ad
4
3
at
ad
7
3
at
ad
0
4
at
ad
3
4
at
ad
6
4
at
ad
9
4
at
ad
(c) データ#2 の制約条件あり（その 2）の場合
図 3.2 最適解の平準化能力
• 縦軸は評価点ごとの Si xopt + bi
2
の値
2
• 左図の横軸は512 評価点
（ Si xopt + bi の値の大きい評価点順）
，
右図は左図の上位50 評価点のみを表示．
• minν・・・
“通常の補助変数νを利用した凸 2 次制約凸 2 次計画問題”で求解したミニマックス問題の
厳密解．
14
Copyright ©NS Solutions Corporation, All rights reserved.
3.1.3.2. “ f ( z ) = iNorm881 ( z , λ = 1) とした場合”と“ f ( z ) = Q1 ( z ) とした場合”との比較
iNorm881 ( z , λ ) が z に関して凸関数である必要性を示すために，2.1 で提示した z に関して凸関数ではな
い関数
N
Q1 (z ) :==
4
∑z
i
∑z
j
i =1
N
j =1
2
を用いて定式化されたミニマックス問題（付録 5.2 に記載した問題で f ( z ) = Q1 ( z ) とした場合（制約条件な
し）
）
z1 S1 x + b1
Q
M
M =
1
min
x
z N S N x + bN
を，数理計画法パッケージ Numerical Optimizer の準ニュートン法（2 階微係数を準ニュートン法によって
求める内点法）を利用して解いた．結果を図 3.3 に示す．
15
Copyright ©NS Solutions Corporation, All rights reserved.
5.0000E+00
4.5000E+00
4.0000E+00
3.5000E+00
3.0000E+00
非凸関数Q1
iNorm881
2.5000E+00
2.0000E+00
1.5000E+00
1.0000E+00
5.0000E-01
61
57
53
49
45
41
37
33
29
25
21
17
9
13
5
1
0.0000E+00
(a) f ( z ) = iNorm881 ( z ,1) の場合に，最適解が求解される時点までを表示．
5.0000E+00
4.5000E+00
4.0000E+00
3.5000E+00
3.0000E+00
非凸関数Q1
iNorm881
2.5000E+00
2.0000E+00
1.5000E+00
1.0000E+00
5.0000E-01
401
326
351
376
251
276
301
176
201
226
101
126
151
1
26
51
76
0.0000E+00
(b) f ( z ) = Q1 ( z ) の場合に，
『最適解が求解できない』と判定されるまでを表示．
図 3.3 最適化計算中の
• 縦軸は
{ Sx
i opt
+ bi
2
{ Sx
i opt
+ bi
2
}の分散変化（制約条件なしの場合）
}の分散，横軸は解 x の変化回数（内点法の反復回数とほぼ同義））
• iNorm881 ・・・
“ iNorm881 による線形制約凸非線形計画問題”による最適解．収束判定定数は 1E－6．
図 3.1 の“λ:1.0”のグラフと同一の最適解．
図 3.3 から，
『 f ( z ) = Q1 ( z ) の場合には，最適化計算が収束せず，最適化計算を強制的に中断して求めた
暫定解の平準化能力も f ( z ) = iNorm816 ( z ,1) の場合の最適解より低い』ことがわかる．
16
Copyright ©NS Solutions Corporation, All rights reserved.
3.2. 平均二乗ノルム評価と最大ノルム評価の間に存在する評価関数で最適化する問題
3.2.1. 問題の内容
[ N 個の二乗ノルムを最適化する問題 ]
i 番目の誤差を
Si x + bi
2
(i = 1,2,L, N )
where
決定すべき操作変数 x ∈ R m
Si ∈ R n× m
所与のデータ bi ∈ R n ,
と規定して，操作変数 x を使って，N 個の誤差を何らかの意味で最適化せよ．□
上記問題に対して，下記の 2 種類の評価関数が採用されることが多い．
平均二乗ノルム L
(
1
N
N
∑ S x+b
i
i =1
最大ノルム L max Si x + bi
1≤i ≤ N
2
i
2
)
これらの評価関数の最適化における利害得失を簡潔にまとめると，下表のようになる．
全体的な最小化
○
×
平均二乗ノルム
最大ノルム
ピーク値の抑制（平準化）
×
○
どちらを選択するかは問題によって変化する．しかし，問題に最適な評価関数（ここでは“ノルム”と呼ぶ）
は両者のノルムの間に存在する．
3.2.2. iNorm による定式化
iNorm p は
i =1
p
最大ノルム類似度 ≥
1000
iNorm p (z , λ = 0) =
1
N
N
∑z
2
i
( )
{z }の平均値～{z }の最大値の間を
⇐
iNorm p ( z , λ = 1) ≅ max zi
2
1≤i ≤ N
2
2
i
i
λを調整することで任意に補間できる
なる性質を有するので，下記の定式化（ iNorm881 を利用）にて調整パラメータλを調整することで最適な
評価関数を決定して，
“N 個の二乗ノルムを最適化する問題”を効率的に解くことができる．
17
Copyright ©NS Solutions Corporation, All rights reserved.
[ iNorm881 による線形制約凸非線形計画問題 ]
z1 S1 x + b1
iNorm881 M =
M
min
x
z N S N x + bN
2
,
+
x
λ
ρ
subject to
l1 x u1
l ≤ Ax ≤ u
2 2
0 ≤ λ ≤1
ρ ≥0
(線形制約)
(調整パラメータ)
(ダンピングファクター)
□
3.2.3. 評価実験結果（ iNorm の効用）
付録 5.2 に記載した最適化問題 A（決定変数数 m = 512 個，制約数 = 50×512 = 25,600 制約，評価点
数 N = 512 評価点 ）に対して，
“ iNorm881 による線形制約凸非線形計画問題（ f ( z ) = iNorm881 ( z , λ ) とし
た場合）
”のλを利用した評価関数変更の結果を示す． 制約条件がない場合もある場合も安定的に最適解を
求解できた．求解状況を表 3.3 に示す．
表 3.3 計算時間などの計数値
（制約条件がない場合）
λ
評価関数値
内点法の反復回数
処理時間(sec)
0
0.1025
19
277
0.25
0.7898
22
299
0.5
1.4745
23
306
0.75
2.1570
31
364
1
2.8679
47
525
（制約条件がある場合）
λ
評価関数値
内点法の反復回数
処理時間(sec)
0
1.3777
61
725
0.25
1.9022
62
737
0.5
2.2609
64
755
0.75
2.5793
67
784
1
2.9602
68
793
また，最適解の平準化能力を示すグラフを図 3.4 に示す．制約条件がない場合も同様の良好な結果が得ら
れているが，図 3.4 では制約条件ありの場合の結果だけを掲載した．
18
Copyright ©NS Solutions Corporation, All rights reserved.
1.8000E+01
1.6000E+01
1.4000E+01
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
1.2000E+01
1.0000E+01
8.0000E+00
6.0000E+00
4.0000E+00
2.0000E+00
data337
data365
data393
data421
data449
data477
data505
data57
data85
data113
data141
data169
data197
data225
data253
data281
data309
data1（大）
data29
0.0000E+00
2
（制約条件ありの場合）
(a) 横軸は 512 評価点（ Si xopt + bi の値の大きい評価点順）
1.6000E+01
1.4000E+01
1.2000E+01
λ：0.0
λ：0.25
λ：0.5
λ：0.75
λ：1.0
minν
1.0000E+01
8.0000E+00
6.0000E+00
4.0000E+00
2.0000E+00
data49
data46
data43
data40
data37
data34
data31
data28
data25
data22
data19
data16
data13
data10
data7
data4
data1（大）
0.0000E+00
(b) 上記(a)の上位 50 評価点のみを表示（制約条件ありの場合）
図 3.4 最適解の平準化能力
• 縦軸は評価点ごとの Si xopt + bi
2
の値（(a),(b)共通）
• minν・・・
“通常の補助変数νを利用した凸 2 次制約凸 2 次計画問題”で求解したミニマックス問題の
厳密解（(a),(b)共通）
．図 3.1 の“minν”のグラフと同一の最適解．
19
Copyright ©NS Solutions Corporation, All rights reserved.
3.3. 操作量 x から見た評価点の“制御困難さ”を定量的に評価する問題
3.3.1. 問題の内容
[ 評価点の制御困難さの定量化問題 ]
(
)
(i = 1,2,L, N )
di := xに対する Si x + bi の制御困難さ
2
l1 x u1
l ≤ Ax ≤ u
2 2
subject to
(線形制約)
を定量的に決定せよ．□
3.3.2. iNorm による定式化
“評価点の制御困難さの定量化問題”を解くには，制御困難さ d i を適切に定義することが必要である．こ
こでも iNorm881 ( z , λ ) :=
∑ {w( ) (z, λ )z } は役に立つ．すなわち，3.1.2 で述べたiNorm (z, λ = 1)
N
2
881
i =1
i
i
881
を利用したミニマックス問題を解けば，最適解 xopt と同時に
z1 S1 xopt + b1
(881)
(881)
M
最適解における重み wi _ opt := wi M =
z N
S N xopt + bN
{
(881)
(881)
(881)
,
λ
=
1
(i = 1,2, L, N )
}
が求まる． w1 _ opt , w2 _ opt , L , wN _ opt は 1 の分解，すなわち，
N
∑ w(
i =1
881)
i _ opt
= 1,
)
wi(881
_ opt ≥ 0
(i = 1,2, L , N )
であるので，
)
d i = wi(881
_ opt
(i = 1,2,L, N )
(881)
と考えることは自然である．なぜならば，
“ wi _ opt が相対的に大きい”ということは，最適解に至る過程で
(881)
2
“誤差 Si xopt + bi が小さくなり切らないので wi _ opt を増大させた”と解釈することができるからである．
よって， iNorm881 を利用した“二乗ノルムに関するミニマックス問題”によって“評価点の制御困難さ
の定量化問題”を解くことができる．
[ iNorm881 による線形制約凸非線形計画問題 ]
z1 S1 x + b1
M
iNorm
M =
881
min
x
z N S N x + bN
subject to
2
,
λ
=
1
+
ρ
x
l1 x u1
(線形制約)
l ≤ Ax ≤ u
2 2
20
Copyright ©NS Solutions Corporation, All rights reserved.
の最適解 xopt を求め，
“ xに対する Si x + bi の制御困難さ d i ”を
2
(881)
z1 S1 xopt + b1
M =
M
z N S N xopt + bN
(881)
di = wi _ opt := wi
,
λ
=
1
(i = 1,2, L, N )
によって決定する．□
3.3.3. 評価実験結果（ iNorm の効用）
付録 5.2 に記載した最適化問題 A（決定変数数 m = 512 個，制約数 = 50×512 = 25,600 制約，評価点
数 N = 512 評価点 ）に対して，
“ iNorm881 による線形制約凸非線形計画問題（ f ( z ) = iNorm881 ( z , λ = 1)
とした場合）
”を利用して得られる
z1 S1 xopt + b1
)
(881)
di = wi(881
:
=
w
M =
M
_ opt
i
z N
S N xopt + bN
2
,
λ
=
1
(i = 1,2,L , N )
(881)
2
を図 3.5 に示す．期待通りに， Si xopt + bi と wi _ opt の傾向は同一（すなわち， Si xopt + bi が大きいほど
)
(881)
wi(881
“ xに対する Si x + bi の制御困難さ d i ”として wi _ opt を採用すること
_ opt も大きい）となっており，
2
の妥当性を示している．
6.0000E-02
5.0000E-02
4.0000E-02
3.0000E-02
λ：1.0
2.0000E-02
1.0000E-02
data505
data449
data477
data393
data421
data365
data309
data337
data253
data281
data197
data225
data169
data113
data141
data57
data85
data29
data1（大）
0.0000E+00
(881)
図 3.5 wi _ opt の分布（制約ありの場合）
(881)
2
• 縦軸は評価点ごとの wi _ opt の値 ，横軸は評価点を Si xopt + bi 値の大きい順に並べた．
21
Copyright ©NS Solutions Corporation, All rights reserved.
4. 結論
1 2
7
+ 7 ≥
= 0.881917 L を有する
9 N
9
λ = 1 のときに最大ノルム類似度
∑ {w( ) (z, λ )z }
N
iNorm881 ( z , λ ) :=
2
881
i
i =1
i
を活用すれば，下記の 3 種類の問題を効率的に解くことができる．
(1) 二乗ノルムに関するミニマックス問題 ―
min max ( S x + b
1≤ i ≤ N
x
i
2
i
)+ ρ x
2
l1 x u1
l ≤ Ax ≤ u
2 2
subject to
：
N が大きい場合には，
“ iNorm881 ( z , λ = 1) による線形制約凸非線形計画問題”を利用すれば，通常利
用される“補助変数νを利用した凸 2 次制約凸 2 次計画問題”よりも，高速にミニマックス問題の近似
最適解を求めることができる．たとえば N = 512 の場合には，データ依存性はあるが，5～33 倍高速に
ミニマックス問題の近似最適解を求めることができる．この計算速度優位性の起源は，
『補助変数νを利
用した定式化では“ Si x + bi
2
(i = 1,2,L, N ) ”なる 2 次制約式が追加されているのに対して，
≤ν
iNorm881 ( z, λ = 1) を利用した定式化では原問題と同一の線形制約条件に留まる．このため制約条件の
複雑さが iNorm881 ( z , λ = 1) を利用した定式化の方が低い』ことにある．なお iNorm881 ( z , λ = 1) を利
用した定式化で求められたミニマックス問題の近似最適解は，最大ノルム類似度
1 2
7
+ 7 ≥
= 0.881917 L
9 N
9
を有する評価関数の厳密な最適解である．
(2) N 個の二乗ノルムを最適化する問題 ―
i 番目の誤差を
Si x + bi
2
(i = 1,2,L, N )
と規定して，操作変数 x を使って，N 個の誤差を何らかの意味で最適化せよ：
iNorm881 は
i =1
p
最大ノルム類似度 ≥
1000
iNorm p (z , λ = 0) =
1
N
N
∑z
2
i
( )
{z }の平均値～{z }の最大値の間を
⇐
iNorm p ( z , λ = 1) ≅ max zi
2
1≤i ≤ N
2
2
i
i
λを調整することで任意に補間できる
22
Copyright ©NS Solutions Corporation, All rights reserved.
なる性質を有するので， iNorm881 ( z , λ ) のλを適切に調整することで
全体的な最小化
○
×
平均二乗ノルム
最大ノルム
ピーク値の抑制（平準化）
×
○
の特性の中間に位置する“問題要望に応じた最適な評価関数”を，
“ iNorm881 ( z , λ ) による線形制約凸
非線形計画問題”を複数回解くことで効率的に探索することができる．その結果，
“N 個の二乗ノルム
を最適化する問題”の問題要望に応じた最適解を効率的に求めることができる．
(3) 評価点の制御困難さの定量化問題 ―
(
)
di := xに対する Si x + bi の制御困難さ
subject to
2
l1 x u1
l ≤ Ax ≤ u
2 2
(i = 1,2,L, N )
(線形制約)
を定量的に決定せよ：
“ iNorm881 ( z , λ = 1) による線形制約凸非線形計画問題”を解いてミニマックス問題の近似最適解 xopt
を求め，
“ xに対する Si x + bi の制御困難さ d i ”として iNorm881 ( z , λ ) :=
2
∑ {w( ) (z, λ )z }
N
i =1
重み関数を利用して定まる
z1 S1 xopt + b1
)
(881)
di = wi(881
:
=
w
M =
M
_ opt
i
z N
S N xopt + bN
なる値を採用すればよい．
23
,
λ
=
1
2
881
(i = 1,2,L, N )
i
i
の
Copyright ©NS Solutions Corporation, All rights reserved.
5. 付録
5.1. 非線形計画問題の求解におけるダンピングファクターの機能
x ∈ R m に関する非線形評価関数 fi ( x ) ∈ R n
(i = 1,2,L, N ) に対する最適化問題を考えよう．
[ 非線形計画問題 ]
N
min ∑ f (x
i =1
x
i
0
+ x ) − ri
2
subject to
l1 x u1
l ≤ Ax ≤ u
2 2
where
決定すべき変数 x ∈ R m
既知の現状操作量 x0 ∈ R m
(i = 1,2,L, N )
既知の目標値 ri ∈ R n
□
非線形評価関数 fi ( x ) を逐次的に線形化することによって最適解を求めることを考えよう．逐次近似スキ
ームを下記のように設計する．
[ 逐次近似スキーム ]
ダンピングファクターρ > 0 として，
N
∂f ( x0 ) (1)
∆xopt := arg min ∑ f i ( x0 ) +
∆x − ri
∂x
i =1
∆x (1 )
(1)
2
+ ρ ∆x (1)
2
l − x ∆x (1) u1 − x0
subject to 1 0 ≤
≤
(1)
l2 − Ax0 A∆x u2 − Ax0
⇓
(
)
(1)
N
∂f x0 + ∆xopt
(1)
∆xopt := arg min ∑ f i x0 + ∆xopt
+
∆x (2 ) − ri
∂x
∆x ( 2 )
i =1
(
(2 )
+ ρ ∆x (2 )
(
)
2
)
(
2
)
)
(1)
(1)
l − x0 + ∆xopt
∆x (2 ) u1 − x0 + ∆xopt
subject to 1
≤
≤
(1)
(1)
(2 )
l2 − A x0 + ∆xopt A∆x u2 − A x0 + ∆xopt
(1)
(2 )
⇒L ⇒
最適操作量 xopt := x0 + ∆xopt
+ ∆xopt
+L
(
)
ここで，各反復段階での評価関数のノルムの中身は，
24
(
Copyright ©NS Solutions Corporation, All rights reserved.
∂f ( x0 ) (1)
∆x − ri = Si x + bi
∂x
where
∂f ( x0 )
Si :=
∈ R n×m
∂x
bi := f i ( x0 ) − ri
f i ( x0 ) +
x := ∆x (1)
という線形モデルであることに注意する．□
ダンピングファクター ρ を適切に選べば，反復が進むにつれて評価関数
(
)
(1)
(k )
f x + ∆x (1) + L + ∆x (k ) + ∂f x0 + ∆xopt + L + ∆xopt ∆x (k +1) − r
∑
opt
opt
i
i 0
∂x
i =1
(
N
)
2
+ ρ ∆x (k +1)
2
の第 1 項（誤差の総和）の変化量は徐々に少なくなり，操作量の大きさを制御する第 2 項が主要項になって
(1)
(2 )
(k → ∞ ) となり， 最適操作量 xopt := x0 + ∆xopt
+ ∆xopt
+L
(k )
くる．したがって ∆xopt → 0
が収束
して最適解が求まる．ただし，ダンピングファクター項が存在することで，求められた最適解は本来の非線
形計画問題の最適解からはわずかに異なる解となる．これはダンピングファクターを利用した逐次近似スキ
ームの欠点である．
5.2. 評価実験に使用した問題
3 章の「評価実験結果（ iNorm の効用）
」の節での実験には，下記の最適化問題を使用した．
[ 最適化問題 A（決定変数数 m = 512 個，制約数 = 50×
×512 = 25,600 制約，評価点数 N = 512 評価点 ） ]
min f (z
1
)
= S1 x + b1 , L , z N = S N x + bN
x
subject to
l ≤ A(Si x + bi ) ≤ u
x∈R = R
m
512
,
(i = 1,2,L, N = 512)
, Si ∈ R100×512 ,
bi ∈ R100 ,
A ∈ R 50×100 ,
l , u ∈ R 50
ダンピングファクター項はなし
□
f ( z ) = iNorm881 ( z , λ ) および f ( z ) = Q1 ( z ) の場合に，数理計画法パッケージ Numerical Optimizer の
準ニュートン法（2 階微係数を準ニュートン法によって求める内点法）を利用して，最適化問題 A を，
（ケースその１） 制約条件がない場合
（ケースその２） 制約条件がある場合
について解いた．
“補助変数νを利用した凸 2 次制約凸 2 次計画問題”の求解には，数理計画法パッケージ
Numerical Optimizer に準備されている SolveQP（2 階微係数を準ニュートン法によって求める内点法）を
利用した．
25