水野研究室ブログ

研究者にとって，研究成果を論文として発表することが大事ですが，数多くの論文を書くだけではなく，オリジナリティが高く，学会等に貢献でき、多くの研究者に読んでもらえる論文を発表できることが，1つの目標でもあります．そのようなことを測る尺度の一つとして，発表した論文が他の文献（論文等）にどれだけ引用されているかを数えた被引用数があります．つまり，発表した論文がその後の研究にどれだけ役立っているかを示した数といえるでしょう．この数を調査し，論文の被引用数が多い研究者を発表しているところがあり、数学者については　ISI highly cited mathematicians list　を次のホームページで見ることができます：

http://hcr3.webofknowledge.com/browse_author.pl?page=0&link1=Browse&valueCategory=31&valueCountry=all&submitCategory.x=20&submitCategory.y=9

これをみると，最適化関係の研究者が思ったより多く数学者として掲載されているのがわかります．日本人も何人か掲載されています．

久しぶりの更新になります．

少し前のことになりますが，7月16日，17日と研究室で富士山に登ってきました．



研究室では３回目の富士登山になりますが，今回は宿泊組と夜行組の2コースに分かれました．宿泊組は富士宮ルートで登りましたので，そろって頂上まで登ることができましたが，夜行組は御殿場ルートをとり，これがかなりのハードコースであり，残念ながら全員とまではいきませんでしたが，元気のよい学生さんたちと頂上で合流できました．帰りは，温泉によって気分をリフレッシュしてきました．

参加した皆さん，ご苦労様でした．

　先日の東日本大震災で被災された方々にお見舞い申し上げます．

　ご存じのようにこの大震災において，次回のＲＡＭＰシンポジウムの
開催予定地であった東北大学，仙台市，およびその周辺地域は大きな被害を
受けました．開催予定の10月までに，会場，交通，宿泊施設，電力など
どこまで回復するかわからず，仙台市で開催するのは難しい状況です．

　そこで，次回のＲＡＭＰシンポジウムを

　　日程：2011年10月24日，25日　(変更なし)
　　会場：関西大学　千里山キャンパス・百周年記念ホール　
　　実行委員長：塩浦先生　（変更なし)

と変更することになりました．開催日と実行委員長には，変更がありません．

会場が変更になりましたが，多くの方にご参加いただければと思います．

昨年末に Klee-Minty's LP に関する論文の記事を書いたのですが，実はこの論文のアイディアを思いついたのは，ちょうどクリスマスの時で，それから１週間ほどでまとめあげ，年末に　OR Letters という論文誌に投稿しました．その結果，わづか２週間程の審査で受理され，このほど　Online で次のURL

http://dx.doi.org/10.1016/j.orl.2011.01.003

に公開されました．いままで，これほど迅速にすべてが進んだことはなく，今回のケースに少し驚いているというのが本音です．

第23回ＲＡＭＰシンポジウムは，次のように開催される予定です．

日程：2011年10月24日（月），25日（火）
場所：東北大学片平キャンパスさくらホール

セッションオーガナイザー
連続最適化　　　山下信雄（京都大）
離散最適化　　　岩田覚　（京都大）
企業セッション　猿渡康文（筑波大）
機械学習と最適化セッション　武田朗子（慶応大）

より詳しくは，http://www.orsj.or.jp/ramp/index.html　を参照して下さい．

多くの皆様のご参加をお待ち申し上げています．

　Klee-MintyのLP(線形計画問題)というのは，単体法で解くと指数回(2^m)の反復回数を必要とし，Dantzigの規則を使った単体法が多項式オーダの解法でないことを示す例題としてよく知られています．この問題は，行列(A)，定数(b),係数(C)のすべてに非常に大きな値を使っているため，複雑な問題と理解されています．

　今回，このKlee-MintyのLPを単純化することにより，定数(b)に 2^k といった値を使うが，その他は簡単な数(1と2)のみを使ったLPで，単体法が指数回の反復を必要とする問題が作れることがわかりました．さらに，この問題は，単体法の各反復で目的関数値が 1 づつ増加するという特徴を持っています．そして，この問題のもう一つ重要な性質として，すべての実行可能基底解の正の要素の最小値が 1 で，最大値が　2^m-1 であるということがわかりました．これにより，前回得た単体法の反復回数の上界に対して，今回は新しい下界が得られることが判明しました．

　より詳しくは，次のURL

http://www.me.titech.ac.jp/~mizu_lab/SimplexMethod/

に掲載されている論文を参照してください．

　　水野

　久しぶりの更新となりますが，報告させてもらいます．

　上海で１２月１０日から１３日まで開催された国際会議　ICOTA8　で招待講演(Plenary speech) をしてきました．北原君と最近得た単体法の結果を話したところ，Nemhauser教授,Anstreicher教授を始め，多くの研究者から「素晴らしい結果で，大変おもしろい」と絶賛していただくことができました．特に， Math. Pro.誌の編集長であるAnstreicher教授からは，「もしジョージ(単体法の開発者であるGeorge Dantzig のこと）がこの結果を聞いたなら，とても喜んだに違いない」，あるいは「この結果は，今後の線形計画問題の教科書には記述されるであろう，基本的で重要な結果である」といったコメントまでいただくことができました．



　その新しい結果というのは，単体法で生成される解の数の上界を得たもので，少し専門的な話になりますが，生成される解の数が

　　　　　　　　n m (gamma/delta)　log　(m gamma/delta)

以下になるというものです．ここで，n は標準形の線形計画問題の変数の数， m は等式制約の数， delta と gamma は，それぞれすべての実行可能基底解の正の要素の最小値と最大値を表しています．なお，単体法の各反復では，解が更新される場合と退化のため更新されない場合がありますので，生成される解の数と反復回数が必ずしも一致するわけではありません．非退化の場合には，一致します．

　線形計画問題の解法としては，単体法以外にも，内点法，楕円体法などがあります．単体法が歴史的に最も古く，実際の問題を解く上で効率的であり，わかりやすい解法であるために，最も知名度があり，よく使われています．しかし，楕円体法あるいは内点法によって解を得るまでに必要とされる反復回数がうまく評価されているのに対して，単体法の反復回数についてはほとんど評価が得られていませんでした．もし評価しようとすれば，すべての基底の数以下であるといった上界を得ることができるぐらいでした．

　単体法の反復回数が評価されてこなかった理由の一つに，Klee and Minty　が示した例題の存在があげられます．この例題は，単体法で解くと変数の数の指数乗　(2のn乗)　の反復回数を必要とします．したがって，単体法が楕円体法や内点法のように多項式オーダの解法になりうるかという疑問には，かなり否定的な結果があるということになり，単体法の反復回数の上界として，よい結果が得られるとはあまり考えられていなっかったということになります．しかし，Klee-Mintyの例題は，ごく小さな係数あるいは非常に大きな係数を使って表現された人工的な問題であり，現実にこのような問題が現れることは，ほとんどありません．

　今回の結果では，生成される解の数の評価に，すべての実行可能基底解の正の要素の最大値と最小値の比(gamma/delta)を使っています．もちろん，Klee-Mintyの例題のように，人工的な問題を作れば，この比はとても大きな値となりますので，反復回数の上界としてうまく機能しません．しかし，現実の線形計画問題では，この比の値がそれほど大きくならないケースが多くありますので，今回得た結果も重要な意味を持つと考えられます．とくに，ネットワーク問題あるいはマルコフ決定問題などの線形計画問題では，この比が小さな値でおさえらることがわかっていますので，今回の結果を使うと，簡単に解の数の上界を得ることができます．

　以上今回のICOTA8での発表とその内容を簡単に説明させてもらいました．このことについて，より興味がある場合には，次のURL

http://www.me.titech.ac.jp/~mizu_lab/SimplexMethod/

から，論文などを手に入れることもできますので，ご参照いただければと思います．

　　　　　　　　　　　　　　　　　水野　眞治

第22回RAMPシンポジウムの案内

日程: 平成22年10月28日（木），29日（金）
場所: 名古屋大学 豊田講堂 シンポジオンホール
　　　〒464-8601 名古屋市千種区不老町
　　　地下鉄名城線 名古屋大学駅 2番出口から徒歩3分

10月28日（木）
9:00 受け付け開始
9:20―9:30 開会挨拶
9:30―12:20
セッション1「離散構造とアルゴリズムの最先端」
オーガナイザ: 加藤 直樹（京都大学）
講演1「解の遷移可能性問題の計算複雑さ」伊藤 健洋（東北大学）
講演2「点素パス問題に対するアルゴリズム」小林 佑輔（東京大学）
講演3「構造物の組合せ剛性: 計数条件とグラフ分割」谷川 眞一（京都大学）

昼休み

13:50―16:50
セッション2「ハイパフォーマンスコンピューティング」
オーガナイザ: 張 紹良（名古屋大学）
講演1「大規模固有値問題と高性能計算」山本 有作（神戸大学）
講演2「自動チューニングの数理モデルと最適化」須田 礼仁（東京大学）
講演3「GPGPUによる大規模流体シミュレーションのスケーラビリティ」
　　　青木 尊之（東京工業大学）

懇親会

10月29日（金）
9:20―12:20
セッション3「連続最適化の挑戦」
オーガナイザ: 久野 誉人（筑波大学）
講演1「半正定値計画と面的縮小」脇 隼人（電気通信大学）
講演2「代数的対称性を利用した半正定値計画法の前処理」
　　　前原 貴憲，室田 一雄（東京大学）
講演3「無限次元変分解析の理論とオンラインアルゴリズムにおける応用例」
　　　関口 良行（東京海洋大学）
講演4「ステレオ画像計測に現れる非線形最適化問題とその大域的最適解の計算法」
　　　檀 寛成（関西大学）

昼休み

13:50―16:50
セッション4「工学における逆問題の周辺」
オーガナイザ: 松本 敏郎（名古屋大学）
講演1「実問題への逆解析の応用」天谷 賢治 (東京工業大学）
講演2「逆問題解析とこれを用いた能動型および受動型電気ポテンシャルCT法」
　　　久保 司郎（大阪大学），阪上 隆英 (神戸大学），井岡 誠司 (大阪大学）
講演3「多倍長計算による非適切問題の大規模高精度計算の実現に向けて」
　　　藤原 宏志（京都大学）
講演4「不連続線推定問題の囲い込み法に基づく数値解法について」
　　　大江 貴司（岡山理科大学）

第22回RAMPシンポジウムについてより詳しくは
http://www.orsj.or.jp/chubu/?p=629
をご覧下さい．

　線形計画問題の内点法に関する新しいテキストを4つ，「解析的中心と中心パス」，「線形計画問題の大きさLと内点法の反復回数」，「主内点法のアルゴリズム」，「主双対内点法のアルゴリズム」というタイトルで　http://www.me.titech.ac.jp/~mizu_lab/text/　に公開しました．
　ご意見・コメント・要望等ありましたら，掲示板　http://9301.teacup.com/optimization/bbs　の方に投稿して下さい．

　線形計画問題を解く内点法としてもっとも単純なアフィンスケーリング法のテキストを公開しました．このアルゴリズムは，Dikinが提案した方法であり，Karmarkarより前に開発さえていた．アルゴリズムとしては単純であるが，その収束性の証明は少し難しく，きちんと書かれている教科書はあまりない．今回のテキストでは，非退化の仮定のもとで，点列が最適解に収束することを証明している．