日本オペレーションズ・リサーチ学会

最適化手法とアルゴリズム
研究部会

Seminars on Optimization Methods and Algorithms


開催履歴

第1回 研究会

日時:2021年7月30日(金)14時〜18時
会場:Zoom によるオンライン開催
参加方法:以下のフォームから参加登録していただきますと、ZOOM接続先情報をメールにて自動返信いたします。
参加登録フォームはこちら(受付終了しました)

講演 1

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

講演 2

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

第2回 研究会

日時:2021年9月27日(月)14時〜18時
会場:Zoom によるオンライン開催
参加方法:以下のフォームから参加登録していただきますと、ZOOM接続先情報をメールにて自動返信いたします。
参加登録・ZOOM接続先情報取得はこちらから(受付終了しました)

講演 1

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

講演 2

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

第3回 研究会

日時:2021年10月30日(土)14時〜18時
会場:Zoom によるオンライン開催
参加方法:以下のフォームから参加登録していただきますと、ZOOM接続先情報をメールにて自動返信いたします。
参加登録・ZOOM接続先情報取得はこちらから(受付終了しました)
 
講演 1

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

講演 2

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

第4回 研究会

日時:2022年1月7日(金)14時〜18時
会場:Zoom によるオンライン開催
参加方法:以下のフォームから参加登録していただきますと、ZOOM接続先情報をメールにて自動返信いたします。
参加登録・ZOOM接続先情報取得はこちらから(受付終了しました)

講演 1

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

講演 2

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

第5回 研究会

日時:2022年3月11日(金)14時〜18時
会場:Zoom によるオンライン開催
参加方法:以下のフォームから参加登録していただきますと、ZOOM接続先情報をメールにて自動返信いたします。
参加登録・ZOOM接続先情報取得はこちらから(受付終了しました)

講演 1

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

講演 2

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