東京工業大学情報理工学研究科 小島政和 第1回横幹連合コンファレンス 2005年11月25,26日 JA 長野県ビル

Slides:



Advertisements
Similar presentations
Absolute Orientation. Absolute Orientation の問題 二つの座標系の間における剛体 (rigid body) 変換を復元す る問題である。 例えば: 2 台のステレオカメラから得られた3次元情報の間の関 係を推定する問題。 2 台のステレオカメラから得られた3次元情報の間の関.
Advertisements

<最適化の概念> 最適化すべき問 題 数学モデル 変数,数式 数理計画法 定められた計算手 順を用いて解くた めの方法論.
2. 数値微分法. 数値微分が必要になる場合として、次の 2 つが考えられる。 関数が与えられていて、その微分を近似的に計算する。 (数値微分の精度が十分で、かつ、計算速度が数値微分の方が 早い場合など。) 離散的な点の上で離散的なデータしかわかっていない関数の微 分を近似的に計算する。(偏微分方程式の数値解を求めたい時.
1. 補間多項式 n 次の多項式 とは、単項式 の 線形結合の事である。 Definitions: ( 区間, 連続関数, abscissas (データ点、格子点、差分点), 多項 式 ) Theorem. (補間多項式の存在と一意性) 各 i = 0, …, n について、 をみたす、次数が高々 n.
遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
到着時刻と燃料消費量を同時に最適化する船速・航路計画
第6回 線形計画法の解法(4) 混合最小値問題 山梨大学.
有限差分法による 時間発展問題の解法の基礎
緩和+分解+調整による 分散協調問題解決 神戸大学大学院海事科学研究科 平山 勝敏.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
「基礎OR」/「OR演習」 第2回 10/06/2009 森戸 晋.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
組合せ最適化問題と厳密解法 最小木、ナップサック問題、ビンパッキング、巡回セールスマン問題 LPによる上界・下界 分枝限定法
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
2013/05/22 半導体露光装置と整数計画法 実務における適用事例の紹介 キヤノン株式会社 光学機器事業本部 第二技術推進室 深川容三.
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
組合せ最適化 輪講 第1回 ERATO研究員 川原 純.
Approximation of k-Set Cover by Semi-Local Optimization
Reed-Solomon 符号と擬似ランダム性
重力3体問題の数値積分Integration of 3-body encounter.
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
ベイズ的ロジスティックモデル に関する研究
「基礎OR」/「OR演習」 第3回 10/13/2009 森戸 晋.
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
第5回 双対問題 テキストp 内容 双対問題の導出 式を足しあわせる方法 Lagrange緩和 相補性条件 双対辞書
第 七 回 双対問題とその解法 山梨大学.
1章前半.
多項式最適化問題に対する2乗多項式緩和 東京工業大学 情報理工学研究科 数理・計算科学専攻 小島政和
半正定値計画問題に対する 行列補完理論の高速実装
Selfish Routing and the Price of Anarchy 第2回
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
第6章 カーネル法 修士2年 藤井 敬士.
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
Linear Relaxation for Hub Network Design Problems
サポートベクターマシン によるパターン認識
データ解析 静岡大学工学部 安藤和敏
応用社会システム計画 (第10回) ここで、学習すること 学籍番号: 氏名: ■これまでの講義内容の整理 ■計画問題の設定と手法
[IBIS2011 企画セッション プレビュー] 大規模最適化および リスク指向最適化の最新解法
正規分布における ベーテ近似の解析解と数値解 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
情報理工学系研究科 数理情報学専攻 数理第四研究室 博士三年 指導教員: 駒木 文保 准教授 鈴木 大慈 2008年8月14日
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
第3回 アルゴリズムと計算量 2019/2/24.
ルンゲクッタ法 となる微分方程式の解を数値的に解く方法.
スパースカット、SDP近似、整数ギャップ、距離埋め込み
半正定値計画を用いた 最大カット問題の .878 近似解法 ver. C.22
主成分分析 Principal Component Analysis PCA
Selfish Routing and the Price of Anarchy 4.3
A First Course in Combinatorial Optimization Chapter
遺伝的交叉を用いた 並列シミュレーテッドアニーリング 同志社大学工学部/大学院 廣安知之,三木光範,○小掠真貴
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
第4回 線形計画 2000年11月 第4回 線形計画.
移動図書館問題 移動施設のサービス停留点を最適配置する問題
公共経営研究科 「シミュレーション」森戸担当分 概要(12/02/05)
First Course in Combinatorial Optimization
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
東京大学大学院工学系研究科 計数工学専攻 松井知己
サポートベクターマシン Support Vector Machine SVM
サプライ・チェイン最適化について 研究者・実務家が知っておくべきこと
回帰分析(Regression Analysis)
土木計画学 第12回(1月14日) 計画における代替案の作成2 担当:榊原 弘之.
半正定値計画問題(SDP)の 工学的応用について
PI補償器の出力を時変係数とする 定常発振制御系の安定性解析
構造方程式ゼミナール 2012年11月14日-11月21日 構造方程式モデルの作成.
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

東京工業大学情報理工学研究科 小島政和 第1回横幹連合コンファレンス 2005年11月25,26日 JA 長野県ビル 多項式最適化問題と双対性 東京工業大学情報理工学研究科 小島政和 第1回横幹連合コンファレンス 2005年11月25,26日 JA 長野県ビル

目次 1. 多項式最適化問題 2. Lagrange緩和とLagrange双対問題 3. 2乗和多項式と一般化Lagrange双対問題 4. 数値例 5. おわりに

目次 1. 多項式最適化問題 2. Lagrange緩和とLagrange双対問題 3. 2乗和多項式と一般化Lagrange双対問題 4. 数値例 5. おわりに

多項式最適化問題(POP) ただし, は を変数とする多変数多項式

多項式最適化問題(POP) 例: n=3, m=2.

多項式最適化問題(POP) さまざまな問題が多項式計画問題として定式化 組合せ最適化問題を含む非凸型最適化問題に対する大域最適化の統一的な枠組みを提供する.

目次 1. 多項式最適化問題 2. Lagrange緩和とLagrange双対問題 3. 2乗和多項式と一般化Lagrange双対問題 4. 数値例 5. おわりに

固定された に対して,Lagrange緩和問題 POP: Lagrange 関数: 固定された に対して,Lagrange緩和問題 このとき, 証明 許容解, は許容解

POP: Lagrange 関数: 固定された に対して,Lagrange緩和問題 このとき, 最良のLagrange緩和問題=Lagrange双対問題 このとき, 一般には,双対ギャップ が存在する

POP: Lagrange 関数: Lagrange緩和: Lagrange双対問題: このとき, 双対ギャップ を0にしたい! 理想的な方法は,罰金関数

目次 1. 多項式最適化問題 2. Lagrange緩和とLagrange双対問題 3. 2乗和多項式と一般化Lagrange双対問題 4. 数値例 5. おわりに 罰金関数を2乗和多項式で近似する

2乗和多項式の集合: 例

2乗和多項式の集合: 一般化Lagrange関数 一般化Lagrange双対問題: 一般に (POPの最小値) POPの許容領域が有界 数値的に解くためには,2乗和多項式の次数を r に 制限して近似する必要がある.

次数r以下の2乗和多項式の集合: 例

次数r以下の2乗和多項式の集合: 一般化Lagrange双対問題(次数r以下) 一般に . 緩い条件の下で 半正定値計画問題として解ける.

目次 1. 多項式最適化問題 2. Lagrange緩和とLagrange双対問題 3. 2乗和多項式と一般化Lagrange双対問題 4. 数値例 5. おわりに

一般化されたRosenbrock関数の最小化 精度=(近似最適値ー最適値の下界値)/|最適値の下界値| 近似最適解と最適値の下解値 大域的最適解の精度保証 多項式の疎性を活用している!

目次 1. 多項式最適化問題 2. Lagrange緩和とLagrange双対問題 3. 2乗和多項式と一般化Lagrange双対問題 4. 数値例 5. おわりに

大域的最適化のための数値計算手法としては非常に強力. 発展途中段階 --- 課題 大規模半正定値計画問題を解く必要がある 多項式の疎性の有効利用 数値的な安定性 理論的には多項式半正定値計画問題 (多項式行列不等式)に拡張されている