非線形最適化を行なう SAS の新プロシジャ NLP の紹介
岸本淳司
111111lllllllllll111111lllllllllllllllJlllllll
1lJlllll川 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllHlllllllllllllllllllllllllllllllllllll川 llllllf

1.

NLP は，現実の非線形最適化問題の形式を考慮して，非線形最適化と NLP の概要

目的関数や制約式の入力や結果の出力が柔軟にできるよ

非線形な関数 f (Xl> X2 ， … ， Xη) について，その最小値(または最大値)と，そのときのパラメタの値を求める技法を非線形最適化と呼ぶ.一般にパラメタ聞の関係に等式または不等式による制約条件を含むこともある.

うになっている.

2. NLP で実行できる最適化手法群
NLP プロシジャで実行できる最適化手法群には次のいわゆる数理計画法のうち線形計画でもないものの総称ようなものがある.と考えることができる.また統計学の応用で，非線形最・小規模問題用(パラメタ数40 まで)小二乗法または最尤推定法の解法に利用される(このとトラストリージョン法

きは制約は考えないことが多 L 、).非線形最適化には，問Newton-Raphson 法

題の性質に応じてさまざまな解法のバリエーションが存

直線探索っき N ewton-Raphson 法

在する.共通したアルゴリズムとして，なんらかの方法・中規模問題用(パラメタ数 200 まで)で定められた初期解からより良い解を反復して推定する

準 Newton 法

逐次近似法がとられる.

双準 Newton 法 (DBFGS.

NLP (NonLinear Programming)

は，リリース

6.
07 (UNIX は 6.09) の SAS/OR に追加された非線形最適化のための新しいプロシジャである.あたかも最適化手法のカタログのように数多くの手法群を網羅している.現在のパージョンでは.線形の等式または不等式による制約を与えることができる.将来のバージョンでは非線形の制約も可能になる予定である.

NLP で採用されている最適化手法群ではつの例
外を除いて，目的関数の l 階の徴係数(勾配)を必要とする.さらに 2 階の微係数(へッセ行列)を必要とする手法群もある.

NLP では，徴係数の計算に次の 3 通りの方法がある.

・内部関数コンパイラにより，解析的な導関数を自動的に計算する.

・有限差分近似により微係数を計算する.
・導関数の解析的な式を明示的に指定する.
前 2 者では，計算の速度は遅くなるが，導関数を指定する手間は省ける.

きしもと

干 104 中央区明石町 6-4

142 (34)

DFP)
DDFP)

ダブルドッグレッグ法・大規模問題用(パラメタ数 200 以上)

共役勾配法
・徴係数が計算しにくいとき
Nelder-Mead シンプレックス法-非線形最小二乗問題専用
Levenberg・ Marquadt 法

ハイブリッド準 Newton 法
Gauss司 Newton 法

最初のグループは 2 階徴係数(へッセ行列)を用いる手法群である.収束の効率はよいが，ヘッセ行列の計算には時聞がかかるので，パラメタ数40程度までの小規模な問題に適している.

Newton-Raphson 法はパラメタ数 40 までのときのデフォルトである.
ン法は Gay (1 983)

トラストリージョと More and S
orensen (1 983)

提案に近いアルゴリズムであり.のNewton-Raphson 法より遅いことが多いが，数値的にはより安定している.

最適点でヘッセ行列が特異になる場合には，直線探索っ

じゅんじ綿 SAS インスティチュートジャ

パン(BFGS.

きの Newton.Raphson 法もよい方法である.

2 番目のグループは2 階微分を計算しないで 1 階微分のみを用いてヘッセ行列の近似を更新してし、く手法群© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

である.問題のパラメタが多くなると，目的関数と勾配の計算に比べて相対的にヘッセ行列の計算に時間がかかのテストに頻用される Rosenbrock 関数である.

f(x)=100(X2‑X12)2+(l‑x1l2るようになる.したがって，比較的大規模な問題に関し初期値ては，最初の手法群に比べて収束に必要な反復数は多くで最小値

x o =( ー1. 2 ，1. 0)

として ，x*=(1,1)の点f( ポ )=0 が得られる.この問題を素直にコなるものの，総合的な効率はよくなる.ただし，近似へーディングすると，次のようになる.

ツセ行列の保存のために Newton-Raphson法と同程度

procnlp;のメモリを必要とするため，パラメタ数 200 程度が上限minf;となる.準 Newton 法と双準 Newton 法での更新公式

parmsxl= ー1. 2, x2=1.0;

は BFGS (Broydon , Fletcher , Goldfarb , Shanno)

f=100*(x2‑xl*xl)**2+(1‑xl)**2;の方法と DFP(Davidon , Fletcher , Powe l1)の方法から選択する.直線探索の手法も 12種用意されている.

run;
まず， PROC ステートメントで NLP プロシジャを

Newton‑ダブルドッグレッグ法は，準 Newton 法と似ているが，呼び出す.デフォルトの最適化法として，へッセ行列のコレスキー因子の近似を勾配から計算する

Raphson 法が選ばれる(パラメタ数から決定される).

手法で，DennisandMei (1 979)の提案による.

パラメタ数が 200を越えるような大規模な問題の場合，最適化法を明示的に示すには，TECH=NEWRAP とオプション指定を行なう.徴係数の計算は，デフォルトパラメタ数の 2 乗のオーダーで増加するヘッセ行列(のにより解析的に行なわれる.収束条件や表示情報などの近似)をメモリに収めておくことができなくなる.その設定はすべてデフォルト設定による. MIN ステートメ

ような場合は，収束は一般に遅いが，共役勾配法が唯一ントでは，最小化したい変数を指定する.最大化するたの解法となる.共役勾配法で利用可能な更新公式には，めには，代わりに MAX ステートメントを指定するこ

Powell-Beale , Fletcher-Reeves , Polak-Ribiere ，共とになる.

役降下法の 4 穫がある.直線探索の手法も準 Newton法

数の変数を指定することもできるが，その意味は後述す

MIN または MAX ステートメントでは，複と同様 12種類使える.

る. PARMS ステートメントでは，目的関数のパラメ

これまで紹介してきた手法はすべて微分の計算を必要タを指定する.ここでは同時に初期値も指定している.としていた.もし導関数が非連続あるいはきわめて計算

初期値を複数指定すると，反復過程に入る前にグリッドしにくいときには，微分計算を要しない Nelder-Mead

十一チを行なう.初期値を指定しなかった場合は，乱数シンプレックス法を使うことになる.ただし，この方法により初期値が設定される.最後に目的関数を通常のプはパラメタの数が多いとき効率が悪く，パラメタ数が 30

ログラム言語と同様な方法で指定する.ここでは 1 行で程度までの小規模な問題に対して適用すべきである.さ目的関数を書いたが，必要なら配列や DO ループなどをらに，この方法では線形式による一般的な制約をつける使ってロジックを記述することもできる.

ことができない.

上に示したプログラムを SAS の環境で実行すると，最後のグループは最小二乗問題専用の手法群である.

解が OUTPUT ウインドウに現われる.

その中には，ヤコピ行列の積和を計算してヘッセ行列を近似するため初期値とそのときの勾配，反復過程の履歴などが含まれその計算が容易にできるパラメタ数 60程度までの小規模る.最終的なパラメタ値と目的関数の値は次のように表な問題に適している

Levenberg-Marq u
ardt 法は安示される.

定性でハイブリッド準ニュートン法に優る.大きな残差があるときはハイブリッド準ニュートン法の方が速い場

OptimizationResults

合がある.ハイブリッド準ニュートン法の 3 つのノ〈ージParameterEstimatesョン (Flecherand Xu 1987)はすべて+ポートされている.直線探索法もオプションで選択できる.

Parameter

Estimatexl1.
0000000.
000000404x21.
000000‑0.000000216

Newton 法は一般に安定性に劣るので推薦できない.

23.

Gradient

Gaussｭ

NLP の簡単な実行例

ValueofObjectiveFunction=3.120954E‑16NLP の簡単な実行例を示そう.例題は，最適化問題
1993 年 3 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(35)143を用いる.

4. 複数の関数の統合(最小ニ乗推定と非線形最適化問題では，複数の関数 j" … ，j，協の二乗和mlnr;の何和)

数点複動=は六また靖明Zhlzを扱うことが多い.

5 1 32 43 14 15sq;
procnlpdata=testl lj(x)=~ Ì: f;2(x);tdata test¥;
input y x @@; cards;

最尤推定〉

parmsa b;

r=y‑a*exp(b ホ x);run;
NLP でMIN または MAX ステー

同様に，最尤推定では対数尤度を最大化することが問トメント中に変数を複数指定した場合，それらの値を二題となる.

乗和か総和の形式で統合した目的関数を最適化する.具

正規分布 N( μ，〆)から発生したとして，パラメタの体的には， LSQ オフヘンョンをつけると各変数の二乗和

μ と σ2 を推定するには，次の目的関数(対数尤度の -2を， FSUM オプションをつけると各変数の和を目的関倍)を最小化することになる.

たとえば ，数として評価する.

y=(12345)'

旬たとえば Rosenbrock 関数の場合，次のようにプログラムを書くことができる.というデータが(Yí 一 μ)2‑21ogL= 五 {l 叫NLP では次のようにコーディングできる.

procnlpl
sq;

datat
est2;

min11 j2;

ards;
inputY @@; cparms xl= 一 1. 2 ， x2=1.0;1234 5O*(x2‑xl*xl);
jl=112=I‑xl;

proc nlρdata=test2 j sum;

run;

minj;

procnlpjsum;

parmsm s2;
j=log(2*3.
14159*s2)+( 百 -m) **2/s2;

minj1j2;run;parms xl=- 1. 2, x2=1.0;
11=100 ホ (x2-xl *xl) ホ* 2;

j2=(1‑xl)* *2;run;

一般に数理計画法の一部として非線形最適化を考えた

最小二乗推定では，実測値と予測j 値との差(残差)の二乗和を最小化する.たとえば ，5. 制約条件のつけかた

y=(53411)' , x場合，パラメタ問の関係に等式または不等式の制約をつけることが多い.

NLP には，各変数の許容範囲の境界=(12345)' というデータに対して y=a*exp(b*x)

を指定する方法と，任意の線形関数について等式またはと L 、う非線形なモデルを当てはめることを考えよう.こ

不等式の制約をつける機能がある.将来のパージョンでのときは，次の目的関数を最小化するのが問題となる.

は非線形の制約式も可能になる予定である.
パラメータの境界制約は，

r =L:{Y a*exp(b*x;)}
2BOUNDS というステート

メントで指定する.変数と定数との聞に<=，>=,ところが，これを上の形式で書くとすると，データののいずれか(意味は自明)の関係演算子を指定する.複件数だけプログラムステートメントが必要になり，また数の制約をつけるときには，式をカンマで区切って指定データをいちいちプログラム中に書き込まなければいけする.複数の変数について共通の制約を与えるときや，ないので不便である.残差の二乗和のように同一形式の上限と下限とを同時に指定するときには，省略記法を用関数を統合した目的関数を最適化するには，あらかじめいることができる.次の 3 つのステートメントは，同じ作成されたデータセットから係数を読み込むと L づ方法制約の別表現である.

144 (36)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

bounds0<=x1 , 0<=x2 , 0 く =x3 ，x1 く =10 ，

x2 く =10 ，x3<=10;bounds0<=xl x2x3 , xl x2x3 <=10;bounds0<=x1‑x3 <=10;50GE

10 ‑15010

procnlρinest=betts;

より一般的に，線形式による等式または不等式の制約与えたいときには，UPPERBD

LINCON ステートメントを指定する.このステートメントでは，線形式と定数との聞に関係演算子を指定する.複数の制約を与えるときには，カminf;parmsx1 x2;
f=O.1 場 xl *xl+x2 本 x2 ー 100;run;

BOUNDS ス

ここでは，制約の係数を含むデータセットを， DATAテートメントで指定する境界制約は， LINCON ステー

ステップで作成している・ _TYPE_ 変数の値が PARMS

トメントでも指定できるがの行は，パラメタの初期値を与えている.

ンマを区切って指定するのも同様である.

2 種類の表現方法があるの1liIJ約を含む非線形最適化の例として， Betts 関数をとメタの上限を，それぞれ BOUNDS ステートメントに対応して示している.最後の GE の行は， LINCON ス

りあげよう.

テートメントで指定する一般的な線形制約に対応していf(x)=O.lx♂ +xz2 -100
制約

LOWERBDの行は各パラメタの下限を， UPPERBD の行は各パラは便利なものである.

10XI- X 2 註 10 ，る. GE というのは豆reater thanor~qual の略であ2 話 Xl 話 50 ，り，与えられた係数と変数との線形結合が _RHS_(~ight-50~三 X2 謡 50

x*=(2 , 0) の点で最小値 f*=f(x*)=

Hand 塁 ide) の値より大きいかあるいは等しいというこ-99.96をとる.初期値にはが=(ー 1 ，一1)を指定するとを表わしている.小さいかまたは等しいという関係に(これは非許容である).この問題は，は LE(~ess thanor~qual) が，等しいという関係には

この関数は ，NLP では次のよ

EQ(~旦回 1) というキーワードを用いることになる.

うに記述できる.

procnlp;

5.

minf;

おわりにNLP プロシジャは，作者 W olfgangHartmann のparmsx1 x2=‑I;
bounds2<=x1 <=50, -50 く =x2 く =50;

ノウハウを凝集した非線形最適化の至宝ともいうべき技I
incon

10*xl‑x2>=10;

法集である.本稿では，その使い方の一部を紹介したの

x1*
xl+x2*
x2‑1Q0;f=O.1*

みで，スピード，問題サイズなどの性能評価は行なわなかった.それは，いままで非線形計画法の包括的なプロrun;
大規模な問題になると，制約式をいちいち記述するのは不便なので，制約式の係数をデータセットから読み込む機能を利用することになる.

NLP ではパラメタの初期値，境界制約，線形制約の情報を INEST= オプショグラムはなかったと思われるので，比較するものがないからである.

NLP~t.，任意に設定した尤度関数を手軽に最適化できることから，新しい統計手法の開発に利用されることも期待したい.

ンで指定したデータセットから読み込むことができる.

参考文献

このデータセット中には，目的関数に含まれる変数のほか， _TYPE_ と L 、う文字型変数が必要である.また，一般線形制約をつけるときには _RHS_ と L 、う変数も必要

今野浩，山下浩(1 978) 非線形計画法日科技連

Hartmann , M. W. , (1992) The NLP Procedure
nstitute.
ExtendedUser'sGuide , SASIになる.

INEST= のデータセット入力を使って Betts 関数を最適化する例を示す.

dat
abett
s(type=est)
;
input
PARMS

̲type
̲$x1 x2 ̲rhs̲;cards;‑1‑1LOWERBD
1993 年 3 月号

2‑50
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(37)145