微分を用いない制約無し最適化手法の収束条件

全文

(1)Title. 微分を用いない制約無し最適化手法の収束条件. Author(s). 金光, 秀雄. Citation. 北海道教育大学紀要. 第二部. A, 数学・物理学・化学・工学編, 41(2) : 61-68. Issue Date. 1991-03. URL. http://s-ir.sap.hokkyodai.ac.jp/dspace/handle/123456789/6179. Rights. Hokkaido University of Education.

(2) . 北海道教育大学紀要（第２部Ａ）第４１巻第２号ｌｏｆＨｏｋｋａＪｏｕｍａｉｄｏＵｎｉｖｅｒｉｔｙｏｆＥｄｕｃａｔｉｓｉｏｎｌＩＡ）Ｖｏｔｌｏｎ（Ｓｅｃ ‐４１．２，Ｎｏ. 平成３年３月Ｍａｒｃｈ，１９９１. 微分を用いない制約無し最適化手法の収束条件. 金光秀雄北海道教育大学函館分校総合科学教室函館０４０. Ｃｏｎｖｅｒｇｅｎｃｅ. ＣｏｎｄｉｉｏｎｓｆｏｒＵｎｃｏｎｓｔｒａｉｎｅｄＯＰｔｉ１ｔｉｚａｔｉｏｎＮ【１１ｅｔｈｏｄｓｉｖｅｓｗｉｔｈｏｕｔＤｅｒｉｖａｔ ‐. ＨｉｄｅｏＫＡＮＥＭＩＴＳＵ１ｎｔｉｅｔａｔｅｄＡｒきりｒｓａｎｄＳｃｅｎｃｅｓＬａｂｏｒａｔｏｌ１γ，ＨａｋｏｄａｔｅＣｏｌｅｇｅ，ＨｏｋｋａｉｄｏＵｎｉｖｅｒｉｉｓｔｙｏｆＥｄｕｃａｔｏｎＨａｋｏｄａｔｅ０４０Ｊａｐａｎ，. Ａｂｓｔ・ａｃｔＴｈｉｓｐａｐｅｒｃｏｎｓｉｄｅｒｓｃｏｎｖｅｒｇｅｎｃｅｐｒｏｐｅｒｔｉｅｓｏｆｉｔｅｒａｔｉｖｅｍｅｔｈｏｄｓｆｏｒｕｎｃｏｌｉｌｓｔｒａｉｅｄｏｐｔｌｎ‐ ｉｚａｔｉｏｎｗｉｔｈｏｕｔｄｅｒｉｖａｔｉｖｅｓ‐ Ｓｏｍｅｍｅｔｈｏｄｓｉｔｅｒａｔｅｍｉｉｉｏｎｏｆｄｉｉｏｎｓｅｔｎｍｉｚａｔｒｅｃｔｓ｛仏，偽， … … ‘ ‘ｄｉｉｏｎｓｅｔｍｅｔｈｏｄｓ”）‐ Ｍａｎｙａｌｇｏｒ４ｎ｝（ｒｅｃｔｉｔｈ［ｎｓｗｉｉｔｈ “ｄｉｏｎｓｅｔｍｅｔｈｏｄｓ” ｈａｖｅｂｅｅｎｒｅｃｔｐｒｏｐｏｓｅｄ，ａｎｄｔｈｅｃｏｎｖｅｒｇｅｎｃｅｐｒｏｐｅ賞ｉｅｓｏｆｔｈｅｓｅａｒｇｏｒｉｔｈｌｎｓａｒｅｓｈｏｖｍｉｎＰｏｗｅｌｌｍｅｔｈｏｄ［３］ｅｔａｌｈｅｇｅｎｅｒａｌｃｏｎｖｅｒｇｅｎｃｅｐｒｏｐｅｎｉｅｓｏｆ “ｄｉｒｅｃｔｉｏｎｓｅｔｍｅｔｈｏｄｓ”ｉｓｎｏｔｈ ‐ Ｈｏｗｅｖｅｒ，ｔｓｏｗｎ‐. Ｔｈｉ ’ Ｆｉｔｉｓｐａｐｅｒｓｈｏｗｓｔｈｅｐｒｏｐｅｎｉｅｓｏｆ“ ｌｉｎｅｓｅａｒｃｈ’ ｒｓｔｃｏｎｓｔｎｌｃｔｓａ “ｄｉｒｅｃｔｉｏｎｍｌｎｌｍ‐ ‐ ’ ‘ ‘ ” ｉｚａｔｉｏｎｍｅ口ｌｉｎｅｓｅａｒｃｈａｎｄｓｈｏｗｓｔｏｄｂｙｕｓｉｎｇｌｈｉ食ｆｒｈｉｅｏｅｅｔｈｐｐｓｏｓｍｅｔｏｄ，．Ｎｅｘｔａ “ｄｉｒｔｔｈｏｄ”ｉｅｃｉｏｎｓｅｔｍｅｔｒｌｉｓｃｏｎｓｒｕｃｔｅｄｂｙｔｉｏｎｍｉｎｉｍｉｉｏｎｍｅｔｈｏｄ’ ａｎｄｔｈｉｅ”ｄｒｅｃｔｚａｔｓｌｅａｄｓｔｏ，ｔｈｅｃｏｎｖｅｒｇｅｎｃｅｃｏｎｄｉｔｉｏｎｓｏｆｔｈｉＦｉｌｌｈｓｍｅｔｈｏｄｔｎｉａｃｏｎｖｅｒｇｅｎｃｅｐｒｏｐｅｒｔｅｓｏｆｔｈｅｒｅｌａ×ａ－ｙ ‐ ，ｅｉｏｎｍｅｔｔｈｏｄａｎｄｔｈｅＤａｖｉｅｓ ‐Ｓｗａｒｍ‐Ｃａｍｐｅｙｍｅｔｈｏｄ［４］ｗｈｉｃｈｈａ. ｖｅｎｏｔｂｅｅｎｒｅｐｏｒｌｔｅｄｅｓｅｗｈｅｒｅ. ａｒｅｓｈｏｗｎ‐. １．はじめに. 最適化問題を解くための数値的手法は最近めざましい進歩をとげ幅広い分野での応用が急，速，に進められている‐ 最適化問題の中で制約条件のない問題を制約無し最適化問題と呼び次のよう，６１（）.

(3) . 金. １６８. 秀. 光. 雄. に定式化される．. ｆ（“，ェＥＲｎれているここで関数ｆ：Ｒｎ→Ｒは目的関数と呼ばれ，この問題を解くための手法が多く提案さ. 最小化. 分を用いない手法は，目的関数が非常に複雑でその微分を解析的に求］２１］［．とりわけ関数の微，［めることができない場合などに有効である．，，ｄｎ｝，偽ｒ …・微分を用いない制約無し最適化問題を解くための手法の中で，ある方向の集合｛〆「を定め，その方向の最小化を繰り返す手法がある（以後，この手法を方向集合法」と呼ぶことにな「方向集合法」を用いたアルゴリズムが提案されてきている．しかしする）．現在まで，さまざま］などで示されているｌｌ法［３ながら，「方向集合法」の収束性については，共役方向を用いたＰｏｗｅが，「方向集合法」全体としての収束性は証明されていない．「「本論文では，まず，「直線探索法」の性質を明らかにした後，直線探索法」を用いて方向最小「「化手法」を構成し，その性質を明らかにする．つぎに，方向集合法」を方向最小化手法」を用いとて構成し，この手法の収束条件を導く．最後に，従来収束性が示されていなかった軸方向探索法「ゴズムであることを示し，両者のＤａｖｉ ‐ｓｗａｍ‐Ｃａｍｐｅｙ法［４］が方向集合法」を用いたアルリｅｓ. アルゴリズムの収束性を示す．. ２．記. 法. ｎ１）０でないベクトルの集合ｄ，ｍＥＲを，偽，…，〆Ｄｍ＝｛感，物，…，４ｎ｝. で表す２）後，物，…，４ｎの張る部分空間をｓｐａｎ［Ｄ一で表す．すなわち，ｓｐａｎ［仏，偽， …，４ｎ］＝ｓｐａｎ［Ｄｍ］＝｛２α威ー雄ＥＲ｝ｉ＝Ｉ. となる．. ］で表す‐ ｎン集合をＡｓ彰，，Ｄｍ３）ｓｐａｎ［Ｄｍ］をズ，ＥＲだけ平行移動して得られるアフィすなわち，Ａｓ』，ｐａｎの一｝，十ｓｐａｎ［Ｄ一；｛ね十ｄｌｄｅｓ，Ｄｍ］＝％. ＝｛％１ズ；ね十Ｘ館仏｝ｉ＝Ｉ. となる．. ４）１，２，…，ｍの要素からなる添字集合をｌｍで表す．すなわち，ｌｍ＝｛１，２，…，ｍ｝となる．. ５）′：Ｒｎ→Ｒとねに対して定義される準位集合を次のように表すことにする．ｎＬ（工Ｊ＝｛メヂ（“ ≦ヂ伝送尤ＥＲ｝６）今後，アルゴリズムを次のように表すことにする．（出力変数１，出力変数２， …，出力変数ｐ）：アルゴリズム名（入力変数１，入力変数２， … …，入力変数ｑ）；. ｛説明｝. この意味は，入力変数１，入力変数２， …，入力変数ｑを与えてアルゴリズム名で識別されるが得らアルゴリズムを実行すると，その結果として出力変数１，出力変数２， ……，出力変数ｐ６２（）.

(4) . 微分を用いない制約無し最適化手法の収束条件. １６９. れるということであるまた｛説明｝は入力変数等の説明である特に出力変数が１つの場合は．．. 両側の（）を省いて表現する ‐. ３．直線探索法３－－直接探索法のアルゴリズム直線探索法は大きく二つに分けることができる一つは正確な直線探索法もう一つは有限回の．，手続きで定義される直線探索法であるここでは正確な直線探索法について述べる ‐ ，．・アルゴリズム：直線探索法 α ，：＝Ｌｍ（エー，仏）；｛ｄ，方向の最小化｝ただし， α は， αだ｛α１ｆ α．十α４）＝ｍｉｎ／伝，十β域）｝ βＥＲ. とする‐. このとき，ヂＥＣＩならばクＴア（繍十α ）＝０，ｄ，. （１）. が成立する．但し， ″＝（ａ／ａ寛）ｉ，Ｔは転置である．３‐－直接探索法の性質補題１）ｆＥＣＩが狭義の凸ならば（１）を満足する点は一意である，．証明）今，（１）式を満足するα ）が存在すると仮定すると，ｆの狭義の凸性より，２（α ２．≠α ，α ，／（ェ十α ．ｄ）〉／（ヱ十のｄ）＋（α，一物）グＴア（ズ十 α ２ｄ）α ＝ｆ（尤十α ）２ｄ. 同様にして，／（ェ十α ）クＴア（ズ十α ２ｄ）〉／（エ十α，ｄ）＋（α ２－α．．α）〆. となり，矛盾する‐ よって（１）式を満足する燭は一意である圏．. ４‐ 方向最小化手法４．１方向最小化手法のアルゴリズム方向集合Ｄｍを定め，これらの方向の直線探索を行うアルゴリズムを次のように構成する．・アルゴリズム：方向最小化手法続十．：＝ＭＤ伝．，Ｄ一；｛〆（ｉ＝１，２，…，ｍ）ＥＤｍ方向の最小化｝ｆｏｒｉ：＝ｌ. ｔｏ. ｍ. ｄｏ. ｂｅｇｉｎ α ，：＝Ｌｍ（ズー，頒）；. ｛〆方向の最小化｝. 為十１：ニエー十 α ，４. ｅｎｄ；. ６３（）.

(5) . 金. １７０. 秀. 光. 雄. ４．２方向最小化手法の性質方向最小化手法は次のような性質を持っている．は補題２）／巴ＣＩのとき，％＊がＡｓ［％，，Ｄｍ］上の最小点となるための必要条件，ワワ（）↓ｓｐａｎ［Ｄｍ］を満足することである．ｐａｎ［Ｄｍ］が存在して，）↓ｓｐａｎ［Ｄｍ］を満足しないとすると，あるｄｅｓ）証明 ×＊が ″ツ（尤＊. （２）. ワツ（尤＊）α≠ ０. １－矛盾する．１となり，明らかに〆がＡｓ脳，，Ｄｍ］上の最小点となることに分条件となるための必要十尤系１） ′ＥＣＩが狭義の凸関数の時，ががＡｓ［，，Ｄｍ］上の最小点は，. ダリ（が）↓ｓｐａｎ［Ｄｍ］を満足することである．. －証明）必要条件は補題２より明らか，十分条件は，（２）式を満足するもう一つの点 × が存在していると仮定すると，補題１において，ｄ＝工＊－ズー，. α，＝０，. α２；１，. ズニエ. とおくことにより，明らか．霊・定理１）関数′巴ＣＩが狭義の凸関数のとき，方向最小化手法％ｍ十．ＥＭＤ伝．，Ｄｍ）において，ズがＡｓ脳，Ｄｍ］上の最小点となるための必要十分条件は，（３）. 拓ｍ十，ニズ１. を満足することである．. 証明）１）必要条件方向最小化のアルゴリズムより（４）. ，４繍 ” ＝エー十 ≧ α ，均：＝Ｌｍ脳，依）；. ｛仏方向の最小化｝. このとき，（１）式と補題１より，任意のｉｅｌｍに対して ″ リ（為十 α威）後に０なる鱒は，一意的に定まる．また，補題２より，任意のｉＥ１ｍに対して）４＝０，４ＥＤｍ ″ ワ（％．が成立する‐ これらのことより，ぬ＝０，. ｉ＝１，２，…，ｍ. すなわち，（４）より籍ｍ＋１＝尤１. が成立する．圏２）十分条件仮定すると，系１より，あるｄＥｓｐａｎ絢十，がＡｓ脳，Ｄｍ］上の最小点でないと，＝ｘ，で，ェ. ［Ｄｍ］が存在して，（５）. ）〆≠ ０ダリ（％ｍ十，. ｉＥ１が成立する．また，ｄｅｓｐａｎ［Ｄｍ］より，ある蛇≠０（ｍ）が存在して，（６）. ｄ＝３ β純，ｉ＝Ｉ. ４ＥＤｍ. が成立する．このとき６４）（.

(6) . 微分を用いない制約無し最適化手法の収束条件. １７１. ″Ｔア（第ｍ．十）ｄ＝ ″Ｔア（妬ｍ十．）・２ゑ４ｉ＝１. ＝ × 姦 ‐ ″Ｔア（濁ｍ十．）・４ｉ＝１. （７）. ｍｍ；芝髭・ ″Ｔア（尤，十３ α ．仏）・仏ｉ＝ｌ. ｉ＝１. となり，補題１と直線探索におけるｆの値の単調減少性より妬＝％のとき＝０ α ．．，ｍ十，. （ｉ＝１，２，…，ｍ）となるからｍ. ｍ. ｉ＝ｌ. ｉ＝１. Ｘ逐・ ″Ｔア（劣．十宝 α ．後）．偽. ＝２Ａ ‐ ″Ｔプ錠叶．）‐ ４＝０１＝１. が成立し，（５）と矛盾するよって続．＝葛のときねはＡｓ［ｘ．十．，，，Ｄｍ］上の最小点を与える．圏. ５‐ 方向集合法５‐ー方向集合法のアルゴリズム以上の方向最小化手法を用いることにより次のような方向集合法のアルゴリズムを構成できる，．・アルゴリズム：方向集合法｝Ｄ糟）；｛初期点ズｑ）と方向集合Ｄ；｛雄１）ｄ夢 … ｄ鐙％＊：＝ＭＤＳ（ｄｌ｝方向をあたえて，点の，ｍ，，，｝移動がなくなるまで方向最小化手法を繰り返すことによりｚを求める｝，ｓｔｅｐｌｋ：＝１；｛ｋ：繰り返し回数｝）Ｄ轡）；｛〆ｋ）ｓｔｅｐ２ｘ瀞．：＝ＭＤ（）方向の最小化｝ｉ＝１（ｉェｒ，，２，…，ｍ）ＥＤ培）！ｆｌｌエ器．－雌ｋｓｔｅｐ３ｉｆ＝ ○ ）：＝×盟；ｓｔｅｐ４ｘｒ十１．. ｔｈｅｎ. ＊尤：＝尤瀞．；ｅｎｄｏｆＭＤｓ；. 次の繰り返しで用いる方向集合Ｄｒｌ｝を定める；ｋ：＝ｋ＋１としてｓｔｅｐ２に÷戻‐る；. このようにして方向集合法は点の移動がなくなるまで方向最小化手法を繰り返すアルゴリズムとして構成されている定理１とｓｔｅｐ３により方向集合法の収束性が示されたように考えられるが．，定理１は葛ｍ十，＝％なる点に収束することを前提としているそこで以降の定理により．，，燭ｍ十，＝ｚ，な. る点に収束することを示すまずＤ密）をＤと固定した場合の収束定理について述べる．ｍ．５‐２. 方向集合法の収束条件. 方向集合法の収束条件に関する定理を以下に示す．定理２）方向集合をＤｍに固定した方向集合法ＭＤＳ（ｄｌ）Ｄ）が次の二条件，ｍ，Ｉ１）ｆＥＣは狭義の凸関数６５（）.

(7) . 金光秀雄. １７２. ）Ｄ一がコンパクト））ｎＡｓ［ｄｌ２）Ｌ（工？，を満足するとき，その収束点ェ＊は，Ａｓ脳，，Ｄ一上でのヂの最小点を与える．証明）アルゴリズムＭＤにより，任意のｋに対して，）１）））≦ｆ（（８）ｆ（％そ尤ｒ＋が成立する．また条件１）より， ′ は下に有界であるから極限をもち，１）））ｉｍヂ（）＝ｌｌｉｍｆ（（９）尤ｒ＋ズｒｋ－ｏｏ. ｋ→ｏｏ. ）Ｄｍ］であるから，ある部分列Ｋがｋ｝｛）ＥＬぜ１）ｎＡｓ脳？さらに，条件２）と（８）より，ｚ，とれて，ｋＥＫに対して，（１０）. （１１）. １）１））｝；％ｒ＋ｉｍ｛寛ｒ＋｝ニズｒ）ｌｉｍ｛尤ｆ，ｌｋＥＫ. ｋＥＫ. ０）より，１となる．ヂの連続性と（９），（１）１）））＝≧蜜月蒋十ロｍバザ）；” が）＝ヂ（ズｒ＋ｋＥＫ. となる．ここで，｝感仏ＥＤ１）；尤ｒ）＋〆一ｗ劣ｒ＋ｍ，ｉ＝Ｉ. ｔｅｐ３およびｓｔｅｐ４により，とすると，（８）と／の連続性，およびアルゴリズムＭＤＳのｓ任意のぬに対して，ｍ. １）十三））＝／（ヂ（工ｒ工ｒ＋ｉ. ＝ｌ. ）（１２. ｍ. ｝＋Ｘα威）４）≦／（尤ｒｉ＝Ｉ. ｉ＝１，２，…，ｍ）となる．したがって，となる．しかしながら，補題１より， αＦに０（）；ズｒ）ｒ＋１. となり，定理１より，ヂの最小点に収束する．圏定理２より，次の定理を導くことができる．｝）Ｄ吊定理３）方向集合法ＭＤＳ（燈１，）が次の三条件１）ヂＥＣＩは狭義の凸関数））がコンパクト２）レベル集合Ｌ（感１. ）］が全空間ｒを張る３）任意のｋに対して，ｓｐａｎ［Ｄ覧ときその収束点をすべて満足するｘ＊はＲｎ上で定義されたｆの最小点を与える．，定理２は次のような線形凸計画問題Ａの解を与えるものである．. 問題Ａ）（１３. 最小化ｆ（“，. ）（１４. 条. 件. ｎ％ＥＲｎ， ′：Ｒ →Ｒの凸関数. ｉ＝１，２，…，ｐ）， α鳶－ろ，＝０，（. 魚ＥＲｎーＥＲ，ろ. ｝とＤｍを与えてやる）Ｄｍ）において，（）式を満足するように膜１１４つまり，方向集合法ＭＤＳ（感１，と，定理２の二条件を満足すれば方向集合法によって求められた点ェは問題Ａの解となる．定理３は制約無し最適化問題における，方向集合法の収束定理である．特に方向集合がｎ個の方向で構成されているとき，条件３）は，ｎ個の方向が一次独立であることに置き換えることができる．. ６６（）.

(8) . 、の収束条件いい制約無し最適化手法微分を用いない・… 訊の条件、，. １７３. ５‐３方向集合法を用いたアルゴリズムの収束性以下に具体的なアルゴリズムをとりあげ，その収束性を定理３に基づいて示す．アルゴリズム：軸方向探索法（図１））Ｄ；｛初期点燈１｝と方向集合Ｄ＝｛偽物 … ｅ｝の方向を座標軸方向としてェ：＝ＭＣＤ（ｄｌ，。，。与えて，点の移動がなくなるまで方向最小化手法を繰り返すことにより尤を求める｝，ｓｔｅｐｌｋ：＝１；｛ｋ：繰り返し回数｝）Ｄ；｛４（ｉ＝１，２，…，ｎヱ群．：＝ＭＤ（踏ｋ）ＥＤ。方向の最小化｝，）１ｔｅｐ３ｉｆｉ加盟．－雌ｋｓー＝ｏｔｈｅｎェ＊：ニズ盟，；ｅｎｄｏｆＭＣＤ）＝尤胤；ｋ：＝ｋ＋１としてｓｓｔｅｐ４ｄｋ十１ｔｅｐ２に戻る．，ｓｔｅｐ２. このアルゴリズムは，方向集合を常に座標方向にとっており各方向が互いに一次独立となる，．のため，本アルゴリズムにおいて，定理３の条件１）と２）を満足すれば最小点に収束する，．. 次のアルゴリズムはＤａｖｉｅｓ１９６４ｒｍ，Ｃａｍｐｅｙ法（）と呼ばれるアルゴリズムで，基本的に，Ｓｗａ. Ｒｏｓ１９６０）に線形探索法を組み合わせた方法と考えることができるこの手法はｅｎｂｒｏｃｋ法（．，在でも有力な手法の一つとして用いられている．. アルゴリズム：Ｄａｖｉｅｓ ‐Ｓｗａｒｍ‐Ｃａｍｐｅｙ法［４］（図２）＊１｝１｝と方向集合Ｄ昔ＭＤＳ：＝）＝｛〆Ｃ１ｌｄ≦ ） … … ｄｇ（ズ～，Ｄ剤；｛初期点ェ～）尤ｉ｝の方向を座標，，. 軸方向としてあたえて，点の移動がなくなるまで方向最小化手法を繰り返すことにより＊を求ヱめる．次の繰り返しで用いる方向集合は，方向最小化での移動ベクトルとそれに直交するｎ－１本のベクトルによって構成する．｝ｓｔｅｐｌ. ｋ：＝１；. ｛ｋ：繰り返し回数｝. ）Ｄ菩）ｋ））方向の最小化｝）；｛〆ｉ＝１，２，…，ｎ～（尤禦，：＝ＭＤ（ｄｋ）ＥＤ菩，ｔｅｐ３ｉｆｌｌ工豊．－ェｒ１＝ｏｔｈｅｎ工＊：＝工禦，；ｅｎｄｏｆＭＤＳＣｓｋ十１））としｔ４～＝ズ豊￥）－工ｒｄｓｅｐ，）上ｄｋ十１｝残りの方向をｄＦＩｉ≠ｊｆ（ｉ），（ｊ＝１， …，ｎ），ｓｔｅｐ２. Ｘ２. Ｘ２. 多彩ｘｌ図－. ＸＩ. 軸方向探索法. 図２６７（）. Ｄａｖｉｅｓ ‐ｓｗａｎｎ ‐Ｃａｍｐｅｙ法.

(9) . 金光秀雄. １７４. と定め，ｋ：＝ｋ十１としてｓｔｅｐ２に戻る．. このアルゴリズムでは，各方向はお互いに直交しており，定理３の条件１），２）を満足していれば，最小点に収束する．この二つのアルゴリズムは従来まで収束性が示されていなかった．ここでは方向集合のアルゴリ，ズムを一般化し，その収束条件を導くことにより，両手法の収束性を示した．また定理３の条件３）にあズムゴリを構成するアル方向集合法のつまり方向の独立性ということが非常に大切であり，たっては，方向の独立性を保存するようにしなければならない．. ６．. おわりに. 本論文で得られた結果を要約する‐ （１）正確な「直線探索法」の性質を明らかにした．２（）「直線探索法」を用いて「方向最小化手法」を構成し，その性質を明らかにした．）「方向集合法」を「方向最小化手法」を用いて構成し，この手法の収束条約を導びくとともに，（３線形凸計画問題に「方向集合法」を適用して解が得られるための条件を示した．４］が「方向集ｉｓｗａｍ‐Ｃａｍｐｅｙ法［ ‐ ｅｓ（４）従来収束性が示されていなかった軸方向探索法とＤａｖ合法」を用いたアルゴリズムであることを示し，両者のアルゴリズムの収束性を示した．今後の課題としては，）直線探索法を用いない手法の収束性を検討する．（１）「方向集合法」において，有限回の手続きで定義される直線探索法を用いたときの収束条件を（２検討する．（）「方向集合法」の収束の次数について検討する．３が考えられる．謝辞本研究を進めるにあたり，日頃よりご指導していただいている北海道大学. 新保勝教授，. 宮腰政明助教授，ならびに大変有益なご助言を頂いた北海道大学伊達惇教授に深く感謝致します．. 参考文献ｌｉｉｉｖａｔｉｅｗ．ＴｈｅＣｏｍＰｕｔｅｒ１ｏｕｍａｖｅｓａｒｅｖｉｍｉｉｏｎｗｉｔｈｏｕｔｅｖａｌｎｇｄｅｒｉｕａｔ，ｔＦ１ｚａｔｏｎｍｉｎｔｃｈｅｒｅ，Ｒ．：Ｆｕｎｃ），３３一４１８（１９６５. ［１］. ８）１９７［２］今野浩，山下浩：非線形計画法，日科技連（. ｌｖａｒｉｔｈｏｕｔｉａｂｌｅｓＷｉｔｉｍｕｎｏｎｏｆｓｅｖｅｒａｉｎｄｉｎｇｔｈｅｍｉｎｌｏｆｆｕｎｃｆｉｃｉｔｈｏｄｆｏｒｆｌｌｅｎｔｍｅ［３］Ｐｏｗｅ．Ｄ，：Ａｎｅｆ，Ｍ．Ｊ６２１５５柵１）ｌ７（１９６４ｈＣＪｉｖｅｓｉｖａｔｒｏｕｒｎａ，ｉａｔｎｇｄｅｒｃａｌｃｕｌ，，ＴｅｏｍＰｕｔｅｉｏｎｉｍｉｔｈｏｄｏｆＯＰｔｚａｔｉｔｓｅａｒｃｈｍｅ．ｌｏｐｍｅｎｔｏｆａｎｅｗｄｒｅｃ．Ｌｔｄ．Ｃ．１，ｔｏｎｔｈｅｄｅｖｅ，１［４］Ｓｗａｍ，Ｗ．Ｈ．：ＲｅＰｏｒ）ｈＮ１９６４Ｒｔ４／３（ｏｅ６ｌ工ｎｓｔＬａｂｏｒａｔｏｗｅｓｅａｒｃｔｍｍｅｎＣｅｎｔｒａ. ６８（）.

(10)