TY - JOUR
T1 - A framework for solving chance-constrained linear matrix inequality programs
AU - Karimi, Roya
AU - Cheng, Jianqiang
AU - Lejeune, Miguel A.
N1 - Funding Information:
History: Accepted by Pascal Van Hentenryck, Area Editor for Modeling: Methods and Analysis. Funding: This research has been supported in part by the Bisgrove Scholars program (sponsored by Science Foundation Arizona). M. Lejeune acknowledges the support of the Office of Naval Research [Grant N000141712420]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2020.0982.
Publisher Copyright:
Copyright: © 2020 INFORMS
PY - 2021/6
Y1 - 2021/6
N2 - We propose a novel partial sample average approximation (PSAA) framework to solve the two main types of chance-constrained linear matrix inequality (CCLMI) problems: CCLMI with random technology matrix and CCLMI with random right-hand side. We propose a series of computationally tractable PSAA-based approximations for CCLMI problems, analyze their properties, and derive sufficient conditions that ensure convexity for the two most popular—normal and uniform—continuous distributions. We derive several semidefinite programming PSAA reformulations efficiently solved by off-the-shelf solvers and design a sequential convex approximation method for the PSAA formulations containing bilinear matrix inequalities. The proposed methods can be generalized to other continuous random variables whose cumulative distribution function can be easily computed. We carry out a comprehensive numerical study on three practical CCLMI problems: robust truss topology design, calibration, and robust control. The tests attest to the superiority of the PSAA reformulation and algorithmic framework over the scenario and sample average approximation methods. Summary of Contribution: In line with the mission and scope of IJOC, we study an important type of optimization problems, chance-constrained linear matrix inequality (CCLMI) problems, which require stochastic linear matrix inequality (LMI) constraints to be satisfied with high probability. To solve CCLMI problems, we propose a novel partial sample average approximation (PSAA) framework: (i) develop a series of computationally tractable PSAA-based approximations for CCLMI problems, (ii) analyze their properties, (iii) derive sufficient conditions ensuring convexity, and (iv) design a sequential convex approximation method. We evaluate our proposed method via a comprehensive numerical study on three practical CCLMI problems. The tests attest the superiority of the PSAA reformulation and algorithmic framework over standard benchmarks.
AB - We propose a novel partial sample average approximation (PSAA) framework to solve the two main types of chance-constrained linear matrix inequality (CCLMI) problems: CCLMI with random technology matrix and CCLMI with random right-hand side. We propose a series of computationally tractable PSAA-based approximations for CCLMI problems, analyze their properties, and derive sufficient conditions that ensure convexity for the two most popular—normal and uniform—continuous distributions. We derive several semidefinite programming PSAA reformulations efficiently solved by off-the-shelf solvers and design a sequential convex approximation method for the PSAA formulations containing bilinear matrix inequalities. The proposed methods can be generalized to other continuous random variables whose cumulative distribution function can be easily computed. We carry out a comprehensive numerical study on three practical CCLMI problems: robust truss topology design, calibration, and robust control. The tests attest to the superiority of the PSAA reformulation and algorithmic framework over the scenario and sample average approximation methods. Summary of Contribution: In line with the mission and scope of IJOC, we study an important type of optimization problems, chance-constrained linear matrix inequality (CCLMI) problems, which require stochastic linear matrix inequality (LMI) constraints to be satisfied with high probability. To solve CCLMI problems, we propose a novel partial sample average approximation (PSAA) framework: (i) develop a series of computationally tractable PSAA-based approximations for CCLMI problems, (ii) analyze their properties, (iii) derive sufficient conditions ensuring convexity, and (iv) design a sequential convex approximation method. We evaluate our proposed method via a comprehensive numerical study on three practical CCLMI problems. The tests attest the superiority of the PSAA reformulation and algorithmic framework over standard benchmarks.
KW - Chance-constrained programming
KW - Linear matrix inequalities
KW - Sampling-based approximation
KW - Semidefinite programming
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=85114686949&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85114686949&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2020.0982
DO - 10.1287/ijoc.2020.0982
M3 - Article
AN - SCOPUS:85114686949
VL - 33
SP - 1015
EP - 1036
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
SN - 1091-9856
IS - 3
ER -