Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
計算情報学研究室 (数理情報学第7研究室)紹介スライド
Search
Sponsored
·
Your Podcast. Everywhere. Effortlessly.
Share. Educate. Inspire. Entertain. You do you. We'll handle the rest.
→
Shinsaku Sakaue
April 30, 2022
Research
1.2k
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
計算情報学研究室 (数理情報学第7研究室)紹介スライド
Shinsaku Sakaue
April 30, 2022
Transcript
13 slides
計算情報学研究室 (数理情報学第7研究室) 岩田 覚 谷川 眞一 坂上晋作 大城泰平
計算手法を軸とした 分野横断型研究の展開 離散最適化 連続最適化 圧縮センシング 化学情報 機械学習 エネルギー システム 線形計算
情報通信 回路・プラント シミュレーション
離散最適化法 • 解き易い問題 (最大流問題,最小木問題) アルゴリズムの高速化 一般的な枠組 • 解き難い問題 (巡回セールスマン問題) 近似アルゴリズム
メタヒューリスティック 厳密解法 (分枝限定法,切除平面法) 劣モジュラ関数
劣モジュラ関数 • ネットワークのカット容量関数 • 行列の階数関数 • 多元情報源のエントロピー関数 ) ( )
( ) ( ) ( Y X f Y X f Y f X f È + Ç ³ + V Y X Í " , V X Y R 2 : ® V f : V 有限集合
一般化固有値計算による 大域最適化手法 5 楕円体間の符号付き距離 非凸最適化問題として定式化 極値 (KKT) 条件の導出 ⇒2変数固有値問題への帰着 ⇒一般化固有値問題による解法
非凸2次計画問題への拡張
None
組合せ的計算幾何学 • 幾何的対象に対する計算問題を解くためのアルゴリズム基盤 – 動作計画 – 幾何的情報システム – 幾何学的モデリング(CAD) •
目標:幾何的対象に背後に潜む組合せ構造を解明したい → 効率的アルゴリズムの設計 goal
幾何的グラフ理論 • グラフの埋め込みや剛性 – センサーネットワーク位置同定, タンパク質の挙動解析, 結晶構 造の同定, ロボット制御 •
幾何的特徴を有するグラフの特徴づけ • 連続最適化問題(半正定値計画問題など)と組合せ最適化
データ構造を用いた最適化手法 9 • 実行可能解の集合をデータ構造を用いて表現 • データ構造上の操作で様々な実問題にアプローチ ネットワークルーティング 混雑ゲームの均衡解析 s t
1 2 3 4 5 1 Root r 2 3 3 4 5 ⊥
微分可能な最適化手法 10 乱択化や正則化により計算手続きを平滑化 微分計算により,最適化問題のパラメータの変化が及ぼす アルゴリズムの出力への影響を調べ活用する. max softmax 問題のパラメータの end-to-end 予測
感度分析 v1 v2 v3 t1 t2 t3 v1 v2 v3 t1 t2 t3 v1 v2 v3 t1 t2 t3 混雑ゲームの シュタッケルベルグ 均衡の計算
代数計算と組合せ最適化 11 0 2 0 0 1 3 0 1
3 ' 行列の階数 ≦ 二部グラフのマッチングの最大サイズ (Edmonds 1967) 行列要素の零・非零情報から二部グラフを作る
代数計算と組合せ最適化 12 • 等号が成立するケースの研究, 他の離散構造への拡張 → 数え上げ手法へ応用 • 行列要素の非可換への拡張 →
線形微分・差分方程式系の解析へ応用 • 行列(線形方程式)から非線形方程式への拡張 → 動的システムのシミュレーション手法へ応用 𝐹! = 𝐹!"# + 𝐹!"$ 𝐴(𝑡) d𝑥 d𝑡 𝑡 + 𝐵(𝑡)𝑥 𝑡 = 𝑓(𝑡)
数理情報学第7研究室 http://www.opt.mist.i.u-tokyo.ac.jp 知性に裏付けられた楽観主義 合理性(最適性)の追求
More Decks by Shinsaku Sakaue
See All by Shinsaku Sakaue
逆最適化と機械学習
ssakaue
3
810
データ駆動型アルゴリズム設計
ssakaue
1
540
Online Inverse Linear Optimization
ssakaue
2
360
ウォームスタートの学習による L 凸関数最小化の高速化
ssakaue
0
250
Online Structured Prediction with Fenchel–Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss
ssakaue
0
310
学習理論に基づく離散最適化アルゴリズムの改良と解析
ssakaue
0
950
計算情報学研究室 (数理情報学第7研究室)紹介スライド
ssakaue
0
490
Other Decks in Research
See All in Research
J-STAGEの現況と全文XML登載必須化について
xspa2012
0
420
完全自律LLMエージェントでDIVER OSINT CTF 2026に挑戦してみた
analokmaus
0
830
Evaluation génomique des femelles laitières croisées : comprendre la méthode pour accompagner les éleveurs à son utilisation
institutdelelevage
PRO
0
230
Méthane 2030 : Développer des solutions de réduction des émissions de méthane entérique : 1ers résultats
institutdelelevage
PRO
0
130
横浜市長(山中氏)の言動にかかる第三者による調査報告書
sishi2026
0
680
ros2-perf-multihost: 分散システムにおける客観的なアーキテクチャ評価フレームワーク
takasehideki
0
350
Pesée et pointage par imagerie 3D : PHENO3D entre en phase de test terrains
institutdelelevage
PRO
0
160
Paris et Berlin face à un monde sans repères. Entre convergences et divergences en matière de politique étrangère
ifri
0
120
最先端NLP勉強会2026 論文紹介:Reasoning with Sampling: Your Base Model is Smarter Than You Think (ICLR 2026 paper)
kogoro
4
980
Work in progress: How have changes in the labour market over the past decade affected attitudes to work?
resolutionfoundation
0
390
MIRU2026 チュートリアル講演2:三次元データ処理の動向
nnchiba
8
5.6k
CDCL を用いた MILP の厳密解法
imai448
0
330
Featured
See All Featured
Marketing to machines
jonoalderson
1
6k
Rails Girls Zürich Keynote
gr2m
96
14k
[Rails World 2026] Durable orchestration on Rails: from continuation to workflow
palkan
4
1.3k
How to Ace a Technical Interview
jacobian
280
24k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
12
2k
Building Experiences: Design Systems, User Experience, and Full Site Editing
marktimemedia
1
670
JAMstack: Web Apps at Ludicrous Speed - All Things Open 2022
reverentgeek
1
680
Statistics for Hackers
jakevdp
799
230k
The Language of Interfaces
destraynor
162
27k
The Spectacular Lies of Maps
axbom
PRO
1
1.1k
BBQ
matthewcrist
90
10k
The Organizational Zoo: Understanding Human Behavior Agility Through Metaphoric Constructive Conversations (based on the works of Arthur Shelley, Ph.D)
kimpetersen
PRO
0
540