We treat the so-called scenario approach, a popular probabilistic approximation method for robust minmax optimization problems via independent and identically distributed (i.i.d.) sampling from the uncertainty set, from various perspectives. The scenario approach is well studied in the important case of convex robust optimization problems, and here we examine how the phenomenon of concentration of measures affects the i.i.d. sampling aspect of the scenario approach in high dimensions and its relation with the optimal values. Moreover, we perform a detailed study of both the asymptotic behavior (consistency) and finite time behavior of the scenario approach in the more general setting of nonconvex minmax optimization problems. In the direction of the asymptotic behavior of the scenario approach, we present an obstruction to consistency that arises when the decision set is noncompact. In the direction of finite sample guarantees, we establish a general methodology for extracting "probably approximately correct"-type estimates for the finite sample behavior of the scenario approach for a large class of nonconvex problems.
引用
收藏
页码:1119 / 1143
页数:25
相关论文
共 15 条
[1]
[Anonymous], 1972, Fourier series and integrals. Probability and mathematical statistics
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Ben-Tal, A
Nemirovski, A
论文数: 0引用数: 0
h-index: 0
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Ben-Tal, A
Nemirovski, A
论文数: 0引用数: 0
h-index: 0
机构:Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Nemirovski, A
Roos, C
论文数: 0引用数: 0
h-index: 0
机构:Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Ben-Tal, A
Nemirovski, A
论文数: 0引用数: 0
h-index: 0
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Ben-Tal, A
Nemirovski, A
论文数: 0引用数: 0
h-index: 0
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Ben-Tal, A
Nemirovski, A
论文数: 0引用数: 0
h-index: 0
机构:Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Nemirovski, A
Roos, C
论文数: 0引用数: 0
h-index: 0
机构:Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
Ben-Tal, A
Nemirovski, A
论文数: 0引用数: 0
h-index: 0
机构:
Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel