A framework for solving chance-constrained linear matrix inequality programs

Roya Karimi, Jianqiang Cheng, Miguel A. Lejeune

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1015-1036
Number of pages22
JournalINFORMS Journal on Computing
Volume33
Issue number3
DOIs
StatePublished - Jun 2021
Externally publishedYes

Keywords

  • Chance-constrained programming
  • Linear matrix inequalities
  • Sampling-based approximation
  • Semidefinite programming
  • Stochastic programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A framework for solving chance-constrained linear matrix inequality programs'. Together they form a unique fingerprint.

Cite this