二乗和最適化のためのより高速な内点法【JST・京大機械翻訳】

Jiang Shunhua; Natura Bento; Weinstein Omri

プレプリント

J-GLOBAL ID：202202201093687990 整理番号：22P0291101

二乗和最適化のためのより高速な内点法【JST・京大機械翻訳】

A Faster Interior-Point Method for Sum-of-Squares Optimization

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

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

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

多項式最適化における中心ツールであり,Lasserre階層における凸プログラミングを捉える,二乗和(SOS)多項式を最適化するためのより速い内部点法を示した。p=Σ_iq ̄2_iは2dのn-変量SOS多項式である。L:=(n+d d)とU:=(n+2d 2d)によって,q_i’sとp_iが,それぞれ,時間O(LU ̄1.87)で実行されるベクトル空間の次元を,示した。これは最先端のSOSと半定値プログラミングソルバよりも多項式に速く,ランタイムO(L ̄0.5min{U ̄237,L ̄4.24})を達成した。提案アルゴリズムの中心ピースは,多項式補間基底の下でSOSバリア関数のHessianの逆数を維持するための動的データ構造であり,それは効率的に多変量SOS最適化に拡張して,要素ワイズ(Hadamard)製品の低ランク摂動にスペクトル近似を維持することを必要とする。これは,逆メインテナンスを用いた最近のIPMブレークスルーからの主な課題と逸脱であり,そこでは,スラックマトリックスへの低ランク更新が,Hessian行列に対して容易に同じを意味する。【JST・京大機械翻訳】

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

システム設計・解析 , 数値計算

前のページに戻る