最適化手法とアルゴリズム

研究部会

開催履歴

第1回 研究会

講演者：武流野・F ・ロウレンソ 氏（統計数理研究所）
講演題目：錐最適化におけるエラーバウンド：一から最近の結果まで
講演概要：
本発表で錐最適化におけるエラーバウンドとその背景を紹介する．
特に，どうしてエラーバウンドが必要か，どのようにエラーバウンドが使われいてるかなど，一から説明する．
モチベーションをしっかり説明してから，恭順錐や面縮小法とエラーバウンドの繋がりを紹介し，エラーバウンドの計算方法を簡単に述べる．
皆様のご興味に応じて，他の最近の結果も紹介する．例：恭順錐の幾何学，恭順錐ではない錐のエラーバウンドを求める方法，エラーバウンドとアルゴリズム解析の関係など．
関連するarxivの論文：1712.06221, 2008.12968, 2010.16391, 2011.07745, 2102.06359．

講演者：河瀬康志 氏（東京大学）
講演題目：不可分財の確率的公平割当
講演概要：
限られた資源や財を公平かつ効率的に割り当てるという問題は，基本的かつ重要な問題である． 近年，アルゴリズム的ゲーム理論の分野では，不可分な財の「よい」割当を求める手法について関心を集めている． 本発表では，期待効用の最小値を最大化する確率的割当を求める問題を扱い，各エージェントの効用関数が加法性，粗代替性，劣モジュラ性を満たす場合それぞれについて，多項式時間（近似）アルゴリズムを与える． また，無羨望制約を追加で満たす必要がある場合について，計算可能性を議論する．

第2回 研究会

講演者：黒木祐子 氏（東京大学）
講演題目：限られた観測に基づく組合せ最適腕識別問題
講演概要：
多腕バンディット問題とは，1930年代から議論されてきた古典的な逐次的意思決定モデルの一つである．近年，推薦システムやクラウドソーシングといった実応用を動機に，組合せバンディットとよばれるアームに組合せ構造を持つような設定が，機械学習分野で活発に研究されている．本発表ではリグレット最小化と最適腕識別問題などバンディット問題の基本設定を紹介した後，組合せ最適腕識別問題の最近の発展について紹介する．限られた観測しか得られない場合（全バンディット及び部分観測）に対するアルゴリズムの提案，及びそのサンプル数の上界と失敗確率に関する理論解析を与える．

講演者：伊藤健洋 氏（東北大学）
講演題目：組合せ遷移への招待
講演概要：
組合せ遷移とは，「状態空間上での遷り変り」を数理モデル化・解析する新しいアルゴリズム理論であり，その概念は，理論から応用まで多種多様な分野に現れる．例えば，スライディングブロックパズルでの駒の移動手順や，配電網におけるスイッチ構成の切替手順なども，組合せ遷移の視点から見ることができる．近年では，グラフにおける組合せ遷移問題が盛んに研究されており，計算容易性と困難性の解析が進められている．本講演では，組合せ遷移の基本事項を紹介しつつ，講演者らを中心とした科研費・学術変革領域研究(B) の「組合せ遷移」プロジェクトも紹介させて頂きたい．その後，時間が許す範囲で，具体的な研究事例も紹介したい．

第3回 研究会

講演者：中山舜民 氏（中央大学）
講演題目：スパース最適化問題に対する近接勾配法と近接DCアルゴリズム
講演概要：
スパース最適化問題の一つとして平滑な関数と非平滑な関数の和として表現されるような関数の最適化問題がある．非平滑な関数が凸関数である問題に対する方 法として，最急降下法に基づいた近接勾配法と、（準）ニュートン法に基づいたニュートン型近接勾配法が挙げられる．また，非平滑な関数が凸関数と凸関数の差で表されるDifference of Convex (DC)関数である問題に対しては近接DCアルゴリズムを適用することができる．本講演では講演者らの研究成果を交えながら，これらの方法について述べる．

講演者：岩政勇仁 氏（京都大学）
講演題目：2部マッチング問題の代数的拡張
講演概要：
最大2部マッチング問題や最大重み完全2部マッチング問題は，「多項式行列のランクを求める問題」や「多項式行列の行列式次数を求める問題」としてそれぞれ代数的に定式化できる．本講演では，上記の代数的定式化に端を発する二種類のランク計算問題（Edmonds 問題，非可換 Edmonds 問題）と行列式次数計算問題（重み付き Edmonds 問題，重み付き非可換 Edmonds 問題）について，講演者の研究成果も交えながら概説する．

第4回 研究会

講演者：劉田香 (Liu Tianxiang) 氏（東京工業大学）
講演題目：逐次DC関数近似法及びシステム同定への応用
講演概要：
機械学習や信号処理を含む様々な分野に特殊構造(スパース性や低ランク性など)を誘導するための複数の非凸非平滑正則化関数付き最適化問題がある.
本発表ではDifference of Convex (DC)という構造に基づいて, 効率的な逐次 DC関数近似法とその理論的保証を紹介する.
システム同定に頻繁に現れているHankel 構造がある問題への応用も紹介する.
関連するarxivの論文: 1710.05778, 1906.10396

講演者：白髪丈晴 氏（東京工業大学）
講演題目：動的グラフ上のランダムウォーク
講演概要：
ランダムウォーク(RW)は探索, サンプリング(積分), 分散計算など複数のアルゴリズム設計で威力を発揮する有用な確率モデルの一つである. 一方で, 時間とともに変化を繰り返すグラフ上のRW, 中でも頂点集合が変化するグラフ上におけるRWの性質について分かっていることは驚くほど少ない. 本発表では発表者らの近年の研究成果である「グラフの拡大する速さとRWの未訪問頂点数の理論的特徴づけ」について動的グラフ上RWの既存研究を通しながら紹介する.

第5回 研究会

講演者：山川雄也 氏（京都大学）
講演題目：非線形半正定値計画問題に対する点列最適性とその最適化手法について
講演概要：
非線形半正定値計画問題は，半正定値計画問題や非線形計画問題などを含む広いクラスの最適化問題であり，これまでに多くの最適化手法が提案されてきた．既存手法の主な目的は，Karush-Kuhn-Tucker条件（KKT条件）を満たす点（KKT点）を求めることである．KKT条件は，制約想定と呼ばれる条件の下で最適性の必要条件となり，多くの場合は特定の制約想定の下で最適化手法の収束性等が議論される．しかし，近年では点列最適性条件という制約想定を必要としない最適性条件やそのための最適化手法も研究されている．本講演では，これまでに提案された点列最適性条件やそれに関する最適化手法について講演者の研究成果も交えて紹介する．

講演者：大城泰平 氏（東京大学）
講演題目：線形マトロイドと数え上げ
講演概要：
いくつかの組合せ構造は，行列式を計算することでその数を効率的に数え上げることができる．全域木を数える行列木定理，有向全域木を数える有向行列木定理，有向非巡回グラフの点素S–Tパスを数えるLindström–Gessel–Viennot補題といった数え上げ公式がその代表例であり，他にもパフィアンな向きづけが与えられたグラフの完全マッチングの数え上げにも行列式が利用される．本講演では，これらの例を含む種々の数え上げ公式を線形マトロイド交叉・パリティ問題の観点から統一的に理解する試みについて，講演者らの成果を交えながら紹介する．

第6回研究会

講演者：相馬 輔 氏（Massachusetts Institute of Technology）
講演題目：作用素スケーリングの数理と最近の発展
講演概要：
作用素スケーリングは(Gurvits 2004)によって行列スケーリングの非可換版として導入された問題で，Edmonds問題やBrascamp-Lieb不等式への応用が近年見つかりつつある．本発表では，行列スケーリングの基礎から始め，Sinkhornアルゴリズム，凸最適化や二部マッチングとの関連，応用例などを解説する．その後，行列スケーリングの理論が作用素スケーリングへどのように拡張されるかを概観し，正定値多様体上の凸最適化や非可換ランクとの関連を紹介する．最後に，講演者が最近行った作用素スケーリングの拡張とshrunk subspaceに関する共同研究について紹介する．

講演者：佐藤 寛之 氏（京都大学）
講演題目：リーマン多様体上の共役勾配法の数理とその周辺
講演概要：
リーマン多様体上の最適化は機械学習や制御工学など幅広い分野に応用をもち，近年注目を集めている．これまでの研究でユークリッド空間上の最適化手法の多くがリーマン多様体上に拡張されているが，そうした拡張はしばしば個々の手法や多様体ごとに工夫を要する．本講演では，そうしたリーマン多様体上の最適化手法の概要を説明した後，最近の研究成果として，リーマン多様体上の非線形共役勾配法の一般的な枠組みについて議論する．また，その枠組みに属する具体的なアルゴリズムや，具体的な多様体への応用例についても紹介する．

第7回研究会

講演者：井床 利生 氏（IBM東京基礎研究所）
講演題目：量子計算機の実用化へ向けた最適化技術の応用
講演概要：
量子計算機は、近年の物理実装技術の進歩によって、計算機としての実用化への期待が俄かに高まってきている。とはいえ、ハードウェアからアプリケーション（アルゴリズム）まで量子計算の実現に必要な全ての階層が研究開発途上にある。本講演では、最適化技術が量子計算の様々な階層で課題解決のために応用されている研究例を、講演者らの研究成果に限らず幅広く紹介する。また、最適化問題の求解に量子計算機を利用する逆向きの応用についても簡単に紹介する。

講演者：包 含 氏（京都大学）
講演題目：機械学習と凸共役の交わり
講演概要：
凸共役は凸解析における重要な概念のひとつであり，最適化問題における双対構造を支えている．一方で，機械学習ではデータに適合するモデルを発見することが目標のひとつであるが，データと予測の近さを測られる際に用いられる一般的な距離尺度であるBregmanダイバージェンスは，凸共役と密接に関わっている．本講演では，近年注目されつつある様々な機械学習の問題に内在する凸共役の構造を紹介する．凸共役の構造に着目することで，教師あり学習，強化学習，最適輸送など，様々な問題を統一的に取り扱うことができる．まだ発展途上であるこの領域において，明らかになっている事実，依然未解決の課題を議論したい．
講演資料：こちらからご覧いただけます

第8回研究会

講演者：五十嵐 歩美 氏（東京大学）
講演題目：The Price of Justified Representation
講演概要：
複数候補者を選ぶ投票では、各投票者が是認するか否認するかの二択の判断を行う二分型投票（approval voting）がよく用いられる。近年、二分型投票における比例性の概念であるJustfied Representation（JR）公理に関する研究が非常に活発に行われている。JR公理とは、価値観の似た集団の意見を集団の大きさに応じて適切に反映するというものである。JR公理を満たす投票ルールは最低限の比例性を満たすものと考えられるが、そのようなルールは他の望ましい公理を満たすとは限らない。例えば、JR公理は社会効用を最大にする原則や選好の被覆度合いを最大にする原則と必ずしも相容れない。本研究では、JR公理を課すことでをこれらの原則にどのような影響を与えるかを理論的かつ実験的に評価する。

講演者：林 俊介 氏（法政大学）
講演題目：都市の集積経済と均衡解析モデル
講演概要：
多くの都市では中心部に商業施設などが集積する都心が形成され，その外周に住宅が立地する光景が見られる．また都市によっては都心以外に副都心が形成されることもある．こうした現象を説明する要因として指摘されるのが集積経済である．本発表では，この集積経済を定量的に分析するモデルの1つでもあるFujita-Ogawaモデルに焦点を当て，その理論的背景と最近の研究動向について連続最適化の立場より概説する．