  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.
