数理解析研究所講究録 1981

新時代を担う最適化

モデル化手法と数値計算

京都大学数理解析研究所
2016 年 1 月

数理解析研究所講究録は，京都大学数理解析研究所の共同利用研究集会および共同研究の記録として 1964 年に刊行が開始されました．現在の共同利用共同研究拠点(2010 年発足) の前身である，全国共同利用研究所として当研究所が発足した翌年のことでしたが，以来半世紀，毎年数十巻を刊行し，2012 年には第 1800 巻が刊行されるに至りました．第 1 巻から第 1840 巻までに収録された論文数は 26,808 編総頁
数は 317,199 頁という膨大なものであり，最先端の数学数理科学分野の研究状況を伝えるのみならず，我が国の数学数理科学の発展の歴史を留める文献として，他に類例を見ない論文集となっています．

講究録の内容は当研究所のウェブサイトおよび京都大学の学術情報リポジトリにおいても公開され，年間の総アクセス数は 1,254,383 回 (2012 年度) を数えるなど，多数の方にご利用いただいています．

講究録の使用言語は論文著者の判断に任されていますが，結果的に日本語が多用されていることが特徴の一つとなっています．その結果，講究録は，数学数理科学の広い領域における最先端の専門知識に母国語でアクセスできるものとして，近年の英語化の流れの中で，重要な文献となりつつあります．

当研究所の共同利用事業に参加し講究録の論文を執筆していただいた多数の方々に対し，講究録を大きく成長させていただいたことを深く感謝いたしますとともに，これからも，当研究所の共同利用共同研究拠点としての活動にご参加いただき，講究録の発展にご協力いただけますよう心よりお願い申し上げます．

RIMS$K\hat{o}k\gamma\hat{u}roku$

1981

0ptimization for the new age.

$\cdot$modeling method and numerical calculation
August $31\sim$ September 1, 2015edited by Shunsuke Hayashi

January, 2016

Research lnstitute for Mathematical Sciences
Kyoto University, Kyoto, Japan
This is a report of research done at the Research Institute for Mathematical
Sciences, Kyoto University. The papers contained herein are in final form
and will not be submitted for publication elsewhere.

新時代を担う最適化 :モデル化手法と数値計算
optimization for the new age: modeling method and numerical calculation
RIMS 研究集会報告集
2015 年 8 月 31 日 $\sim 9$ 月 1 日

研究代表者

林俊介 (Shunsuke Hayashi)
目次

1. 電子ジャーナル購読計画の効率的な作成
阪大情報科学 (Osaka U.)

1
梅谷

俊治 (Shunji Umetani)

2. ラスタ表現された図形の詰込み問題に対する局所探索法
阪大情報科学 (Osaka U.)〃

5

村上祥平 (Shohei Murakami)

梅谷俊治 (Shunji Umetani)NTT データ数理システム (NTT DATA Math. Systems Inc.)
阪大情報科学 (Osaka U.)

中野雄介 (Yuusuke Nakano)

森田浩 (Hiroshi Morita)

3. 時空間ネットワークを用いた大都市近郊区間における最長経路探索 –27
名大工学 (Nagoya U.)’/

犬塚幹夫 (Mikio Inuzuka)

田地宏一 (Kouichi Taji)

4. 非負行列分解に対する前処理付き逐次射影法のノイズ頑強性
東工大社会理工学 (Tokyo Inst. Tech.)

水谷友彦 (Tomohiko Mizutani)

5. ワイヤレスネットワーク最適化問題に現れる Interference 写像の性質
神奈川大工 (Kanagawa U.)

進藤

45

$–51$

晋 (Susumu Shindoh)

6. 無制約最適化問題に対するメモリーレス修正 SR1 法の大域的収束性について –55
東京理大理学 (Tokyo U. Sci.)
中山
横浜国大国際社会科学 (Yokohama Nat. U.) 成島
東京理大理 (Tokyo U. Sci.)矢部

舜民 (Shummin Nakayama)
康史 (Yasushi Narushima)

博 (Hiroshi Yabe)

7. 価格競争におけるロバストナッシュ均衡問題について

66

横浜国大国際社会科学 (Yokohama Nat. U.) 成島 康史 (Yasushi Narushima)
横浜国大経営 (Yokohama Nat. U.)
平野 達也 (Tatsuya Hirano)

8. Power Cone Programming の弱双対定理
ステラリンク株式会社 (Stera Link, Co., Ltd.) 小崎$- i -$75
敏寛 (Toshihiro Kosaki)9. A DOUBLY NONNEGATIVE RELAXATION FOR MODULARITY DENSITYMAXIMIZATION
筑波大システム情報工学 (U. Tsukuba) 伊豆永 洋一 (Yoichi Izunaga)
東工大社会理工学 (Tokyo Inst. Tech.)松井 知己 (Tomomi Matsui)筑波大工 (U. Tsukuba)

山本

芳嗣 (Yoshitsugu Yamamoto)10. 実務で現れるスタッフスケジューリングに対する近似解法
東工大社会理工学 (Tokyo Inst. Tech.)(株) ディ $-\cdot$ エヌエー

廣瀬

84

—-98

貴也 (Takaya Hirose)

DeNA $Co., Ltd.)$ 鈴木 翔太 (Shota Suzuki)
日本ユニシス株式会社 (Nihon Unisys, Ltd.) 佐藤 悠介 (Yusuke Sato)(株) 三菱東京 UFJ 銀行 (Bank Tokyo-Mitsubishi UFJ, Ltd.)$($

東工大社会理工学 (Tokyo Inst. Tech.)

鈴木寛人 (Hiroto Suzuki)

中田

和秀 (Kazuhide Nakata)

1 1. ON THE COMPLEXITY OF THE STABLE MARRIAGE PROBLEM FOR
RESTRICTED INSTANCE CLASSES

117

筑波大システム情報工学 (U. Tsukuba)〃12.

五十嵐悠 ( $Yu$ Igarashi)

久野誉人 (Takahito Kuno)

佐野良夫 (Yoshio Sano)

シュティーフエル多様体上のニュートン法とその収束性解析
東京理大工 (Tokyo U. Sci.)
東京理大理 (Tokyo U. Sci.)

127

佐藤寛之 (Hiroyuki Sato)

相原研輔 (Kensuke Aihara)

13. A note on nonlinear semidefinite programming and the squared slack
variables technique
京大情報学 (Kyoto U.)

–

福田エレン

143

秀美

(Ellen Hidemi Fukuda)

東工大・情報理工学 (Tokyo Inst. Tech.)

Bruno Figueira Lourengo
福島 雅夫 (Masao Fukushima)

南山大理工 (Nanzan U.)

14. 平滑化法を用いたマルチリーダーフォロワーゲームの解法
京大情報学 (Kyoto U.)$|$〃149露口大介 (Daisuke Tsuyuguchi)

福田

エレン

秀美(Ellen Hidemi Fukuda)

京都情報大学院大 (Kyoto Coll. Grad. Studies Info.)
南山大・理工 (Nanzan U.)$- 11 -$

胡明 (Ming Hu)

福島

雅夫 (Masao Fukushima)

15. 半無限半正定値計画問題に対する主双対パス追跡法

158

東京理大工 (Tokyo U. Sci)

奥野貴之 (Takayuki Okuno)

南山大理工 (Nanzan U.)

福島雅夫 (Masao Fukushima)

16. 複数のボトルネックをもつ通勤時刻選択問題とその均衡解
東北大情報科学 (Tohoku U.)

林$-$iii

俊介 (Shunsuke Hayashi)

173