SCENARIO APPROACH FOR MINMAX OPTIMIZATION WITH EMPHASIS ON THE NONCONVEX CASE: POSITIVE RESULTS AND CAVEATS

被引:8
作者
Assif, Mishal P. F. [1 ]
Chatterjee, Debasish [2 ]
Banavar, Ravi [2 ]
机构
[1] Univ Illinois, Dept Elect Engn, Urbana, IL 61801 USA
[2] Indian Inst Technol, Syst & Control Engn, Mumbai, Maharashtra, India
关键词
robust optimization; scenario approach; nonconvex programs; RANDOMIZED SOLUTIONS; ROBUST SOLUTIONS; UNCERTAIN;
D O I
10.1137/19M1271026
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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
  • [2] Random sampling of multivariate trigonometric polynomials
    Bass, RF
    Gröcheng, K
    [J]. SIAM JOURNAL ON MATHEMATICAL ANALYSIS, 2004, 36 (03) : 773 - 795
  • [3] Robust convex optimization
    Ben-Tal, A
    Nemirovski, A
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (04) : 769 - 805
  • [4] Robust solutions of uncertain quadratic and conic-quadratic problems
    Ben-Tal, A
    Nemirovski, A
    Roos, C
    [J]. SIAM JOURNAL ON OPTIMIZATION, 2002, 13 (02) : 535 - 560
  • [5] Robust solutions of uncertain linear programs
    Ben-Tal, A
    Nemirovski, A
    [J]. OPERATIONS RESEARCH LETTERS, 1999, 25 (01) : 1 - 13
  • [6] Uncertain convex programs: randomized solutions and confidence levels
    Calafiore, G
    Campi, MC
    [J]. MATHEMATICAL PROGRAMMING, 2005, 102 (01) : 25 - 46
  • [7] The scenario approach to robust control design
    Calafiore, Giuseppe C.
    Campi, Marco C.
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2006, 51 (05) : 742 - 753
  • [8] THE EXACT FEASIBILITY OF RANDOMIZED SOLUTIONS OF UNCERTAIN CONVEX PROGRAMS
    Campi, M. C.
    Garatti, S.
    [J]. SIAM JOURNAL ON OPTIMIZATION, 2008, 19 (03) : 1211 - 1230
  • [9] The scenario approach for systems and control design
    Campi, Marco C.
    Garatti, Simone
    Prandini, Maria
    [J]. ANNUAL REVIEWS IN CONTROL, 2009, 33 (02) : 149 - 157
  • [10] A General Scenario Theory for Nonconvex Optimization and Decision Making
    Campi, Marco Claudio
    Garatti, Simone
    Ramponi, Federico Alessandro
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2018, 63 (12) : 4067 - 4078