バックナンバー ( 2009 Vol.2 ) 2009 年 5 月 28 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2009 Vol.2 ( 2009 年 5 月 28 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> NUOPT V11 の新機能 NUOPT/DFO のご紹介 ■ <トピック> Shift Scheduling Pro バージョンアップのお知らせ ■ <トピック> 数理計画用語集 用語追加 ■ <トピック> 出展・発表報告（日本 OR 学会 2009 年春季研究発表会） ■ <トピック> 数理計画法の誕生と発展（その 5） ■ <セミナー> NUOPT 無料セミナーのご案内 ■ < tips > SIMPLE よくある間違い（第 9 回） +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ***************************************************************** ■ <トピック> NUOPT V11 の新機能 NUOPT/DFO のご紹介 ***************************************************************** NUOPT V11 がリリースされて 2 ヶ月が経ちました．NUOPT V11 では様々な 新機能を提供しておりますが，ここではその中から NUOPT/DFO についてご 紹介します． NUOPT/DFO は数式では記述できないシステムに対して最適化計算を行うた めの有償アドオンとなります．ここで，名前にある DFO とは，derivative free optimization の略称で，関数の微分の情報を直接用いることなしに 最適化計算を行なう解法の総称となります．このため，シミュレーション などの分野での利用が考えられます． ところで，DFO に属する解法の研究に関して，制約条件がない問題に対す るものが中心となっていました．しかし，NUOPT/DFO では制約なしの問題 に対する手法にペナルティ関数の概念を導入することで制約条件がある問 題も扱えるようになっております． 今後もより多くの皆様がお持ちの問題に対応できるよう更なる機能拡張に 取り組んでまいります． （島田 直樹） ****************************************************************** ■ <トピック> Shift Scheduling Pro バージョンアップのお知らせ ****************************************************************** 現在大好評の Shift Scheduling Pro がユーザ様の声に応える形で，9 月 下旬バージョンアップ予定です．「バイトのシフトに対応」「複雑な制約 の記述に対応」「編集機能の増強」等さらに高機能化かつ使い易いものと なります．今後 Web 上で詳細情報をアップして行きます． 導入のご検討の際に試用版もございますので，ご興味のあるかたは是非と もお問い合わせください． < URL > http://www.msi.co.jp/nuopt/shift/shiftschedulingpro.html < e-mail > nuopt-info@ml.msi.co.jp （佐藤 誠） ***************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では，「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回の追加用語は，前回に引き続き数理計画部でやりとりしている最近の メールからホットな用語を抽出しています． 以下の用語を追加しております． ・BFGS ・サポート ・スケーリング ・近似解法 ・浮動小数点例外 ・ラグランジュ双対 ご興味がある用語がありましたら，是非ご一読いただければと思います． ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <トピック> 出展・発表報告（日本 OR 学会 2009 年春季研究発表会） ****************************************************************** 2009 年 3 月 17 日（火）・18 日（水）に日本オペレーションズ・リサー チ学会春季研究発表会が筑波大学にて行われました．弊社からは，下記の 3 件の発表を行いました． ・「数式表現によらない関数の制約付き最適化」 弊社研究員の島田 直樹が発表いたしました． 目的関数の微分の情報が使えないような無制約最小化問題に対し用いられ る手法の一種を制約付きの問題に拡張し，実装を行った報告をいたしまし た．なお，発表の中では数値実験の結果として構造最適化の分野での問題 に適用した例などをご紹介しました． ・「半正定値計画問題に対する内点法における逐次正定値判定の利用」 弊社研究員の原田 耕平が発表いたしました． 半正定値計画問題に対する内点法において，ステップサイズを計算する際 の計算上の工夫を紹介し，既存の方法との比較を行いました． ・「地理情報システムへの数理計画エンジンの組込開発－施設配置問題を 例として－」 私，多田 明功が発表いたしました． 施設配置問題に対し，地理情報システム上から，必要データ入力・NUOPT による求解・地理情報システム上への結果表示の一連の流れをシームレス 実行できるシステムを紹介いたしました．実際にデモンストレーションを 通じて，本システムのイメージを聴衆の皆様に掴んでいただきました． 最後になりますが，弊社の出展ブースに数多くの皆様がお立ち寄りいただ きましたこと，ここに感謝申し上げます． （多田 明功） ****************************************************************** ■ <トピック> 数理計画法の誕生と発展（その 5） ****************************************************************** 今回は「非線形計画法の確立 内点法と自動微分法」と題して非線形計画法 に関する歴史的な事情を振り返ります． 輸送，組み立て，混合，流量保存，裁断，対応関係，分割，グルーピング， など，線形な関係の組合せで表現できる事象は驚くほど多様です．それら 多様な事象に対して一次式という数学的に最も簡明な表現を与え，線形計 画法アルゴリズムの守備範囲に落とし込むことができるのが数理計画法の 大きな強みであるのは疑いのないところでしょう． しかしながら，状態方程式から導かれる圧力とエンタルピーの関係，交通 流の均衡，精密に測定された機器の特性値，異種の物体の混合に伴う物性 値の変化，マルコフ過程，微分方程式のパラメータ推定，最尤推定など， 非線形な関係によって記述される系の最適化に対するニーズも存在します． 古くから知られている方法として，最も基本的な非線形最適化問題である， 二次計画問題（目的関数が二次，制約式が線形）で非線形計画法を近似す ることを繰り返す，逐次二次計画法（Sequential Quadratic Programming: SQP）があります．二次計画問題は，有効制約法と呼ばれる単体法の拡張ア ルゴリズムを適用すれば解くことができます．有効制約法の動作原理は単 体法と同じ，不等式制約を有効（active）なものとそうでないものに分け， 有効な不等式制約を等式制約だと考えた部分空間の解の列を生成し，その 中から最適解を探します． 一方で，非線形最適化問題に対して書き下された KKT 条件そのものを非線 形方程式として解くというアプローチも古くより試みられていました．単 体法/有効制約法はどの不等式制約が active なのかという離散的な情報を 更新することで求解します．これは KKT 条件の一部である相補性条件: x(主変数) * z(双対変数) = 0 を特別扱いしていることになりますが，このアプローチでは特別扱いを排 して，特殊な構造をしている相補性条件もいわば「平等に」扱います． そのうち，相補性条件に，正のパラメータ mu を入れて， x(主変数) * z(双対変数) = mu と変形したのち x と z を 0 でない領域に拘束すれば，KKT 条件が与える 非線形方程式系の性質は飛躍的に安定することが知られました．これが非 線形計画法のための内点法です．非線形最適化問題に対する KKT 条件を直 接解いているので，解法の道具立てが簡便であること，線形計画法に対す る内点法の自然な拡張になっていることが特徴と言えます． 90 年代には KKT 条件に対する Newton 法と整合したメリット関数により 大域的な収束性を備えた内点法アルゴリズムが提案されました．実装も進 歩し，現在ではノート PC 上で数万変数の問題でも数分の計算時間で解く ことができるようになっています． しかし，非線形最適化問題が実務的に利用されるにはもう一つ乗り越えね ばならない壁がありました．非線形関数の表現は，定数行列のような簡素 な形を取らないということ，非線形最適化アルゴリズムの大部分が要求す る目的関数や制約式の微係数を計算するには少なからざる手間がかかる， ということです．このままでは，手で書き下せる小規模問題や，構造の簡 明な問題に用途が限られてしまいます．アルゴリズムのみが先行してしまっ ていたその状況に大きな進展を与えたのが，80 - 90 年代に確立された自 動微分という技術です． 長くなってしまいましたので次回は「非線形計画問題の表現技法 自動微分 法を中心に」と題して，非線形計画法のお話を継続します． （田辺 隆人） ****************************************************************** ■ <セミナー> NUOPT 無料セミナーのご案内 ****************************************************************** ---- [ NUOPT 無料セミナー 開催日程 ] ----------------------------- ※ NUOPT 無料紹介セミナー ・ 6 月 25 日（木） 13:30 ～ 16:30 体感しながら NUOPT 入門 ・ 7 月 22 日（水） 13:30 ～ 17:30 スケジューリング特集 ・ 7 月 23 日（木） 10:30 ～ 17:00 金融工学特集 ※ NUOPT 無料スキルアップセミナー ・ 6 月 24 日（水） 10:30 ～ 17:00 実戦に向けての NUOPT 演習 会場：（株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > ------------------------------------------------------------------ セミナー終了後個別相談も承っておりますので，お気軽にお声かけください． なお，セミナーの詳細につきましては下記 URL をご参照ください． ＜セミナー案内 URL＞ http://www.msi.co.jp/nuopt/seminar_nittei.html ＜告知＞ 上記ラインナップが 9 月以降パワーアップ致します．各セミナー内容につ いてさらに進化させる予定ですが，目玉は新セミナー「スキルアップセミ ナー"実践編"（タイトル仮）」です．実際の業務で要求される最適化スキ ルを惜しみなく紹介致します．詳細に付きましては 6 月中旬をメドに Web にて掲載致しますのでご興味がある方は奮って御参加ください． （佐藤 誠） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 9 回） ****************************************************************** このコーナーでは，SIMPLE の記述に関してお客様が陥りやすい間違いを紹 介していきます． 今回は前回に引き続き，SIMPLE の関数 ifelse についてご紹介します． 関数 ifelse は，領域によって定義が異なる関数を定義するためのもので す．前回はこの ifelse の意外な落とし穴についてご説明いたしましたが， 今回はこの ifelse の「正しい」活用法についてご説明いたします． 例えば，モデル内において以下のような関数を考えたいとします． f(x) = log(x + 1) （x >= 0 の場合） x （x <= 0 の場合） このような場合，関数 ifelse を用いると便利です．関数 ifelse を用い ると，関数 f が以下のようにモデル内に記述できます． ------------------------------------------------------------------ Expression f; f = ifelse(x >= 0,log(x + 1),x); ------------------------------------------------------------------ ただし ifelse を用いる際は注意点があります．NUOPT マニュアルにもあ るように ifelse の対象とする関数は「領域全体で連続かつ微分可能」で ある必要があります．上の例ですと，関数 f がこの条件を満たしている必 要があります． では，上記の関数 f が条件「領域全体で連続かつ微分可能」を満たしてい るかどうかを検証をしてみましょう．x = 0 以外では明らかなので x = 0 で検証を行えば十分です． まず「連続」ですが， x -> +0 の時 f(x) = log(x + 1) -> 0 x -> -0 の時 f(x) = x -> 0 より示せます． 次に「微分可能」を示すために f の微分を計算しましょう． x -> +0 の時 df(x) = 1/(x + 1) -> 1 x -> -0 の時 df(x) = 1 -> 1 となります．ここで df は f の微分です． したがって，f は条件を満たすことがいえます． いかがだったでしょうか．関数 ifelse は便利ですが，対象とする関数に ついてよく吟味する必要があります．もしも ifelse を使用したモデルが エラーに見舞われた際は，上記のように関数が「領域全体で連続かつ微分 可能」であるかどうかを検証することをお勧めします． （藤井 浩一） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に NUOPT に関するお問い合わせを頂いたことのある方，および本メール マガジンの配信を希望された方にお送りしています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください． 発行：株式会社 数理システム << NUOPT >> 担当 東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階 e-mail : nuopt-magazine@ml.msi.co.jp ==================================================================