最適化セミナーのご案内

14.2 アルゴリズム一覧

 Numerical Optimizerは以下のようなアルゴリズムを備えています.見出しの解法名は,アルゴリズムを指定する際に用います.カッコ内の解法名は,標準出力にMETHODとして出力されるものです.

  • simplex:単体法(SIMPLEX)
    線形計画法の解法として古くから知られている方法です.大規模問題では内点法に速度的に劣りますが,可能基底解が求まり原理的に内点法/外点法よりも高精度です.
    整数変数を含む問題に対して指定すると,単体法を分枝限定法(Branch and bound method)という枠組のなかで繰り返し行って,最適性の保証のある整数解を求めます.大規模問題において基底解が必要な場合には,"cross:on"と指定して内点法からのクロスオーバーを用いるのが有利です.
  • dual_simplex:双対単体法(DUAL_SIMPLEX)
    (主)単体法が主実行可能な基底解をたどりながら最適解にたどり着くのに対し,双対単体法は双対実行可能な基底解をたどりながら最適解にたどり着きます.
    大規模な線形計画問題に対して,(主)単体法と比較して有利であることがあります.
  • asqp:有効制約法(ACTIVE_SET_QP)
    単体法と同様,古典的な凸二次計画問題の厳密解法です.1万変数以上の大規模問題では,一般に内点法(直線探索法(Line Search Method))に劣りますが,

    • 変数に比べて制約式の数が非常に少ない(1/10以下)場合
    • 目的関数のヘッセ行列が密行列である場合

    には内点法よりも高速かつ高精度です.また,整数計画法に対応しているので,整数変数が含まれている凸二次計画問題を解くことができます."cross:on"と指定することで内点法からのクロスオーバーを用いることができるので,大規模問題に対して高精度な解を求めることができます.

  • higher:線形計画問題専用内点法(HIGHER_ORDER)
    線形計画法に特化した内点法で,大規模な線形計画問題の解法としては最も高速です.単体法と違い,可能基底解は求まりません.
  • lipm:(新版)直線探索法(LINE_SEARCH_IPM)
  • lepm:直線探索外点法(LINE_SEARCH_EPM)
  • line:(旧版)直線探索内点法(LINE_SEARCH)
    一般の凸計画問題に適用可能な内点法・外点法です.問題が凸であることがわかっている場合には信頼領域法よりも高速です.幅広い範囲の問題に対して有効なのが内点法(lipm),外点法(lepm)は問題に対して比較的良い初期値が得られている場合に有効であることが示されています.旧版の内点法(line)は,以前のバージョンとの整合を取る場合にご利用ください(Ver.7以前の内点法lineとVer.8以降の内点法lipmでは,メリット関数の定義が若干異なっておりますので,新版と旧版では異なる結果を与える場合があります).
  • bfgs:準ニュートン法(BFGS_LINE_SEARCH)
    準ニュートン法によって二階微係数を求める内点法です.“bfgs”はヘッセ行列の近似行列を密行列として保持しますので,小規模(50~500変数以下)な非線形計画問題に適しています.
  • tipm:(新版)信頼領域内点法(TRUST_REGION_IPM)
  • tepm:信頼領域外点法(TRUST_REGION_EPM)
  • trust:(旧版)信頼領域法内点法(TRUST_REGION)
    大規模なものを含む一般の非線形計画問題に適用可能な内点法・外点法です.幅広い範囲の問題に対して有効なのが内点法(tipm),外点法(tepm)は問題に対して比較的良い初期値が得られている場合に有効であることが示されています.旧版の内点法(trust)は,以前のバージョンとの整合を取る場合にご利用ください(Ver.7以前の内点法trustとVer.8以降の内点法tipmでは,メリット関数の定義が若干異なっておりますので,新版と旧版では異なる結果を与える場合がございます).
  • lsqp:直線探索法に基づく逐次二次計画法(LINE_SEARCH_SQP)
    準ニュートン法によって二階微係数を求める逐次二次計画法です.小規模(50~100変数以下)な非線形計画問題に適しています.
    問題によっては直線探索内点法/外点法(lipm/lepm/line)よりも安定的により精度の良い解を導くことができます.
  • tsqp:信頼領域法に基づく逐次二次計画法(TRUST_REGION_SQP)
    二階微係数をそのまま用いる逐次二次計画法です.大規模なものを含む一般の非線形計画問題に適用可能な方法です.一般に内点法よりも低速ですが,問題によっては内点法よりも安定的に,より精度の良い解を導くことができます.
    変数の数よりも制約式数が多い場合には内点法/外点法(tipm/tepm/trust)よりも高速な場合があります.
  • slpsqp:逐次線形二次計画法(SLP-SQP)
    ペナルティ関数を用いない逐次線形二次計画法です.ある程度大規模なものを含む一般の非線形計画問題に適用可能です.大域的収束性を保証する原理が内点法/外点法(tipm/tepm/trust)や従来の逐次二次計画法(lsqp/tsqp)のものとは異なるため,他の方法で収束しない問題に対して有効な場合があります.また,制約式の勾配が小さい反復点にいる時,実行可能領域に接近するという仕組みが組み込まれていますので複雑な制約においても安定的な動作が期待できます.
  • lsdp:線形半正定値計画問題に対する主双対内点法
    線形の半正定値計画問題に対する主双対内点法です.目的関数・制約式に出現する項は線形である必要があります.内部でメリット関数の計算を行いません.
  • csdp:凸半正定値計画問題に対する主双対内点法
    目的関数が凸非線形関数で,制約が線形な半正定値計画問題に対する主双対内点法です.この類の問題は,線形半正定値計画問題で記述することができますが,そのまま扱った方が高速に求解できます.内部でメリット関数の計算を行う点がlsdpと異なります.
  • qnsdp:準ニュートン法を用いた非線形半正定値計画問題に対する主双対内点法
    目的関数・制約式に非線形項が出現する半正定値計画問題に対する主双対内点法です.メリット関数の降下を保証するために,準ニュートン法を利用しています.
  • lmsdp:Levenberg-Marquardt法を用いた非線形半正定値計画問題に対する主双対内点法
    目的関数・制約式に非線形項が出現する半正定値計画問題に対する主双対内点法です.メリット関数の降下を保証する為に,Levenberg-Marquardt法を利用しています.準ニュートン法に基づく方法(qnsdp)に比べて,規模の大きな問題を取り扱う事ができます.変数が少なく,行列次元が大きい問題の場合,信頼領域法に基づく方法(trsdp)より高速な場合があります.
  • trsdp:信頼領域法を用いた非線形半正定値計画問題に対する主双対内点法
    目的関数・制約式に非線形項が出現する半正定値計画問題に対する主双対内点法です.メリット関数の降下を保証するために,信頼領域法を利用しています.準ニュートン法に基づく方法(qnsdp)より規模の大きな問題を取り扱う事ができます.
  • wcsp:制約充足問題ソルバ(WCSP)
    京都大学「問題解決エンジン」グループの開発による制約充足問題に対するアルゴリズムです.必ずしも厳密解が求まるわけではありませんが,大規模な整数計画問題に対し,非常に高速に実行可能解(近似解)を求めることができます.
    整数変数のみを含み,かつすべての変数に上限と下限がある問題に対してのみ有効です.目的関数,制約式に重みを設定することができます.制約の重みには,ハード制約,セミハード制約,ソフト制約の三種類があります.
  • wcsplp:混合整数計画問題専用の制約充足問題ソルバ
    線形な混合整数計画問題を制約充足問題の枠組みで解くアルゴリズムです.このアルゴリズムでは,連続変数は適当な刻み幅をもつDiscreteVariableと解釈されます.wcsplpでは全ての制約式をハード制約として扱い,目的関数をソフト制約として扱います.
  • rcpsp:資源制約付きスケジューリング問題ソルバ(RCPSP)
    京都大学「問題解決エンジン」グループの開発による資源制約付きスケジューリング問題に対するアルゴリズムです.資源制約の下,決められた作業の開始・終了時刻を決定する問題の実行可能解を高速に求めることができます.rcpspの記述にあたっては問題をSIMPLEの特殊なクラスを用いて記述する必要があります.完了時刻の最小化問題と,納期遅れ最小化問題を扱うことができます.前者を扱う際にはソフト制約,後者を扱う際にはハード制約のみが使用できます.
  • global:大域的最適化アルゴリズム(GLOBAL)
    一般の非線形計画問題または,整数変数を含む非線形計画問題に対し,大域的な最適解を求めることができます.Numerical Optimizerが備えている他の非線形計画法アルゴリズム(bfgs, trust)では,局所的な最適解を出力する可能性があるのに対し,この解法は大域的な最適解を与えます.ただし,凸緩和法に基づく分枝限定法を行いますので,計算機資源を多く消費します.数十変数程度の小規模でかつ複雑な問題に適しています.本アルゴリズムの実行に際してはフルセット及びNumerical Optimizer/Globalが必要です.Numerical Optimizer/Globalは有償アドオンであり,別途購入が必要となります.
  • DFO:目的関数の数式表現が困難な問題に対するアルゴリズム
    目的関数について数式表現が困難あるいは微分に関する情報を用いることが出来ないような整数変数を含まない小規模な問題に有効な解法です.本アルゴリズムの実行に際してはフルセット及びNumerical Optimizer/DFOが必要です.Numerical Optimizer/DFOは有償アドオンであり,別途購入が必要となります.また,Numerical Optimizer/DFOのご利用方法に関しては「Numerical Optimizer/DFO利用ガイド」をご参照ください.

 Numerical Optimizerのアルゴリズムは,SIMPLEで記述される目的関数,制約で四則演算および以下の関数を用いて記述されたものをサポートします注1

+     -     /     *
sin   cos   tan   asin   acos   atan
sec   csc   cot   asec   acsc   acot
sinh  cosh  tanh  asinh  acosh  atanh
sech  coth  asech acsch  acoth
atan2 hypot erf   csch
exp   log   log10 pow    sqrt
ceil  floor fabs  fmod

 erf関数はバージョン9から導入された,ガウスの誤差関数です.

\[erf(x) \equiv \frac{2}{\sqrt{\pi}} \int_{0}^{x} e^{-t^{2}}dt, \quad x \in [-\infty, \infty]\]

  • iisDetect:実行不可能性要因行の特定アルゴリズム
    上記のアルゴリズムと異なり,本アルゴリズムは数理計画問題を解くためのものではありません.本アルゴリズムはNumerical Optimizerに与えられた問題が実行不可能と判定されたら,自動的に起動し,実行不可能性の原因となっている制約式の組(できるだけ式の少ないもの)を特定します.内部では単体法を繰り返し呼び出しています.iisは初期設定ではonになっています.

注1)使用するアルゴリズムによっては利用できない関数がございます.


 

 

上に戻る