Japanese | English

Kobe Studio Seminar for Studies with Renderman

ワークショップ: Optimization theory for Renderman users

幅広く使用されているPixar社のRendermanを活用する際のより良いshadingのアルゴリズムを考える,あるいは高速化に寄与する実装方法などを考えていくことは実践的な面から非常に重要です。その過程においては,実際に行われる数値計算に関して,様々な面からの知識を育むこともとても重要となってきます。本セミナーでは,九州大学IMIの脇先生を主たる講師としてお招きし,(CG分野を含めた幅広い応用のある)最適化理論の理解を育む,また,それをうまく活かせないかを議論したいと考えています。なお,今までのこのセミナーシリーズの流れを考慮し,数式処理から見た最適化理論の必要性なども,最適化の導入としての講演が設定されておりますので,幅広い専門分野の立場からの議論を期待しております。

本ページの最後に,主たる講師の脇先生からの最適化に関する説明を寄稿して頂いております。参加をご検討の方はぜひ一読をお願い致します。

日時:
2014/02/01
会場:
開催場所: 神戸大学大学院人間発達環境学研究科(六甲台地区の鶴甲第2キャンパス)
部屋:
A739およびA721
ワークショップ世話人:
桐生裕介 (Studio Phones), 脇隼人 (九州大学 マス・フォア・インダストリ研究所)
備考:
過去のセミナーシリーズは,Kobe Studio Seminar for Studies with Rendermanをご覧ください。
時間:
10:00-10:45
タイトル:
Optimization theory for Renderman users 1: Intro.1
登壇者:
桐生裕介 (Studio Phones)
時間:
10:45-11:30
タイトル:
Optimization theory for Renderman users 2: Intro.2
登壇者:
長坂耕作 (神戸大学)
時間:
11:30-12:00
ディスカッション:
デザインとvisulaizationと学術的交流の意義について
Moderator:
Kazuhisa Takemoto (Honda R&D Co.,Ltd. Motorcycle R&D Center)
時間:
12:00-13:30
タイトル:
昼休み
備考:

昼食は各自でお持ちください。食堂は開いていません。

時間:
13:30-14:30
タイトル:
Optimization theory for Renderman users 3: Basic
登壇者:
脇隼人 (九州大学 マス・フォア・インダストリ研究所)
概要:

TBA

時間:
15:00-16:00
タイトル:
Optimization theory for Renderman users 4: Advance
登壇者:
脇隼人 (九州大学 マス・フォア・インダストリ研究所)
概要:

TBA

時間:
16:30-
ディスカッション:
計算機科学の一般論と,実践的な技術について
Moderator:
長坂耕作 (神戸大学),脇隼人 (九州大学 マス・フォア・インダストリ研究所),桐生裕介 (Studio Phones)

最適化に関する脇先生によるご紹介

最適化とは

最適化は,産業だけでなく日常生活において生じる意思決定の場面によく現れ,“○○”という条件の下で“できるだけ□□を達成する”手段などを選ぶ際に用いられます。最近ではIBMが“ビジネス・アナリティクス・アンド・オプティマイゼーション”,すなわち,ビジネスにおける意思決定の場面では膨大なデータの分析と最適化が重要である,ということをさかんに提唱しています。このことからも最適化の重要性が認識できると思います。

最適化の例

理学や工学等のアカデミックな場面だけでなく,物流・ロジスティクス,スケジューリング,施設配置,ものつくりなどビジネスの場面で現れる意思決定から,数独の解を求めるといった様々な場面で最適化が利用されています。より具体的には,限られた輸送手段の中で,できるだけ効率よく品物を各拠点に配送する航空機乗務員の搭乗スケジュール強度が一定以上あってできるだけ軽い形状のものを作る授業の時間割の作成などがあげられます。

最適化理論とは

理論と聞くと役に立たなさそうに思う方もいるかもしれませんが,最適化理論は上であげた例で現れる最適化問題を効率よく解くための基礎となります。特に,最適化は解を求めるというゴールがあります。したがって,最適化理論は解の存在を保証するだけでなく,どのように計算すれば効率よく解が求められるか,といった解の構成法を与えることもあります。この構成法が解を求めるアルゴリズムと呼ばれるものです。例えば,最も基本的な最適化問題である線形計画問題は,最適解が多面体の頂点に存在します。線形計画問題に対する実用的なアルゴリズムである単体法が,これらの頂点を効率よくたどることで最適解を見つけます。また,整数計画問題は一般に効率的に最適解を求めることが困難であることが知られていますが,整数計画問題では線形計画問題を利用して最適解を求めます。実際,整数計画問題と線形計画問題が最適化問題として似ている,という性質を巧みに利用しています。このように,最適化理論は,最適化する上で必要不可欠な理論・技術なのです。

最適化と他分野の関係

最適化は様々な分野と関係しています。“効率よく”解を求めるアルゴリズムの基礎になるのが最適化理論ですが,与えられた最適化問題が効率よく解けるかどうかは,計算機科学でいうクラスPに属しているかそれともクラスNPに属しているか,ということに対応します。また,与えられた最適化問題が,頂点と辺で構成される数学的対象(グラフと呼ばれます)で記述できる場合は,グラフ理論を使って効率のよいアルゴリズムを構成できることがあります。一方,連続量を扱う最適化問題の場合は,最急降下法やニュートン法等が有効な場合があります。こういった計算でも基本的に行列・ベクトルの演算や分解が計算の構成単位になります。したがって,数値計算や数値解析がアルゴリズムの基礎になります。数値計算を利用すると誤差の影響で解が求められないこともあります。こういった場合は,数式処理の技術を利用することもあります。

他にも経済学やゲーム理論との関連があります。1975年 KoopmansとKantrovichが資源の最適配分でノーベル経済学賞を受賞していますが,これは線形計画問題を利用したものです。また,Markowitzも金融資産の投資モデルであるポートフォリオ選択において最適化理論を利用して1990年にノーベル経済学賞を受賞しています。線形計画問題の双対性は,ゲーム理論の二人ゼロ和ゲームと関連しています。(ここには,最適化理論の創始者であるG. Dantzigと,20世紀最高の科学者の一人であるJ. von Neumannとのエピソードがあります。) ナッシュ(ビューティフル・マインドという映画で有名です。)はゲーム理論で1994年にノーベル経済学賞を受賞しています。

また,近年注目されているビッグデータを利用した最適化もこれから重要視されるでしょう。その際,スパコンをはじめとする高性能計算技術(HPC)が必要になってきます。現在,最適化分野でもHPC技術を利用した研究が進んでいて,例えば,Facebook,twitterや交通ネットワークなどの超大規模なグラフを高速に探索する技術も開発されています。この技術は,2013年に開催されたSC13(http://sc13.supercomputing.org)のGreen Graph500(http://green.graph500.org)で,JST CRESTチーム(代表: 藤澤克樹(中央大))と協力して,2部門で世界一位になりました。詳細は,http://www.imi.kyushu-u.ac.jp/news/view/458http://www.graphcrest.jp/jp/news2013-11-b.htmlをご覧ください。最適化は実用的な観点から利用されるだけでなく,HPC等の最先端計算技術と組み合わせより現実的な問題を解決したり,他分野の理論の発展に貢献もしています。

九州大学 マス・フォア・インダストリ研究所の概要

九州大学 マス・フォア・インダストリ研究所(Institute of Mathematics for Industry, IMIと略)は,2011年4月に創設された多様な数学研究を基礎に置く産業数学の研究所です。マス・フォア・インダストリとは,純粋・応用数学を流動性・汎用性をもつ形に融合再編しつつ産業界からの要請に応えようとすることで生まれる,未来技術の創出基盤となる数学の新研究領域です。詳細は,http://www.imi.kyushu-u.ac.jpをご覧ください。

数学理論先進ソフトウェア開発室

IMIの部門の一つで,数学理論先進ソフトウェア開発室を開設しています。ここでは,主にIMIで発見された数学の理論や定理をアルゴリズム化し,さらにソフトウェアとして実装することを目的としています。また数学ソフトウェアの研究・開発の促進を目的としたセミナーやワークショップも不定期に開催しています。詳細につきましては,http://www.imi.kyushu-u.ac.jp/academic_staffs/department/36をご覧ください。

技術相談

IMIでは,産業界・諸科学との連携交流や技術相談なども行っています。産業技術に関する数理的問題に対するご相談を学内外に対して広く受けつています。ご相談がある場合は, techcons@imi.kyushu-u.ac.jp にご連絡ください。技術相談に関する詳細は,http://www.imi.kyushu-u.ac.jp/technical_consultationsをご覧ください。

プロフィール

2007年3月東京工業大学 大学院情報理工学研究科 数理・計算科学専攻で博士課程修了。電気通信大学電気通信学部助教を経て,2012年5月,九州大学 マス・フォア・インダストリ研究所 数学理論先進ソフトウェア開発室 准教授となり現在に至る。専門は,最適化,数理計画であり,特に連続最適化の研究や ソフトウェア開発に従事している。

最適化理論に関連する基本的な文献
  • 穴井宏和,“数理最適化の実践ガイド”,講談社,2013
  • 茨木俊秀,福島雅夫,“最適化の手法”,共立出版,1993
  • 福島雅夫,“新版 数理計画入門”,朝倉書店,2010
  • 藤澤克樹,梅谷俊治,“応用に役立つ50の最適化問題”, 朝倉書店,2009
  • A. Barvinok, “A Course in Convexity”, AMS, 2002
  • A. Ben-Tal and A. Nevirovski, “Lectures on Modern Convex Optimization”, SIAM, 2001
  • S. Boyd and L. Vandenberghe, “Convex Optimization”, Cambridge, 2004
  • D. Luenberger and Y. Ye, “Linear and Nonlinear Programming”, Springer, 2008
  • M. Ferris, O. Mangasarian and S. Wright, “Linear Programming with Matlab”, SIAM, 2007
  • J. Nocedal and S. Wright, “Numerical Optimization”, Springer, 2006
  • A. Schrijver, “Combinatorial Optimization - Polyhedra and Efficiency”, Springer, 2003
研究紹介

計算とソフトウェア化ということに主眼をおいて,最適化分野における理論の構築とソフトウェアの実装に取り組んでいる。特に,最適化分野において重要視されている半正定値計画問題や,それを含む錐最適化問題に関連する理論的な研究から応用・計算に関して研究している。今まで行った研究を簡単に紹介する。

  1. 多項式最適化問題に対する半正定値計画問題と疎構造の利用

    多項式最適化問題とは,多項式の等式・不等式で記述された集合の上で,多項式を最小化する最適化問題である。大域的な最小値を求めることは非常に難しく,多項式最適化問題はNP-困難な最適化問題であることが知られている。Lasserre(2001)が提案した半正定値計画問題を利用した求解法を改良することで,疎構造を持った多項式最適化問題に対しても半正定値計画問題を利用して効率よく計算できるようにした。また,この手法を実装したソフトウェア“SparsePOP”を共同で開発し公開している。

  2. 半正定値計画問題の応用の一つとして,センサーネットワークの位置同定問題

    これは,与えられたセンサー間の距離情報からセンサーの位置を推定する問題である。Biswas and Ye(2004)で提案された半正定値計画問題を利用した手法に対して,より効率よく計算できる様に疎構造を持った半正定値計画問題に定式化してセンサーの位置を推定する手法を提案した。この手法に基づいたソフトウェア“SFSDP”を共同で開発し公開している。

  3. 数値的に求解困難な半正定値計画と面的縮小法

    半正定値計画問題に対する解法として,主双対内点法が知られている。主双対内点法は,半正定値計画問題がある仮定を満たしている時には最適解に収束することが知られている。一方,仮定を満たさない場合は,求解が数値的に困難になり主双対内点法が最適解に近づく前に終了してしまうこともある。このように,仮定を満たさない半正定値計画問題は応用でも良く現れる。こういった場合,Borewin and Wolkowicz(1980)によって提案されている面的縮小法が有効であることが知られている。この事実に基づいて,多項式最適化問題のために提案されている様々な手法が面的縮小法と関係していることを示した。面的縮小法の実用化やソフトウェア化が今後の課題である。