非凸最適化問題における最適性ギャップの境界推定：非線形安全クリティカルシステムへの応用
Bounding Optimality Gaps for Non-Convex Optimization Problems: Applications to Nonlinear Safety-Critical Systems
パーセンタイル最適化による非凸問題の解の最適性ギャップを確率的に評価する2つのアルゴリズムを提案し、非線形MPCに応用した。
著者: Prithvi Akella, Aaron D. Ames
分類: math.OC, cs.IT, cs.RO, cs.SY, eess.SY, math.IT
原文アブストラクト
Efficient methods to provide sub-optimal solutions to non-convex optimization problems with knowledge of the solution's sub-optimality would facilitate the widespread application of nonlinear optimal control algorithms. To that end, leveraging recent work in risk-aware verification, we provide two algorithms to (1) probabilistically bound the optimality gaps of solutions reported by novel percentile optimization techniques, and (2) probabilistically bound the maximum optimality gap reported by percentile approaches for repetitive applications, e.g. Model Predictive Control (MPC). Notably, our results work for a large class of optimization problems. We showcase the efficacy and repeatability of our results on a few, benchmark non-convex optimization problems and the utility of our results for controls in a Nonlinear MPC setting.
