多項式最適化問題の表現におけるスパース性と構造を活用するための効率的なデータ構造:SOSTOOLSにおける実装【JST・京大機械翻訳】

Jagt Declan; Shivakumar Sachin; Seiler Peter; Peet Matthew

プレプリント

J-GLOBAL ID：202202213800430982 整理番号：22P0298560

多項式最適化問題の表現におけるスパース性と構造を活用するための効率的なデータ構造:SOSTOOLSにおける実装【JST・京大機械翻訳】

Efficient Data Structures for Exploiting Sparsity and Structure in Representation of Polynomial Optimization Problems: Implementation in SOSTOOLS

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年03月03日プレプリントサーバーでの情報更新日： 2022年09月02日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

平方和(SOS)プログラムの構文解析における多項式変数の表現のための新しいデータ構造を提示した。SOSプログラムでは,変数s(x;Q)は独立変数xの多項式であるが,決定変数Qでは線形である。しかし,現在のSOSパーサは多項式変数の半線形構造を利用することができず,それらの表現における独立変数として決定変数を処理する。これは,多項式変数の貯蔵と操作における不必要なオーバヘッドをもたらし,大規模最適化問題に対処することから,パーザを禁止する。この計算オーバヘッドを除去するために,決定変数においてアフィンである多項式変数,”dpvar”構造の新しい表現を導入した。著者らは,dpvar表現における変数に関する操作の複雑性が,決定変数の数によって好ましいことを示した。さらに,多項式変数を保存するために必要なメモリは,特にMATLABスパース保存構造を利用するとき,dpvar構造を用いて相対的に小さいことを示した。最後に,著者らは,Dpvarデータ構造をSOSTOLS4.00に組み込み,いくつかの多項式最適化問題に対するパーザの性能を試験した。【JST・京大機械翻訳】

, , , , , , , ,
, , , , , , , , 【Automatic Indexing@JST】

システム・制御理論一般 , グラフ理論基礎

, , , , , ,

前のページに戻る