文献

J-GLOBAL ID：202002254721540443   整理番号：20A1273205

大域的に解く多項式最適化問題に対する走行交差不等式の影響について【JST・京大機械翻訳】

On the impact of running intersection inequalities for globally solving polynomial optimization problems

著者 (3件)： Del Pia Alberto (Department of Industrial and Systems Engineering and Wisconsin Institute for Discovery, University of Wisconsin-Madison, Madison, USA) ,  Khajavirad Aida (Department of Management Science and Information Systems, Rutgers School of Business, Rutgers-State University of New Jersey, New Brunswick, USA) ,  Sahinidis Nikolaos V. (Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, USA)
資料名： Mathematical Programming Computation  (Mathematical Programming Computation)
巻： 12  号： 2  ページ： 165-191  発行年： 2020年 
JST資料番号： W4714A  ISSN： 1867-2949  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ここでは,分解可能な再定式化が形式[数式:原文を参照],[数式:原文を参照]の多重線形方程式の収集を含む非凸問題の大域的最適化を考察した。ここでEは,少なくとも2つの基底集合における基数の部分集合を示す。重要な特殊ケースは,多線形および多項式最適化問題を含む。多重線形ポリトープは,上記の多線形方程式のシステムを満たす二値点zの集合の凸包である。最近,Del PiaとKhajavirradは,多重線形ポリトープに対するファセット定義不等式のファミリーである走行交差不等式を導入した。本論文では,このクラスの不等式に対する分離問題に取り組んだ。著者らは,最初に,実行交差不等式のサブクラスである分離花不等式がNP困難であることを証明した。続いて,固定度の多重線形ポリトープに対して,著者らは,実行交差不等式を分離するための効率的多項式時間アルゴリズムを考案し,分岐および縮小グローバルソルバBARONのあらゆるノードにおいて,提案した切断面生成方式を埋め込んだ。提案した方法の有効性を評価するために,2つのテストセットを検討した。ランダムに生成した多線形と4,および画像復元問題からのコンピュータビジョンインスタンスの結果から,ランニング交差カットはBARONの性能を大幅に改善し,ランダムテストセットでは50%,画像復元テストセットでは63%の平均CPU時間短縮をもたらした。Copyright Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  一次方程式 ,  *最適化 ,  *多項式 ,  *不等式 ,  *最適化問題 ,  多重化 ,  コンピュータビジョン ,  ファセット ,  定式化 ,  NP困難 ,  凸包 ,  画像復元
準シソーラス用語： 大域的最適化 ,  ポリトープ , 【Automatic Indexing@JST】

著者キーワード (6件)： 分枝切断 ,  多項式最適化 ,  走行交差不等式 ,  多重線形ポリトープ ,  分離アルゴリズム ,  混合整数非線形最適化

分類 (1件)： その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (4件)： 多項式 ,  最適化問題 ,  交差 ,  不等式