Data-driven tuning for chance constrained optimization: analysis and extensions

Abstract

Many optimization problems involve uncertain parameters which, if not appropriately accounted for, can cause solution infeasiblity. In this work, we consider joint chance-constrained optimization problems, which require all constraints to hold with a given probability, and a two-step solution method based on iterative tuning. Previous work established an a priori feasibility guarantee for this tuning approach, which relies on an assumption that must be verified on a case-by-case basis. In this paper, we propose an empirical methodology using statistical hypothesis testing to assess the validity of this assumption, thus providing further insight into the validity of the a priori guarantee. In addition, we provide sample complexity results to assess the requisite amount of data for the tuning method. We find that for large scale optimization problems, the tuning approach may require significantly less samples than the scenario approach. We numerically assess these results via application to the optimal power flow problem as well as further assess the scalability of the method and the optimality and feasibility of solutions obtained from tuning.

A Case study comparison formulations

1.1 A.1 Scenario approach

The scenario approach (Campi et al. 2009; Calafiore and Campi 2006) is a common approach used to solve chance-constrained problems. While it requires no assumptions on the underlying distribution of the uncertainty $\xi$, it relies on the availability of uncertainty samples or scenarios $\Xi _\text {SA} = \{ \xi ^{(1)}, \dots , \xi ^{(N_\text {SA})} \}$ to transform probabilistic constraints into deterministic constraints. The JCCP is reformulated by enforcing that the chance constraint must hold for all uncertainty samples, that is

$$\begin{aligned}&\min _{x} \sum _{i \in {\mathcal {N}}} c_{2, i} x_i^2 + c_{1,i} x_i + c_{0,i} \end{aligned}$$

(34a)

$$\begin{aligned}&\text {s.t.} \sum _{i \in {\mathcal {N}}} x_i - d_i = 0, \end{aligned}$$

(34b)

$$\begin{aligned}&{\Omega} _\xi ^{(k)} := \sum _{i \in {\mathcal {N}}} \xi _i^{(k)}, ~\forall k\in [N_\text {SA}] \end{aligned}$$

(34c)

$$\begin{aligned}&x_i - \alpha _i {\Omega} _\xi ^{(k)} \le p_{G,i}^{\max }, ~~\forall i \in {\mathcal {N}},~k\in \Xi _\text {SA} \end{aligned}$$

(34d)

$$\begin{aligned}&x_i - \alpha _i {\Omega} _\xi ^{(k)} \ge p_{G,i}^{\min }, ~~\forall i \in {\mathcal {N}},~k\in \Xi _\text {SA} \end{aligned}$$

(34e)

$$\begin{aligned}&{M}_{(ij,\cdot )}(x - \alpha {\Omega} _\xi ^{(k)} + \xi ^{(k)} - d) \le p_{ij}^{\max }, ~\forall ij \in {\mathcal {L}},~k\in \Xi _\text {SA} \end{aligned}$$

(34f)

$$\begin{aligned}&{M}_{(ij,\cdot )}(x - \alpha {\Omega} _\xi ^{(k)} + \xi ^{(k)} - d) \ge p_{ij}^{\min }, \forall ij \in {\mathcal {L}},~k\in \Xi _\text{SA}. \end{aligned}$$

(34g)

Here, the objective function and nodal balance constraint remain the same as in the deterministic problem. Constraint (34c) defines ${\Omega} _{\xi }^{(k)}$ as the total uncertainty summed across all nodes ${\mathcal {N}}$ for sample draw $k \in [N_{\text {SA}}]$. Constraints (34d)–(34g) enforce the generator and line constraints for each uncertainty realization.

1.2 A.2 CVaR inner approximation

The CVaR reformulation (Nemirovski and Shapiro 2007) is a conservative (inner) convex approximation of the JCCP. To solve the CVaR reformulation, we use the sample average approximation approach (Wang and Ahmed 2008), using an available sample set $\Xi _{\text {CVaR}} = \{ \xi ^{(1)}, \dots , \xi ^{(N)} \}$ to solve the following deterministic approximate problem:

$$\begin{aligned}&\min _{\begin{array}{c} x, \beta \le 0, s \end{array}} \sum _{i \in {\mathcal {N}}} c_{2,i} x_i^2 + c_{1,i} x_i + c_{0,i} \end{aligned}$$

(35a)

$$\begin{aligned}&\text {s.t.} \sum _{i \in {\mathcal {N}}} x_i - d_i = 0 \end{aligned}$$

(35b)

$$\begin{aligned}&{\Omega} _\xi ^{(k)} = \sum _{i \in {\mathcal {N}}} \xi _i^{(k)}, \forall k \in [N] \end{aligned}$$

(35c)

$$\begin{aligned}&x_i - \alpha _i {\Omega} _\xi ^{(k)} - p_{G,i}^{\max } \le s_k, \forall i \in {\mathcal {N}}, \forall k \in [N] \end{aligned}$$

(35d)

$$\begin{aligned}&p_{G,i}^{\min } - x_i + \alpha _i {\Omega} _\xi ^{(k)} \le s_k, \forall i \in {\mathcal {N}}, \forall k \in [N] \end{aligned}$$

(35e)

$$\begin{aligned}&{M}_{(ij,\cdot )}(x \!-\!\alpha {\Omega} _\xi ^{(k)} \!+\! \xi ^{(k)} \!-\! d) \!-\! p_{ij}^{\max } \le s_k, \forall ij \in {\mathcal {L}}, \forall k \in [N] \end{aligned}$$

(35f)

$$\begin{aligned}&p_{ij}^{\min } - {M}_{(ij,\cdot )}(x \!-\! \alpha {\Omega} _\xi ^{(k)} \!+\! \xi ^{(k)} \!-\! d) \le s_k, \forall ij \in {\mathcal {L}}, \forall k \in [N] \end{aligned}$$

(35g)

$$\begin{aligned}&\frac{1}{N} \sum _{k = 1}^{N} s_k - (1 - \epsilon ) \beta \le 0, \end{aligned}$$

(35h)

$$\begin{aligned}&s_k \ge \beta,~\forall k \in [N]. \end{aligned}$$

(35i)

The objective function, nodal balance constraint, and definition of ${\Omega} _{k}^{(k)}$ remain the same as previously for the scenario approach. Here, we introduce non-negative auxiliary variable $s_k$ for each uncertainty realization $k = 1, \dots , N$ to denote uncertain constraint violations in the generator and line flow constraints (35d)–(35g). Auxiliary variable $\beta \le 0$ and constraints (35h) and (35i) result directly from the definition of a CVaR constraint (Nemirovski and Shapiro 2007).