周一匿−5 日本オペレーションズ。リサーチ学会 2005年春季研究発表会
2次錘制約楷曹非線形最適他聞題の解法
01701240（株）数理システム ＊山下 浩 YAMASHITA Hiroshi
01702330 東京理科大学
矢部 博 YABE Hiroshi
1． はじめに本発表では，2次錘制約付きの非線形最適化問題に対
する主双対内点法による解法を述べる．この問題に対す るアルゴリズムは幾つか発表されているが，我々の知る 限り部分問題（通常のSOCP）を内点法によって扱い， 外部反復はSQP／SLPのようなフレームワークに依存し たもののみである．本方法は非線形最適化問題を主双対 空間における内点法の反復によって直接求解する点が特徴であり，主双対空間におけるメリット関数の構築がア
ルゴリズムの鍵となっている．対象とする問題は以下のようなものである．2次錘を
疋＝＝疋1×‥．×疋β 炉＝（㌔＝（鵡，軒∈乱れil鵡≧‖酬） と表すと，制約条件ヱ＝（ェ1，… ，諾β）t∈疋（⇔諾声0） はェi∈疋i（⇔∬i声0），五＝1，…，βを意味する．そし て解くべき問題を バリヤKKT条件r（礼㌧〃）＝0は，上記∬OZ＝0を エ。Z−〃e＝0，〃＞0，e＝（el，‥・，eざ）‘（e五はJordan 積の単位元）と修正したものである．ここで 言＝ち‡，言＝7JIz，ちモRnXれ によって，バリヤKKT条件を（還 ∇。エ（ひ
） ） 9（￡） 斎0才一〃e 叶叫両≡ ＝0，エト0トZト0 と変換する■ちはち‘＝2ノ4m㌔（piトArt〟（（が）2），p∈ int疋の直和で，血Ⅶ（p電）∈RmiXれiは叫pi）＝（碧欝）
と定義される・行列ちはAγW（斎）とArぴ（可が可換に なるように選ばれる． 2．アルゴリズム 2．1．外部反復 通常の内点法と同様に，パラメータ〃を減少させな がらバリヤKKT条件γ（叫〃）＝0を近似的にみたす内 点を逐次求めることによって最終的にKKT点を得ることを目的とする外部反復を行う．
【ⅨⅨT点を求めるための反復】 ステップ0．e＞0，穐＞0，た＝0とする．侮＼0とな る正数列（擁）を与える． ステップL肝（乱砿＋いイ城川≦几毎たをみたす内点Ⅷた吊 を求める． ステップ2・肝0（ひ頼1川≦どならばストップ ステップ3．た←た＋1とおいてステップ1に行く．D 定理上記アルゴリズムによって生成された点列を（址戊） として，点列（∬た）と（仇）が有界なとき，点列（zた†も 有界で，（祝蟻）の任意の集積点はKKT条件をみたす．□ 2．2．内部反復最小化J（ヱ），
∬∈取れ，条 件 g（諾）＝0，こr≠0
（1） と定義する．J：乱れ→Rl，タ：乱れ→吼mである．ラグ ランジュ関数と，その∬に関する微分は エ（w）＝J（〇）−y七夕（ヱトヱtエ ∇。ム（可 ＝ ∇J（ヱトA（￡）fy−Z となる．ここで ひ ＝（ェ，y，Z）t∈RnxRmxRれ A（諾）＝（▽飢（霊），…，∇耳m（∬））亡∈Rm… で，y∈Rm，Z∈Rれはそれぞれ等式制約と2次錘制約 に対する双対変数である．KKT条件は （∇重冒㌻’） F（叫〃）＝0に対するニュートン法は ＝0，拍0トZわO ro（ぴ）≡ （2） J（w）△ぴ＝一司叫〃） と書ける・ここで，諾OZ＝（芯10Zl，…，がoz5）りま〇jと g‘のJordan積をブロック成分とするベクトルを表す・ J（可＝ C −A（ヱ）￡ A（諾） O AγW（みち 0 −102− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.ステップ1．肝（咄，〃川づどならばストップ・ ステップ2．ニュートン方程式（2）によって探索方向△祝枕 ここで，C＝∇まム（w），あるいはヘッセ行列に対する近 似行列である． 主双対空間において大域的収束性をもつ内点法を構 築するために，主双対空間でのメリット関数を定義する． 本稿で提案するメリット関数は，【1］で提案された通常の 非線形最適化問題に対する主双対メリット関数を修正し たものである．BPP関数（＝barrier−penalty−pOtential 関数）を ダ（ひ）＝鞄p（ひ）＋〝印（w），〃＞0 と定義する． を計算する． ステップ3．ス ●αェmax＝mlni ップサイズの計算 テ
