Probability estimation via policy restrictions, convexification, and approximate sampling
Probability estimation via policy restrictions, convexification, and approximate sampling
复制标题
通过政策限制、凸化和近似抽样进行概率估计
DOI：
10.1007/s10107-022-01823-6
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Tawarmalani, Mohit
中科院分区：
文献类型：
--
作者：
Chandra, Ashish;Tawarmalani, Mohit
本文开发了各种优化技术来估计事件的概率，其中凸规划的最优值，满足一定的结构假设，超过给定的阈值。首先，我们将稳健对应物的仿射/多项式策略的搜索与MINLP中现有的松弛层次结构相关联（拉瑟尔在国际数学家大会论文集（ICM 2018），2019; Sherali和亚当斯在用于解决离散和连续非凸问题的重构线性化技术，Springer，柏林）。其次，我们利用最近的进展Dworkin等人。（在：Kaski，Corander（编辑）第十七届人工智能和统计国际会议论文集，机器学习研究论文集，PMLR，雷克雅未克，2014年），Gawrychowski等人。（在：ICALP，LIPICS，施洛斯达格斯图尔-莱布尼茨-Zentrum für Informatik，2018）和Rizzi和Tomescu（Inf Comput 267：135-144，2019）开发技术来近似计算来自伯努利分布的概率二进制随机变量属于一个特殊结构的集合。第三，我们使用凸化，强大的对手，和机会约束优化技术，以涵盖这样的集工会的事件集的兴趣。第四，我们将我们的技术应用于网络可靠性问题，该问题量化了导致网络利用率超过1的故障场景的概率。最后，我们提供了初步的计算评估，我们的技术对网络可靠性的测试实例。
This paper develops various optimization techniques to estimate probability of events where the optimal value of a convex program, satisfying certain structural assumptions, exceeds a given threshold. First, we relate the search of affine/polynomial policies for the robust counterpart to existing relaxation hierarchies in MINLP (Lasserre in Proceedings of the international congress of mathematicians (ICM 2018), 2019; Sherali and Adams in A reformulation–linearization technique for solving discrete and continuous nonconvex problems, Springer, Berlin). Second, we leverage recent advances in Dworkin et al. (in: Kaski, Corander (eds) Proceedings of the seventeenth international conference on artificial intelligence and statistics, Proceedings of machine learning research, PMLR, Reykjavik, 2014), Gawrychowski et al. (in: ICALP, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018) and Rizzi and Tomescu (Inf Comput 267:135–144, 2019) to develop techniques to approximately compute the probability binary random variables from Bernoulli distributions belong to a specially-structured union of sets. Third, we use convexification, robust counterpart, and chance-constrained optimization techniques to cover the event set of interest with such set unions. Fourth, we apply our techniques to the network reliability problem, which quantifies the probability of failure scenarios that cause network utilization to exceed one. Finally, we provide preliminary computational evaluation of our techniques on test instances for network reliability.
登录
查看更多内容
影响因子：
3.1
作者：
Shuo Han;Molei Tao;U. Topcu;H. Owhadi;R. Murray
通讯作者：
R. Murray
用于计数和随机生成背包解决方案的更快 FPTAS
DOI：
--
发表时间：
2014
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Romeo Rizzi;Alexandru I. Tomescu
通讯作者：
Alexandru I. Tomescu
更快的 FPTAS
DOI：
--
发表时间：
2018
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Paweł Gawrychowski;Liran Markin;Oren Weimann
通讯作者：
Oren Weimann
机会约束交流最优潮流：多项式混沌方法
影响因子：
6.6
作者：
T. Mühlpfordt;Line A. Roald;V. Hagenmeyer;T. Faulwasser;Sidhant Misra
通讯作者：
Sidhant Misra
DOI：
10.1007/978-3-030-29414-4_1
发表时间：
2018-01
期刊：
--
影响因子：
--
作者：
Benjamin Doerr
通讯作者：
Benjamin Doerr