多面体ホモトピー法から生じる条件付き線形不等式系の全解列挙法
スポンサーリンク
概要
- 論文の詳細を見る
1995年に多面体ホモトピー法が提案されて以来,多項式方程式系の全根列挙問題に関する研究は飛躍的に発展してきた.多面体ホモトピー法はそれまでのホモトピー法に比べて計算量が少なく済むという素晴らしい性質を持つ反面,ホモトピー法に必要な"初期方程式系"を形成するために「条件付き線形不等式系に対する全解列挙」という新たな組合せ問題が生じてしまう.現在,多項式方程式系の全根列挙に必要な計算時間の約3分の1が,この組合せ問題を解くことに費されており,この部分の高速化が望まれている.本論文では,条件付き線形不等式系の全解列挙問題に対して,線形計画法の感度分析テクニック,双対理論を使ったアルゴリズムを提案する.また,本アルゴリズムに対して効率の良い並列計算処理が可能であり,並列計算機に実装した結果,今まで解けなかった規模の問題まで扱えるようになった.本アルゴリズムの必要とする計算機メモリーや計算時間などを既存の実験結果と比べることにより,その有効性を検証する.
- 社団法人日本オペレーションズ・リサーチ学会の論文
- 2002-03-01
著者
-
藤澤 克樹
中央大学
-
小島 政和
東京工業大学情報理工学研究科数理・計算科学専攻
-
藤沢 克樹
京都大学工学研究科
-
武田 朗子
東京工業大学
-
藤沢 克樹
中央大学
-
藤沢 克樹
京都大学
-
武田 朗子
東芝
-
小島 政和
東京工業大学
関連論文
- 大規模最短路問題に対する高速処理システム : メモリ階層構造の考慮とクラスタ&クラウド技術による高速化 (21世紀の数理計画 : アルゴリズムとモデリング)
- 特集にあたって(半正定値計画に対するソルバーと応用例)
- 2-G-2 重み付き対数行列式を持つ半正定値計画問題を解くSDPA(連続最適化(1))
- 2-F-14 大規模最短路問題に対するダイクストラ法の高速化(グラフ(2))
- 2-B-8 決定係数最大化ポートフォリオ選択に対する凸最適化アプローチ(連続最適化)
- 1-A-5 大規模最短路問題に対する高速処理システム : メモリ階層構造の考慮とクラスタ&クラウド技術による高速化(つくばOR学生発表(5))
- An algorithm for decomposition of matrix -algebras generated by symmetric matrices (21世紀の数理計画--最適化モデルとアルゴリズム--RIMS研究集会報告集)
- Solving Sparse Semidefinite Programs by Matrix Completion (Part II) (Mathematical Science of Optimization)
- Solving Sparse Semidefinite Programs by Matrix Completion (Part I) (Mathematical Science of Optimization)
- グリッドチャレンジテストベッドの構築と運用 : グリチャレテストベッドの作り方(HPC-3 : 大規模運用システム(1))
- 平成19年秋季研究発表会ルポ(情報の窓)
- "Bare Metal" Cloud: 実マシンを提供するクラウドサービス
- 2-D-14 最適化問題用オンライン・ソルバーの構築と自動選択機能の開発(非線形計画(3))
- 不確実な電力事業環境下における発電設備投資計画法
- 拡散過程の生存確率に対する半正定値計画を用いた数値計算手法
- 庁舎建築の企画・設計におけるコストプランニングシステムに関する研究(建築経済・住宅問題)
- 2-E-3 ロバスト最適化問題に対する確率的解法の精度評価(非線形最適化)
- 非線形最適化と変分不等式に関する国際会議(学術会合報告)
- 不確実性下での最適化 : ロバスト最適化を中心に(21世紀を最適化する女性たち)
- ニュートン法および準ニュートン法の区分的連続微分可能な方程式への拡張
- 不動点アルゴリズムの計算効率の改善
- SDPA project and new features of SDPA 7.1.0 (計算科学の基盤技術としての高速アルゴリズムとその周辺--RIMS研究集会)
- 2-D-6 半正定値計画による分子の電子構造計算(数理計画(1))
- 最適化ソフトウェアSDPA
- 半正定値計画に対する行列補完型主双対内点法の並列化(錘計画問題と相補正問題)
- 半正定値計画問題を解くソフトウェアのPCクラスタ上における並列実装(最適化(2))
- 第49回シンポジウムルポ(情報の窓)
- 半正定値計画法を用いた指定座屈荷重係数を有するトラスのトポロジー最適化
- 210 半正定値計画法を用いた重複固有値を有するトラスのトポロジー最適化問題
- 2033 半正定値計画法を用いた指定座屈荷重係数を有するトラスのトポロジー最適化(構造)
- 半正定値計画法を用いた構造最適設計 (最適化のための連続と離散数理)
- 20190 半正定値計画法を用いた重複固有振動数を有するトラスのトポロジー最適化
- 2019 半正定値計画法を用いた指定1次固有振動数を有するトラスのトポロジー最適化(構造)
- 建築生産分野における最適化(統合オペレーション)
- Successive Convex Relaxation Method applied to Nonlinear Programs
- Approximation of global optimal values of nonconvex programs using Successive Convex Relaxation Method (Continuous and Discrete Mathematics for Optimization)
- 線形計画問題に対する双対内点主シンプレックス法
- 最大カット問題に対するSemidefinite Programming緩和(数理計画(2))
- Semidefinite Programming Relaxation for Nonconvex Quadratic Programs(Discrete and Continuous Structures in Optimization)
- 非凸2次計画問題に対するSemidefinite Programming緩和(数理計画(1))
- 広域分散コンピューティング環境における数理計画ソフトウェアSDPA
- 半正定値計画問題に対する内点法ソフトウェアSDPA(SemiDefinite Programming Algorithm)
- 半正定値計画問題に対する内点法ソフトウェアSDPA (SemiDefinite Programming Algorithm) (最適化のための連続と離散数理)
- 半正定値計画問題(SDP)に対する主双対内点法の実装と工学的応用について
- 半正定値計画問題に対する主双対内点法における共役勾配法の実装 (特集「計算と最適化」)
- 単調な半正定値線形相補性問題に対する内点法における探索方向の存在に関する一考察(数理計画(3))
- 線形計画問題に対する主双対内点法と、その相補性問題へ拡張 : 1992年度Lanchester賞受賞の対象論文を中心として(Lanchester賞)
- 穏やかな非凸計画問題の凹2次不等式条件1本付き凸計画問題への帰着
- SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING(Network Design, Control and Optimization)
- ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関関係の分析
- High Performance Grid Computing for Optimization Problem (Mathematics and Algorithms of Optimization)
- 11022 ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関分析
- 繰り返し型建築工事におけるTOCを用いた工程計画に関する研究
- 建築プロジェクトにおける工事編成最適化 : 工事編成支援システムの提案
- 多面体ホモトピー法から生じる条件付き線形不等式系の全解列挙法
- ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
- 建築工事編成最適化システムの構築
- 建築生産情報の確定過程に関する研究
- 建築画像の消失点検出手法の開発とそれに基づく3次元建築モデルの再構成手法
- 8048 キャッシュフローを考慮した一般化資源制約付きプロジェクトスケージューリング問題に関する研究
- 8025 キャッシュフローを考慮した一般化資源制約付きプロジェクトスケジューリング問題に関する研究(建築経済・住宅問題)
- 半正定値計画問題での大規模線形方程式系に対する前処理付き共役勾配法 (最適化のための連続と離散数理)
- 最小楕円に基づく領域判別(SVMの周辺:One-Class SVMと領域判別)
- 2-A-15 アルゴリズムサイエンス分野における最適化ソフトウエアの実装方式(計算と最適化(3))
- 1-A-7 計算と最適化の新展開に向けて(計算と最適化(1))
- 8114 キャッシュフローを考慮した複数プロジェクトスケジューリング
- Moderate Nonconvexity = Convexity + Quadratic Concavity (Continuous and Discrete Mathematics for Optimization)
- Polynomial-Time Convergence of Predictor-Corrector Infeasible-Interior-Point Algorithms for Monotone SDLCP : Generalization and Inexact Approach
- Convergence Analysis of Some Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem
- Centers of Generalized Complementarity Problems
- 条件付き最小楕円と多クラス判別への応用(モデリングと最適化の理論)
- 2-G-3 条件付き最小楕円と多クラス判別への応用(判別・分類)
- Conditional Geometric Score に基づく線形判別モデル(SVM)
- 平成12年度秋季研究発表会ルポ
- Decomposition in Interior-Point Methods
- Some Applications of the Convex Property of Monotone Complementarity Problems
- 大きなステップ長を許す内点法 : 線形相補性問題の場合(数理計画)
- アフィン・スケーリング法に対するBigM法の適用(数理計画)
- 疎性を持っている多項式最適化問題に対する半正定値計画緩和(最適化数理の手法と実際)
- 平面上の凸包における最小ノルム点問題(計算幾何)
- A Combinatorial Problem Arising from Polyhedral Homotopies for Solving Polynomial Systems (Mathematical Science of Optimization)
- A Combinatorial Problem Arising from Polyhedral Homotopies for Solving Polynomial Systems
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
- Solving polynomial least square problems as polynomial semidefinite programs (数値最適化の理論と実際--RIMS研究集会報告集)
- 理論家にとっての数理モデル(モデリング-広い視野を求めて-)
- 疎な多項式計画問題に対する半正定値計画緩和 (決定理論と最適化アルゴリズム)
- 多項式最適化問題に対する半正定値計画緩和
- 多項式計画に対する線形化緩和とLagrange緩和 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
- A GENERAL FRAMEWORK FOR CONVEX RELAXATION OF POLYNOMIAL OPTIMIZATION PROBLEMS OVER CONES
- 錐上の多項式制約を持つ最適化問題に対する緩和手法 (最適化の数理とアルゴリズム)
- 半正定値計画問題に対するソフトウェアSDPAの広域並列計算システム (最適化の数理科学)
- 大規模最短路問題に対するダイクストラ法の高速化
- TD-1-1 目で見るグラフ分割アルゴリズム
- 2-A-6 最適化と計算に関する最新の傾向について(計算と最適化の新展開)
- 2-F-10 最速フローを用いた避難所の評価(最適化(2))
- 1-E-4 大規模グラフに対する幅優先探索の高速化(探索理論)
- 2-E-1 緊急避難計画に対する普遍的最速流の実験的解析(防災・減災)