111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111E墨霊園
非線形計画法 (4)一制約条件付き最適化問題一矢部博，八巻直一
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
111
1111111111111111111111111111111111
1111
1
1
1
11111111
1111111111111111111
111
111
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
1
1
1
1
1

れ，アメリカの AT&T ベル研究所の N.Karmarkar が1984 年 lこ発表した内点法が近年注目を浴びています.

1.はじめにこれはとりわけ.r数学的手法が特許申請された例」と今回は，制約条件のついた最適化問題の数値解法を紹介します.この問題は，次の形で定式化されます.

けとなって，現在，非線形計画問題における内点法の見直しがなされつつあります.

制約条例持問題n 変数の非線形関数 J(x) ( 目的関数〉を，等号制
約条件
ん (x)=O ，しても有名です. LP 問題での内点法の成功がきっか

以下で述べる解法は反復法です.これは，与えられた初期点から出発して解の近似点を生成していくものです.その際に，初期点をいかにうまく選ぶかが重i=l ,..., m要な問題になります.解の十分近くに初期点を選べば収束性が保証される場合，その数値解法は局所的にと不等号制約条件
9j(X) 三 0 ，収束するといい，この場合には収束速度が議論され

j=1 ,... ,/ます.一方，解から離れた初期点から出発しても解に収束する場合，その解法は大域的収束するといい，このもとで，最小化せよ.の場合は数値解法の頑健性が議論されます.現在，大

ここで ， J(x) を目的関数， 9j(x) ゃん (x) を制約関数とよびます.とくに，関数 f (x) , 9j(x) ， ん (x) のすべてが z についての 1 次関数のとき，線形計画 (LP) 問

題と呼び ， J(x) が 2 次関数での (x) ， h， (x) が 1 次関数のとき 2 次計画 (QP) 問題と呼びます.さらにいずれかの関数が非線形であるとき，総称して非線形計画問
題と呼びます.
LP 問題は，それ専用の有力な数値解法がほぼ確立されていて，第 2 次世界大戦が終結して聞もない
1947 年にアメリカの G.B.Dantzig が発表したシンプレックス法(単体法)が， 47 年を経た今日でも不動の地位を築いていることは周知の事実です.しかしな
がらその一方で， LP 問題の数値解法の見直しもなさを調整する直線探索法と，解の近似点、のまわりの限られた領域で次の点を探す信頼領域法の 2 つが代表的です.

具体的な数値解法を紹介する前に，まず準備として最適性条件を述べましょう.以下では，ベクトル V=(Vl"'" vnf に対して 11世 11 はらノルムを表し，•11Fで与えられます.

また，,9(X)= (91(X) ， ・・ . ,9 (x )f,h(x)= (h 1 (x) ， ・・・ ， hm(x))
T

やべひろし東京理科大学工学部と定義します.

干 162 新宿区神楽坂 1-3

やまきなおかずシステム計爾研究所
干 150 渋谷区桜丘町 2-9 カスヤビル

112(38)域的収束を実現する手段として，探索方向での刻み幅制約条件を満たす点の集合

S= {x εRπ1 9(X) 壬 0 ， h(x)=O}© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

を許容領域といい， 8 に属する点を許容解といいます.

数値が，領域の境界に近づくにつれて大きくなり，境任意の許容解 z に対して ， J(x.) 三 J(x) が成り立っ界上では無限大になるような関数を定義し，その関数

とき，許容解 x. εS は大域的最適解であるといいまの最小点を無制約最小化法を用いて求めることにあす.また ， x. の近傍内の任意のベクトル z に対してります.このような関数をバリア一関数といいます.

E 8 は局不等号条件に対するバリア一関数として，次のものがJ(x.) 三 J(x) が成り立っとき，許容解 x.
所的最適解であるといいます.

考えられています.

ラグランジュ関数を

L(x， λ ， μ=P(x;T) = J(x) ーゥ-，--，会t g・ (x)'J(x)+ λT g(x)+ μTh(x)= J(x)+~ンjgj(x) + 乞 μム (x)j=1P(x;T) = J(x)‑T 玄 log( ーの (x)).=1・ =1と定義したとき，制約条件付き問題を解くことは次の5 つの条件を満足する点 (X. ， À. ， 向)を見つけることに帰着 8 れます.

とくに後者はログバリア一関数と呼ばれるもので，LP の新解法では重要な役割を果たしています.
内点ペナルティ法のアルゴ、リズムは，まず初期点 Xo(許容領域の内点〉を選んで，単調に減少して Tk → O'i1xL(x , >.， μ)

マ J(x) + 乞 λj 'i1gj(x)となるペナルティパラメータ列 h} に対して，逐次バ

j=1

リア一関数 P(x; Tk) を最小にする点 Xk を求めて，最適解の近似点列 {xd を生成していくものです.その際，+~ンj 'i1 h j (x) = 。

バリア一関数の最小化には，前回紹介した無制約最小.=1

マ λ L(x ， >.， μ=Vμ L(x ， λ ， μg(x) 壬 0 ，化法が利用されます.

h(x)=O ，λ.

三入 jgj(x)このとき，適当な仮定のもとで0，i=1,…, 1,0,i=1,… , 1.

AP(ZK;TK)=f(♂)，

Af(zk)=f( ♂)が成り立ちます.

ただし， >.， μ をそれぞれ不等号，等号条件に対するラ

実際の問題では，最適解を得ることもさることながグランジュ乗数(ベクトル)といい，また，最後の条ら，より良い許容解を得ることが当面の目的である場

件式を相補条件といいます.

合が多いので，内点ペナルティ法はいつ停止しでも初以上の 5 つの条件をカルーシュ・キューン・タッカ

期点よりも良い許容解が得られている，という利点をー (KKT:Karush-Kuhn- Tucker) 条件といいます.と持っています.しかしながら，制約条件をみたす初期=点を必要とすることや，許容領域の境界に近づくにつ

1 ，…， m のすべてが線形ならば KKT 点のらは最適解れて数値的に不安定になることなどが，問題点としてになることが証明されています.

挙げられます.

くに ，J, gj , j

1 ，… ， 1 ， がすべて凸関数で

hj ， i

こうした裏付けのもとで，既存の数値解法の多くは2.
2 外点ペナルティ法と混合法

KKT 条件を満足する点を求めることを目指している最小化問題に等号条件が含まれる場合には，もはやわけです.

内点ペナルティ法は使えません.このことを克服する

2.

ペナルティ法ために外点ペナルティ法 (exterior penaltymethod) がそれでは，代表的な数値解法を紹介していきましょう.まず最初に，本節ではペナルティ法をいくつか紹

外点ペナルティ関数は z の全域で定義され，許容領内点ペナルティ法

域内ではペナルティ項が 0 ，許容領域の外側では境界不等号条件だけが付いた問題を考えましょう.内点ペナルティ法 (interior penaltyfunctionmethod またはbarrierfunctionmethod) の原理は，許容領域内での関1995 年 2 月号

るほか，初期点として必ずしも内点を求めなくてもよいように考案されています.

介します.

2.
1

考えられています.この方法は，等号条件を考慮し得から離れるに従って，関数値が無限大に近づくように構成されます.
外点ペナルティ関数の例として© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(39)1
13V，. L(x ， μ)P(x;r) = j(x)+r{乞 1 max(gj(x) , 0)1 α=0, Vμ L(x ， μ) =0(2)となります.このとき，この方程式にニュートン法を適用すれば k回目における反復式は

j=l=Xk+l Xk+aXk ， μk+l = μk+ a μk+玄|ん (x)I ß }i=lがあります.ここに，自， β 乏し T は正のペナルティパで与えられます.ただしで，次の連立 1 次方程式の解です.

ラメータで， r →∞の場合を考えます.
さらに，不等号条件に対してはバリア一関数の性質質をもっペナルティ関数を作ることもできます.これを混合ペナルティ関数 (mixed penaltyfunction) といョ( v:u L ( 叫k)V'L(凹k) = I巾¥ Vh(XkYい，たとえば，ここで Vh(x)Ehん.例1m恥)=吋引引仰削(何例j( z司) 一 T吉z 石羽:石窃E可)+勺戸( V，. L(叫) ¥I--:--~ I=‑I
1,1 ム μk J
¥ h(Xk) J,{ aXk ¥?r,マ辺 L( 叫)をもち，等号条件に対しては外点ペナルティ関数の性.
.
.

aXk とムμk は補正ベクトル(3)

Vh(Xk) ¥0l

J=[Vh 1(x) , …, Vhm(x)] ε R"xm は h(x)のヤコビ行列の転置行列，

V "，，，， L(x ， μ) は L(x ， μ) の zに関するヘッセ行列，および同 = (Xkt μk) です.
が考えられます.
なお， FiaccoandMcCor出ck(1968) の SUMT 法は，一般の制約付き問題 lこ対する混合ペナルティ法のことです.

乗数法の原理は，上記のようにラグランジュ関数を構成して，その停留点を探索することにあります.もし，ラグランジュ関数のへッセ行列 V 2 L が正定値行列であれば，ニュートン法は安定に極値に収束すること

2.
3 正確なペナルティ関教法が期待できます.しかし，残念なことに V2L は正定値

これまで述べたペナルティ法では，ペナルティパラメータ T を T → o (もしくは T →∞)としながら無制約最小化(部分〉問題を何回も解かなければなりませんでした.これに対して，ペナルティパラメータを変更することなく，変換された無制約最小化問題を1 回解くだけで，もとの問題の解が得られるような手法が考えられています.これは正確なペナルティ関数法 (exact penaltyfunctionmethod) と呼ばれ，z 祖 g­

行列ではないのでそのままニュートン法を適用することには問題があります.そこで，ラグランジュ関数にペナルティ項を付加して，局所的に関数が凸になるように工夫することが， Hesten 田 (1969) と Powell (1 969)によって独立に試みられました.この関数を拡張ラグランジュ関数 (augmented Lagrangi 日 function) と呼び，次のように与えられます.

Q(x ,Jl ;r) =j仙 2μ ん(Z)+jTZA 例will(1 967) によって提案されました.正確なペナルティ
ただし， γ はベナルテイパラメ一夕です.もし VQ =0関数として，たとえばとなる点が制約条件をみたすならば，それはラグランP(x;r) = j(x)+r{乞 max(の (x) ， O)
j=l+乞 Ih;(x)l}ジュ関数の停留点になります.乗数法の重要な利点のひとつは，ペナルティパラメータ γが有限の値でよい(1);=1乗数法のアルゴリズムの基本は，与えられた μkt rkがよく知られています.

3.ということです.

に対して，無制約最小イヒ法で関数 Q(x ， μ k ， rk) の最小点 Xk を求めて点列 {xd を生成することです.その際，乗数法

ペナルティ関数を用いる方法は，許容領域の境界付近で数値的に不安定になる，という問題点を抱えています.ペナルティ法の持つこの欠点を回避する方法として，乗数法 (multiplier method) があげられます.等

ペナルティパラメータ η とラグランジュ乗数の推定値内が更新されます.ラグランジュ乗数の推定値の更新については，いくつかの更新公式が提案されていますが，次の 2 つが代表的です.

号条件付き最小化問題を考えてみましょう.ラグランμk+l=ジュ関数を L(x ， μ) としたとき， KKT 条件はμk+l=114(40)+rkh(xk) ,山 +Hk1h(Xk)μk© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

QP 問題 (b).マ'‑'-町'-.

Hk='ïl h(Xkf 'ïlxxQ(Xk. μkjTk)ー l1 'h(Xk)

線形制約条件fg(Xk)+l'g(Xk ~X 壬 0 ，です.

h(Xk)+l'h(Xk)
T~X

不等号条件がある場合には，スラック変数を導入して，以上と同様の議論ができます.

=0のもとで. 2 次関数

4. 逐次 2 次計画法

juTB山+'ïl州T ムz

本章では，準ニュートン法の考え方に基づく方法を紹介します.まず等号条件付き問題を考えてみましょう.基本的な考え方は乗数法と同じで，非線形方程式を ~X ERn について最小にせよ.

(2) に対するニュートン法です.ただし，もうひと工夫

以上のように，各反復で QP 問題を解いて探索方向します.すなわち， μk+1 = μk+ ム内とおくと，方程~Xk を決定していく方法を逐次 2 次計画法 (sequential

式 (3) はquadraticprogramrningmethod) といいます.この方{ ~Xk ¥(l'f(Xk)¥.
,,-., I¥ h(Xk) J

l'2L(Xk' μ k) I‑‑. I=一 I\μk+ 1 J

法は，ヘッセ行列'ïlxxL(Xko 九， μk) を行列 Bk で近似するという意味から，制約条件付き問題に対する準ニュートン法とみなすことができます.と書けます.

ここでさらに，無制約問題における準ニュートン法の考え方を用いて，ヘッセ行列'ïlxxL(xk! 内)を適当な近似行列 Bk で置き換えれば，上式は次の方程式に帰着されます.

準ニュートン法という観点からみれば. Bk の更新公式をどう選ぶかが重要な問題になります.これに関しては. Powell(1 978) が正定値性を保存することを考慮して. BFGS 公式に対応する次の更新公式を提案しました.

Bk~Xk +l'f(Xk)+'ïl h(Xk) μk+1 = 0,B.
‑"‑l叶A九 (Xk) +l'h
(Xkf~Xk =o.

sk(Bkskf .ZkZ'[=B.応 ー Bk+一一一(BkSk )T Sk
Z'[SkTこだし，

実は，この式が次の QP 問題の KKT 条件であることが容易に確かめられます.
QP 問題 (a)Zk

れ ω+ (1‑øk)Bks k,SkX
k+1‑Xk ,Ykl'x
L(xk +l， λk+1 ， μk+ d

線形等号条件h(Xk)+'ïl h(Xkf ム X=oのもとで‑l'xL(Xk. λ k+1 ， μk+ d2 次関数

れ= ~ y'[Sk2:'IjJ仏 sr 土 J、juTBKAZ+ マ仇 )T ~Xをム X E Rn について最小にせよ.

ハー 1.\_Tn←llそうでないとき当号干与三苧与skベ B Jr. s /C-れ)です.ここで， ψ= 0.1 または ψ= 0.2 が選ばれます.
とくにれ= 1 が採用された場合には，本来のセカン

このとき Bk が正定値対称行列ならば，この QP 問題

ト条件を満足する BFGS 公式になります.この更新は一意解ム引をもち，内 +1 が線形等号条件に対するラ公式を Powell の修正 BFGS 公式といいます.

グランジュ乗数ベクトルになります.したがって，非収束性に関しては，正確なペナルティ関数 (1) ，こ直線形方程式を解く代わりに QP 問題 (a) を解いて探索線探索を適用した逐次 2 次計画法の大域的収束性が方向ム Xk を求める解法が考えられるわけです.

Han (1 977) によって示されています.また，収束の速以上の考え方をそのまま制約条件付き問題に適用すれば，次の問題が得られます.
1995 年 2 月号

さに関して. Powell(1978) が修正 BFGS 公式の超 1 次収束性を論じています.

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

(41)1155. 主現対内点法となるように Qxk ， 山 kKarmarkar 法以来， LP 問題や QP 問題に対する内点法が理論的にも実用的にも非常に活発に研究されています. LP 問題に対する内点法の中でも近年とくに主双対内点法 (primal-dual interiorpointmethod) が有望視されており， Kojima , M
izuno andYoshise(1989) の研究に端を発して，多くの研究者によって大域的収束性(とくに多項式オーダ性)や局所的収束性が研究されています.そうした状況の中で，非線形最適化問題の内点法の検討は今後の大きな課

主双対内点法と従来のニュートン法との本質的な違いは，扱う方程式に摂動項Tk e が含まれていること，点列 {(Xk' Zk)} が非負条件に関して内点になるように減速をしなければならないこと，です.さらに，このことに付け加えて，ラグランジュ関数のへッセ行列¥7xxL(叫)を近似することも考えれば，ニュートン方程式に対応する連立 1 次方程式 Jkd叫 = -r(wk) を解いて探索方向山IJk= (dxk， ム Yk ， dzk)T を求める解法が得られます.ただし( Gk

題です.本節では，非線形最適化問題に対する主双対内点法を紹介します.
非線形最適化問題は次の形に書き換えられることに注意しましょう.

が選ばれます.したがって，‑A(Xk)T ‑[ ¥Jk= IA(Xk)00¥0Xk JZkです.ここで G kI= \7xx L (Wk) の場合がニュートン法に基づく主双対内点法 ， G k をへッセ行列の近似行

h(x)=O , x 主 0 のもとで f(x) を最小化せよ

列にとった場合が準ニュートン法に基づく主双対内点
不等号条件 g(x) 壬 0 はスラック変数を導入すれば，上式の形で書けます.上記の問題のラグランジュ関数を法になります.収束性に関しては，非負条件にログバリアー関数を，そして等号条件に正確なペナルティ関数をそれぞれ適用して得られる直線探索評価関数
L(却) =f(x)‑yTh(x)‑zTx(4)と Armijo の直線探索法を組み合わせることによって，Y乱m凶hita( 1992) が大域的収束性を示しています.まとしたとき， KKT 条件は次式で与えられます:

た，局所的超 1 次収束性が Yamashita 乱nd Yabe(1993)\7 x L ( 即) =0, h(x)=0 , XZe=0,によって示されています.

z と 0， z 主 0，6.

(非負条件)

ただし ， y ε Rm ， z εR飽はそれぞれ等号条件，非負以上で，制約付き問題に対する代表的な数値解法=(x ， 仏 zf ， X =の紹介を終わります.ここで述べた解法以外 lこも，信diag(zl>Z2 ， ・・・ ， zπ) ， e =頼領域法や射影法など有効な数値解法がいくつかあ条件 iこ対するラグランジュ乗数t W

diag(xl'X2 ,..., x ,,), Z

おわりに(1 ， 1 ，...， 1)T εP です.このとき相補条件 XZe =0りますし，また，コンプレックス法のような微分の情を XZe=re(T は非負定数)で置き換えた次の方程報を使わない解法もありますが，ここでは割愛しました.実際問題としてよく扱われる，制約条件付き非式を考えます:I¥
7x L (卸)r( ω) 三h(x)¥I0 ¥I=I0 I¥XZe‑ Te I

線形最小二問題に対する数値解法にも触れませんで

(5)

¥0 I

x>O ， z>O.(x ， z が正であることに注意)

主双対内点法は，この非線形方程式に対してニュートン法を適用したものです.主双対内点法では，変数(Xk， Zk) が非負条件に関して内点になるように刻み幅が調整されます.すなわち，

Xk+l

Xk+ 白 xkdxk >0 ,zk+lZk+azk ム zk >0116(42)した.

さて，非線形計画法に関する連載も今回で終了いた
します.本連載の主なねらいは，第一回目で取り上げた専門書の紹介です.残りの三回分はそのための補足であり，これから非線形計画法を勉強しようとする人たちが気軽に専門書をひもとくためのウォーミングアップを兼ねています.したがって，ここで十分に説明できなかった方法については，第一回で紹介した専門書を参考にしていただければ幸いです.

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

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