A data-driven approach to non-parametric reliability-based design optimization of structures with uncertain load

Abstract

This paper presents a simple method for conservatively solving a reliability-based design optimization (RBDO) problem of structures, when only a set of random samples of uncertain parameters is available. Specifically, we consider the truss design optimization under the stress constraints, where the external load is a random vector. The target confidence level, i.e., the probability that the structural reliability is no smaller than the target reliability, is specified, without any assumption on statistical information of the input distribution. We formulate a robust design optimization problem, any feasible solution of which satisfies the reliability constraint with the specified confidence level. The derived robust design optimization problem is solved with a sequential semidefinite programming. Two numerical examples are solved to show the trade-off between the specified confidence level and the structural volume.

1 Introduction

Consideration of uncertainty is indispensable for design of structures having high assurance of quality. Two major approaches to structural optimization against uncertainty are reliability-based design optimization (RBDO) and robust design optimization (see surveys by Park et al. (2006)), Beyer and Sendhoff (2007), Valdebenito and Schuëller (2010), Yao et al. (2011), and Jiang et al. (2018). Roughly speaking, robust design optimization makes use of a possibilistic (or bounded-but-unknown) model of uncertainty, which assumes only the set of values that the uncertain parameters can possibly take. In contrast, RBDO adopts a probabilistic model of uncertainty, which assumes statistic properties, i.e., a probabilistic distribution, of the uncertain parameters. As an emerging research topic, among others, in RBDO, diverse methods that can address uncertainty in distribution have received considerable attention (Ito and Kogiso 2016; Ito et al. 2018; Peng et al. 2017; Noh et al. 2011a; Cho et al. 2016; Moon et al. 2017, 2018; Picheny et al. 2010; Gunawan and Papalambros 2006; Youn and Wang 2008; Zaman and Mahadevan 2017; Jiang et al. 2013; Noh et al. 2011b; Huang and Zhang 2009; Choi et al. 2010).

Naturally, uncertainty has also been taken into account in the research field of mathematical optimization. An optimization model with possibilistic uncertainty is called robust optimization (Ben-Tal et al. 2009), while the one with probabilistic uncertainty is called chance-constrained optimization (a.k.a. stochastic programming) (Shapiro et al. 2009). Robust optimization requires that each constraint is satisfied in its worst case, when the uncertain parameters can take any value in a prescribed uncertainty set. In chance-constrained optimization, the probability that the constraints are satisfied should be no smaller than the prescribed threshold, when the distribution of the uncertain parameters is given. Uncertainty in distribution is addressed in the framework of distributionally robust optimization (Goh and Sim 2010; Ben-Tal et al. 2013; Bertsimas et al. to appear; Delage and Ye 2010), in which the worst-case distribution is considered when a set of distributions is given.

In most literature on robust optimization, the uncertainty set is assumed to be given a priori, and means for designing the uncertainty set is rarely discussed. As an exception, Goldfarb and Iyengar (2003) proposed to use the linear regression for the market data to determine the uncertainty set for robust portfolio selection. Also, for making use of data to design the uncertainty set, Tulabandhula and Rudin (2014) proposed to apply statistical learning methods, and Bertsimas et al. (2018) used the statistical hypothesis testing. Recently, Hong et al. (2017) have proposed quite a simple method to design the uncertain set. In this method, a given data set is split into two sets, and one of them is used to determine the shape and the other is used to calibrate the size of the uncertainty set. The size calibration is based on the order statistics (Arnold et al. 2008) of the data set to give feasible solutions of the derived robust optimization problem a statistical feasibility guarantee. This paper is inspired by Hong et al. (2017).

This paper attempts to show how the idea in Hong et al. (2017) can be utilized in RBDO with an unknown input distribution. We assume that only the set of random samples of uncertain variables is available. Specifically, in this paper, the external load applied to a structure is considered a random vector. As usual in RBDO, we impose a lower bound (i.e., a target reliability) for the probability that the constraints on structural performance are satisfied. However, this probability itself is a random variable, because we do not know the (joint) distribution of the external load. Here, we consider any possible distribution such that the given data set forms a random sample from it. We then impose a lower bound (i.e., a target confidence level) for the probability that the structural reliability is not smaller than the target reliability. Using the idea in Hong et al. (2017), we can derive a sufficient condition for this confidence level constraint. Since this sufficient condition is in a form of robust constraints, we thus transform the RBDO problem with a confidence level to a robust design optimization problem; more precisely, any feasible solution of the latter problem is feasible for the former problem. Furthermore, by using a technique developed in robust design optimization (Kanno and Takewaki 2006a), we can transform the robust design optimization problem to an optimization problem in the conventional form. Thus, we convert the RBDO problem with a confidence level to a tractable form.

There exist several methods proposed for RBDO with incomplete statistical information on random variables. For example, Gunawan and Papalambros (2006) used the Bayesian inference to estimate the structural reliability, when for some of random variables only a finite number of samples are available. To reduce the computational cost for a Bayesian approach to reliability estimate, Youn and Wang (2008) adopted the eigenvector dimension reduction method. Noh et al. (2011a, b) proposed to use the adjusted mean and correlation coefficient for an input normal distribution model with a confidence level. Given the intervals of input variables as data, Zaman and Mahadevan (2017) proposed to use the Johnson distribution as an input distribution model. In Cho et al. (2016) and Moon et al. (2017, 2018), some candidates of the input distribution types are prepared, and distribution parameters are considered random variables to compute the confidence level of the probability of failure with a Bayesian approach. Ito et al. (2018) assumed that each random variable follows a normal distribution with the mean and the variance modeled as random variables, and converted RBDO with a confidence level to the conventional form of RBDO with a modified value of the target reliability index. In this paper, we do not make any assumption on the distribution type and the statistical parameters; we only assume that the given data is a set of independent and identically distributed samples drawn from an unknown distribution.

An application of order statistics in structural design can be found in determination of the so-called A-basis and B-basis values of allowable stresses of materials for, particularly, aircraft and aerospace vehicles; see, e.g., Bhachu et al. (2016). Here, the B-basis value refers to the value below which 10% of the observations fall with 95% confidence. From a given material data set, a non-parametric method finds (a conservative estimate of) the B-basis value according to order statistics (Bhachu et al. 2016, section II). Thus, from the view point of structural optimization, this method uses order statistics to determine the parameters (more precisely, the specified bounds of stresses) in constraints. In contrast, the method presented in this paper uses order statics to determine the magnitude (or the level) of uncertainty against which the constraints should be satisfied.

As for approximate solution methods for chance-constrained optimization, scenario-generation approaches have been developed (Calafiore and Campi 2005, 2006; Luedtke and Ahmed 2008; Campi and Garatti 2011). In these methods, a chance constraint is replaced by a set of constraints evaluated at generated samples, where the probability that the obtained solution violates the original constraint has a theoretical bound. Also, there exist integer programming approaches to chance-constrained optimization in the case that the random variables have finite supports (Luedtke et al. 2010; Luedtke 2014; Vielma et al. 2012).

The paper is organized as follows. In Section 2, we define the RBDO problem that we handle in this paper, and give an overview of the methodology that links the RBDO problem to a robust design optimization problem. Following Hong et al. (2017), Section 3 explains how to construct the uncertainty set used in the robust design optimization. As a concrete RBDO problem, Section 4 discusses a design optimization problem of trusses under the stress constraints. Section 5 reports the results of numerical experiments. Some conclusions are drawn in Section 6.

In our notation, ^⊤ denotes the transpose of a vector or a matrix. The Euclidean norm of vector ${\boldsymbol {x}} \in \mathbb {R}^{n}$ is denoted by $\| {\boldsymbol {x}} \| = \sqrt {{\boldsymbol {x}}^{\top } {\boldsymbol {x}}}$. We often write the (n + m)-dimensional column vector (x^⊤,y^⊤)^⊤ consisting of ${\boldsymbol {x}} \in \mathbb {R}^{n}$ and ${\boldsymbol {y}} \in \mathbb {R}^{m}$ as (x,y). We use ${\mathcal {S}}^{n}$ to denote the set of n × n real symmetric matrices. We write X ≽ 0 and X ≼ 0, respectively, if $X \in {\mathcal {S}}^{n}$ is positive semidefinite and negative semidefinite. For a, $b\in \mathbb {R}$ with a < b, ]a,b[ designates the open interval between a and b. We use ${\mathcal {N}}({\boldsymbol {\mu }},\Sigma )$ to denote the multivariate normal distribution with mean vector μ and variance-covariance matrix Σ.

2 Problem setting

Throughout the paper, we assume that the input distribution in RBDO is known imprecisely. Some situations might match this assumption. For instance, suppose that only a set of some samples of random variables is given, and we try to use the data set directly rather to construct its empirical distribution model. Also, we may suppose that a distribution of random variables is given, but its statistical information is not reliable. Moreover, even if reliable statistic information of random variables is available, epistemic uncertainty stemming from, e.g., empirical modeling of a structural system, is inevitable. In this paper, we attempt to find a structural design which is robust against such uncertainty in a probabilistic model. By using the order statistics of the data set, we can give a structural design a confidence level for the prescribed reliability.

Consider a finite-dimensional structure. Let d denote the number of degrees of freedom of the nodal displacements. We use ${\boldsymbol {x}} \in \mathbb {R}^{m}$ to denote the vector of design variables, where m is the number of independent design variables.

Let ${\boldsymbol {q}} \in \mathbb {R}^{d}$ denote the external load vector. Throughout the paper, we assume that q is a random vector and that the other quantities are not uncertain. For notational convenience, let F denote the joint distribution function¹ of q.² Suppose that the performance requirement for the structure is expressed as

$$g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 , \quad l = 1,\dots,r . $$

Assuming that F is known, the conventional RBDO solves the following optimization problem:

$$\begin{array}{@{}rcl@{}} {\mathrm{Min.}} &{\quad}& g_{0}({\boldsymbol{x}}) \end{array} $$

(1a)

$$\begin{array}{@{}rcl@{}} {\mathrm{s.{ }t.}} && {\mathrm{P}}\{ g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 \} \ge 1 - \epsilon , \quad l = 1,\dots,r, \end{array} $$

(1b)

$$\begin{array}{@{}rcl@{}} && {\boldsymbol{x}} \in X . \end{array} $$

(1c)

Here, $g_{0}: \mathbb {R}^{m} \to \mathbb {R}$ is the objective function, 𝜖 ∈]0,1[ is a constant, and $X \subseteq \mathbb {R}^{m}$ is a given set, where constraint (1c) represents, e.g., the side constraints of the design variables. It is worth noting that 𝜖 is the threshold (or the upper bound) of the failure probability, and −Φ^− 1(𝜖) is the target reliability index, where Φ is the distribution function of the standard normal distribution. For simplicity, in the following we often call 1 − 𝜖 the target reliability.

We now proceed to the situation that F is unknown, or known imprecisely. Instead, we are given a data set $D=\{ \hat {{\boldsymbol {q}}}_{1},\dots ,\hat {{\boldsymbol {q}}}_{n} \}$, where $\hat {{\boldsymbol {q}}}_{1},\dots ,\hat {{\boldsymbol {q}}}_{n}$ are independent and identically distributed samples drawn from F. It should be clear that we do not attempt to estimate F from D. Rather, we assume only that D forms a random sample from F. Then the reliability of the structure, P{g_l(x;q) ≤ 0}, is considered a random variable with respect to F. In this regard, we use

$${\mathrm{P}}_{F} \left\{ {\mathrm{P}}\{ g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 \} \ge 1 - \epsilon \right\} $$

to denote the probability that the structure has the reliability no smaller than 1 − 𝜖. With this notation, the design optimization problem that we attempt to solve is formulated as follows:

$$\begin{array}{@{}rcl@{}} {\mathrm{Min.}} &{\quad}& g_{0}({\boldsymbol{x}}) \end{array} $$

(2a)

$$\begin{array}{@{}rcl@{}} {\mathrm{s.{ }t.}} && {\mathrm{P}}_{F} \left\{ {\mathrm{P}}\{ g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 \} \ge 1 - \epsilon \right\} \ge 1 - \delta ,\\ && \qquad\qquad\qquad\qquad\qquad\qquad l = 1,\dots,r, \end{array} $$

(2b)

$$\begin{array}{@{}rcl@{}} && {\boldsymbol{x}} \in X . \end{array} $$

(2c)

Here, δ ∈]0,1[ is a constant, and 1 − δ corresponds to the target confidence level. Namely, any feasible solution of this problem is guaranteed with probability at least 1 − δ to have the reliability no smaller than 1 − 𝜖.

Hong et al. (2017) proposed a robust optimization approach for approximately solving chance-constrained optimization problems. The methodology, adjusted to our context, can be summarized as follows. For α ≥ 0, define $Q(\alpha ) \subset \mathbb {R}^{d}$ by

$$ Q(\alpha) = \{ {\boldsymbol{q}} \in \mathbb{R}^{d} \mid ({\boldsymbol{q}} - \bar{{\boldsymbol{q}}})^{\top} \Omega ({\boldsymbol{q}} - \bar{{\boldsymbol{q}}}) \le \alpha \} , $$

(3)

where $\bar {{\boldsymbol {q}}} \in \mathbb {R}^{d}$ is a constant vector and $\Omega \in {\mathcal {S}}^{d}$ is a constant positive definite real symmetric matrix. Suppose that Q(α) satisfies

$$ {\mathrm{P}}_{F} \left\{ {\mathrm{P}}\{ {\boldsymbol{q}} \in Q(\alpha) \} \ge 1-\epsilon \right\} \ge 1-\delta . $$

(4)

Then we can easily see that, if x satisfies

$$g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 , \quad \forall {\boldsymbol{q}} \in Q(\alpha) , $$

then it satisfies

$${\mathrm{P}}_{F} \left\{ {\mathrm{P}}\{ g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 \} \ge 1 - \epsilon \right\} \ge 1 - \delta . $$

Therefore, problem (2a)–(2c) is approximated in a conservative manner by the following robust optimization problem with Q(α) satisfying (4):

$$\begin{array}{@{}rcl@{}} {\mathrm{Min.}} &{\quad}& g_{0}({\boldsymbol{x}}) \end{array} $$

(5a)

$$\begin{array}{@{}rcl@{}} {\mathrm{s.{ }t.}} && g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 \ (\forall {\boldsymbol{q}} \in Q(\alpha) ), \quad l = 1,\dots,r , \end{array} $$

(5b)

$$\begin{array}{@{}rcl@{}} && {\boldsymbol{x}} \in X . \end{array} $$

(5c)

More precisely, any feasible solution of problem (5a)–(5c) is feasible for problem (2a)–(2c).

What remain to be considered are how to construct Q(α) satisfying (4) and how to solve problem (2a)–(2c). Concerning the former, Section 3 briefly explains an idea found in Hong et al. (2017). The latter is dealt with in Section 4, for a concrete design optimization problem of trusses.

3 Construction of uncertainty set

As explained in Section 2, the confidence level in RBDO is guaranteed at a feasible solution of a robust optimization problem with the uncertainty set, Q(α), satisfying (4). We utilize the data set, D, to construct such a Q(α). In this section, we summarize the idea presented in Hong et al. (2017), with adjusting it to our purpose.

With referring to the definition in (3), we see that Q(α) is determined by $\bar {{\boldsymbol {q}}}$, Ω, and α. Among them, we first determine $\bar {{\boldsymbol {q}}}$ and Ω, and subsequently determine α. We choose some data points randomly from D. Let $\hat {{\boldsymbol {\mu }}}$ and $\hat {\Sigma }$ denote the mean and the variance-covariance matrix of the chosen data points. Then we put $\bar {{\boldsymbol {q}}}=\hat {{\boldsymbol {\mu }}}$ and $\Omega =\hat {\Sigma }^{-1}$.

In the following, we use the remaining data points in D to determine α satisfying (4). For simple notation, we use the same notation, $D=\{ \hat {{\boldsymbol {q}}}_{1},\dots ,\hat {{\boldsymbol {q}}}_{n} \}$, to denote the set of remaining data points. A small value of α is preferable to avoid an overly conservative structural design. The key observation in Hong et al. (2017, Lemma 3) is obtained from fundamentals of the order statistics. For the convenience of the reader, essentials of the proof, with modification to adjust our context, are repeated here.

Proposition 1

LetF_Xbe a continuous distribution function, and$X_{1},\dots ,X_{n} \in \mathbb {R}$beits independent and identically distributed samples. We useX₍₁₎ < X₍₂₎ < … < X_(n)to denote the order statistics ofX₁,…,X_n.For a given𝜖 ∈]0,1[,chooseδsatisfying

$$ (1-\epsilon)^{n} \le \delta < 1 . $$

(6)

Then, for any natural number p (1 ≤ p ≤ n) satisfying

$$ \sum\limits_{k=p}^{n} \binom{n}{k} (1-\epsilon)^{k} \epsilon^{n-k} \le \delta , $$

(7)

we have

$$ {\mathrm{P}}_{F_{X}} \{ F_{X}(X_{(p)}) \ge 1-\epsilon \} \ge 1-\delta . $$

(8)

Proof

Let s_1−𝜖 denote the (1 − 𝜖)-quantile of F_X, i.e.,

$$F_{X}(s_{1-\epsilon}-0) \le 1 - \epsilon \le F_{X}(s_{1-\epsilon}) . $$

As a simple computation, we obtain

$$\begin{array}{@{}rcl@{}} &&{}{\mathrm{P}}_{F_{X}} \{ F_{X}(X_{(p)}) > 1-\epsilon \} \\ &&{}= {\mathrm{P}}_{F_{X}} \{ X_{(p)} > s_{1-\epsilon} \} \\ &&{}= 1 - {\mathrm{P}}_{F_{X}} \{ X_{(p)} \le s_{1-\epsilon} \} . \end{array} $$

(9)

As a fundamental of the order statistics (Arnold et al. 2008, section 2.2), we have³

$$\begin{array}{@{}rcl@{}} &&{}{\mathrm{P}}_{F_{X}} \{ X_{(p)} \le s_{1-\epsilon} \} \\ &&{}= \sum\limits_{k=p}^{n} \binom{n}{k} F_{X}(s_{1-\epsilon})^{k}(1-F_{X}(s_{1-\epsilon}))^{n-k} \\ &&{}= \sum\limits_{k=p}^{n} \binom{n}{k} (1-\epsilon)^{k} \epsilon^{n-k} . \end{array} $$

(10)

It follows from (9) and (10) that (7) implies (8). □

Remark 1

The assumption in (6) of Proposition 1 ensures the existence of p satisfying (7); we can easily see that p = n satisfies (7).

Define $a : \mathbb {R}^{d} \to \mathbb {R}$ by

$$a({\boldsymbol{q}}) = ({\boldsymbol{q}} - \bar{{\boldsymbol{q}}})^{\top} \Omega ({\boldsymbol{q}} - \bar{{\boldsymbol{q}}}) . $$

Renumber the data points $\hat {{\boldsymbol {q}}}_{1},\dots ,\hat {{\boldsymbol {q}}}_{n} \in D$ so that

$$a(\hat{{\boldsymbol{q}}}_{(1)}) < a(\hat{{\boldsymbol{q}}}_{(2)}) < {\dots} < a(\hat{{\boldsymbol{q}}}_{(n)}) $$

holds. Then, $a(\hat {{\boldsymbol {q}}}_{(1)}),\dots , a(\hat {{\boldsymbol {q}}}_{(n)})$ correspond to the order statistics of samples $a(\hat {{\boldsymbol {q}}}_{1}),\dots , a(\hat {{\boldsymbol {q}}}_{n})$. Let $\tilde {p}$ be the minimum natural number satisfying (7). It is worth noting that $\tilde {p}$ depends only on n, 𝜖, and δ, i.e., the number of data points in D, the target reliability, and the target confidence level. From Proposition 1, we obtain

$$ {\mathrm{P}}_{F_{A}}\{ F_{A}(a({\boldsymbol{q}}_{(\tilde{p})})) \ge 1-\epsilon \} \ge 1-\delta, $$

(11)

where F_A is the distribution function of a(q). On the other hand, the definition of the distribution function yields

$$ F_{A}(\alpha) = {\mathrm{P}}\{ a({\boldsymbol{q}}) \le \alpha \} = {\mathrm{P}}\{ {\boldsymbol{q}} \in Q(\alpha) \} . $$

(12)

It follows from (11) and (12) that we obtain

$${\mathrm{P}}_{F} \left\{ {\mathrm{P}}\{ {\boldsymbol{q}} \in Q(\tilde{\alpha}) \} \ge 1-\epsilon \right\} \ge 1-\delta $$

with $\tilde {\alpha }=a({\boldsymbol {q}}_{(\tilde {p})})$.

The upshot is that any feasible solution of problem (5a)–(5c) with the uncertainty set $Q(\tilde {\alpha })$ is guaranteed to have the reliability 1 − 𝜖 with the confidence level no smaller than 1 − δ.

Remark 2

Although in this paper we restrict ourselves to single load cases for simplicity, the presented method can deal with multiple load cases. For a problem with s load cases, we suppose that corresponding data sets, $D_{1},\dots ,D_{s} \subseteq \mathbb {R}^{d}$, of external loads are given, where D_j forms a random sample from F_j(j = 1,…,s). It is worth noting that D_j and $D_{j^{\prime }} (j^{\prime }\not = j)$ may consist of different numbers of data points. For each j = 1,…,s, we compute $\bar {{\boldsymbol {q}}}_{j}$ and Ω_j by using some data points randomly chosen from D_j. Apply the procedure described above to determine $\tilde {\alpha }_{j}$, so that we have

$${\mathrm{P}}_{F_{j}} \left\{ {\mathrm{P}}\{ {\boldsymbol{q}} \in Q_{j}(\tilde{\alpha}_{j}) \} \ge 1-\epsilon \right\} \ge 1-\delta . $$

Thus, for a problem with multiple loads, we replace (5b) with

$$g_{l}({\boldsymbol{x}};{\boldsymbol{q}}) \le 0 \ (\forall {\boldsymbol{q}} \in Q_{j}(\alpha_{j}) ), \quad l = 1,\dots,r; \ j = 1,\dots,s $$

and solve problem (5a)–(5c).

4 Application to truss design under stress constraints

In this section, we demonstrate how the methodology introduced in Section 2 can be applied to a concrete problem in RBDO. Specifically, we consider design optimization of trusses under uncertainty in the external load. As for the reliability, we consider the probability that the member stresses do not exceed the specified bound.

Consider a truss structure. We use x_i(i = 1,…,m) to denote the member cross-sectional area, which is considered a design variable, where m is the number of members. We set the lower bound, denoted $\underline {x} > 0$, for x_i, and do not consider change in truss topology in the course of optimization. In the following, we assume small deformation and linear elasticity.

Let $K({\boldsymbol {x}}) \in {\mathcal {S}}^{d}$ denote the stiffness matrix, which has the form

$$K({\boldsymbol{x}}) = \sum\limits_{i = 1}^{m} x_{i} K_{i} = \sum\limits_{i = 1}^{m} \frac{E}{l_{i}} x_{i} {\boldsymbol{b}}_{i} {\boldsymbol{b}}_{i}^{\top} . $$

Here, l_i is the undeformed length of member i, E is the Young modulus, ${\boldsymbol {b}}_{i} \in \mathbb {R}^{d}$ is a constant vector, and $K_{i} = \frac {E}{l_{i}} {\boldsymbol {b}}_{i} {\boldsymbol {b}}_{i}^{\top }$ is a constant matrix. The equilibrium equation is written as

$$K({\boldsymbol{x}}) {\boldsymbol{u}} = {\boldsymbol{q}} . $$

Since we give positive lower bounds for all the member cross-sectional areas, it is natural to assume rankK(x) = d. Therefore, the equilibrium equation has a unique solution for any ${\boldsymbol {q}}\in \mathbb {R}^{d}$. We use u(x;q) to denote this solution.

For member i, let σ_i(u) denote the stress corresponding to displacement u. Since we do not allow change in the truss topology in the course of optimization, the stress constraint can be written simply as

$$\underline{\sigma}_{i} \le \sigma_{i}({\boldsymbol{u}}({\boldsymbol{x}};{\boldsymbol{q}})) \le \overline{\sigma}_{i} , $$

where $\underline {\sigma }_{i}$ and $\overline {\sigma }_{i}$ are specified lower and upper bounds, respectively. This constraint can be rewritten as

$$ |\sigma_{i}({\boldsymbol{u}}({\boldsymbol{x}};{\boldsymbol{q}})) - r_{i}| \le \sigma_{{\mathrm{c}}i} $$

(13)

with $\sigma _{{\mathrm {c}}i} = (\overline {\sigma }_{i} - \underline {\sigma }_{i})/2$ and $r_{i} = (\overline {\sigma }_{i} + \underline {\sigma }_{i})/2$. Since q is considered a random vector, σ_i(u(x;q)) is a random variable. Therefore, we handle constraint (13) within the framework of the reliability constraint with the specified confidence level, as explained in Section 2. Accordingly, the design optimization problem that we attempt to solve is formulated as follows:

$$\begin{array}{@{}rcl@{}} {\mathrm{Min.}} &{\quad}& {\boldsymbol{l}}^{\top} {\boldsymbol{x}} \end{array} $$

(14a)

$$\begin{array}{@{}rcl@{}} {\mathrm{s.{ }t.}} && {\mathrm{P}}_{{\mathrm{F}}} \left\{ {\mathrm{P}}\{ |\sigma_{i}({\boldsymbol{u}}({\boldsymbol{x}};{\boldsymbol{q}}))| \le \sigma_{{\mathrm{c}}} \} \ge 1-\epsilon \right\} \ge 1-\delta,\\ && \qquad\qquad\qquad\qquad\qquad i = 1,\dots,m, \end{array} $$

(14b)

$$\begin{array}{@{}rcl@{}} && x_{i} \ge \underline{x} , \quad i = 1,\dots,m . \end{array} $$

(14c)

Here, the objective function is the structural volume. As a conservative approximation of problem (14a)–(14c), we consider the following robust optimization problem:

$$\begin{array}{@{}rcl@{}} {\mathrm{Min.}} &{\quad}& {\boldsymbol{l}}^{\top} {\boldsymbol{x}} \end{array} $$

(15a)

$$\begin{array}{@{}rcl@{}} {\mathrm{s.{ }t.}}&& |\sigma_{i}({\boldsymbol{u}}({\boldsymbol{x}};{\boldsymbol{q}}))| \le \sigma_{{\mathrm{c}}} \ (\forall {\boldsymbol{q}} \in Q(\tilde{\alpha})),\\ && \qquad\qquad\qquad\qquad\qquad i = 1,\dots,m, \end{array} $$

(15b)

$$\begin{array}{@{}rcl@{}} && x_{i} \ge \underline{x} , \quad i = 1,\dots,m . \end{array} $$

(15c)

The attention of the remainder of this section is focused on how to solve this robust optimization problem.

Define $G_{i} \in {\mathcal {S}}^{d + 1}$ by

$$\begin{array}{@{}rcl@{}} G_{i} &= \left[\begin{array}{cccccc} E {\boldsymbol{b}}_{i}/l_{i} \\ -r_{i} \end{array}\right] \left[\begin{array}{cccccc} E {\boldsymbol{b}}_{i}/l_{i} \\ -r_{i} \end{array}\right]^{\top} - \left[\begin{array}{cccccc} O & O \\ O & \sigma_{{\mathrm{c}}i}^{2} \end{array}\right] \end{array} $$

(16)

so that

$$|\sigma_{i}({\boldsymbol{u}}) - r_{i}| \le \sigma_{{\mathrm{c}}i} \quad\Leftrightarrow\quad \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right]^{\top} G_{i} \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right] \le 0 $$

holds. For ${\boldsymbol {x}} \in \mathbb {R}^{m}$ satisfying (15c), define $\Psi ({\boldsymbol {x}}) \in {\mathcal {S}}^{d + 1}$ by

$$\Psi({\boldsymbol{x}}) = \left[\begin{array}{cccccc} K({\boldsymbol{x}}) \\ -\bar{{\boldsymbol{q}}}^{\top} \end{array}\right] \Omega \left[\begin{array}{cccccc} K({\boldsymbol{x}}) \\ -\bar{{\boldsymbol{q}}}^{\top} \end{array}\right]^{\top} - \left[\begin{array}{cccccc} O & O \\ O & \tilde{\alpha} \end{array}\right] $$

so that

$$\exists {\boldsymbol{q}} \in Q(\tilde{\alpha}) : \ K({\boldsymbol{x}}) {\boldsymbol{u}} = {\boldsymbol{q}} \quad\Leftrightarrow\quad \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right]^{\top} \Psi({\boldsymbol{x}}) \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right] \le 0 $$

holds. The following proposition can be obtained in a manner similar to (Kanno and Takewaki 2006a, Proposition 3.1).

Proposition 2

Suppose rankK(x) = d.Thenxsatisfies

$$ |\sigma_{i}({\boldsymbol{u}}({\boldsymbol{x}};{\boldsymbol{q}})) - r_{i}| \le \sigma_{{\mathrm{c}}i} , \quad \forall {\boldsymbol{q}} \in Q(\tilde{\alpha}) $$

(17)

if and only if there exists ν_i ≥ 0 satisfying

$$\Psi({\boldsymbol{x}}) - \nu_{i} G_{i} \succeq 0 . $$

A proof appears in Appendix.

It follows from Proposition 2 that problem (15a)–(15c) is equivalent to the following optimization problem:

$$\begin{array}{@{}rcl@{}} {\mathrm{Min.}} &{\quad}& {\boldsymbol{l}}^{\top} {\boldsymbol{x}} \end{array} $$

(18a)

$$\begin{array}{@{}rcl@{}} {\mathrm{s.{ }t.}} && \Psi({\boldsymbol{x}}) - \nu_{i} G_{i} \succeq 0 , \quad i = 1,\dots,m, \end{array} $$

(18b)

$$\begin{array}{@{}rcl@{}} && \nu_{i} \ge 0 , \quad i = 1,\dots,m, \end{array} $$

(18c)

$$\begin{array}{@{}rcl@{}} && x_{i} \ge \underline{x} , \quad i = 1,\dots,m . \end{array} $$

(18d)

Here, ${\boldsymbol {x}}\in \mathbb {R}^{m}$ and ${\boldsymbol {\nu }}\in \mathbb {R}^{m}$ are variables to be optimized.

We next present an algorithm for finding a local optimal solution of problem (18a)–(18d). The algorithm is essentially based on the same idea as the sequential semidefinite programming (sequential SDP) proposed in Kanno and Takewaki (2006a); see also Kanno et al. (2001) and Kanzow et al. (2005). It is worth noting that a maximization problem of the robustness of a truss is considered in Kanno and Takewaki (2006a). In contrast, in problem (18a)–(18d), we fix the target robustness, $\tilde {\alpha }$. Hence, the sequential SDP for problem (18a)–(18d), presented in Algorithm 1, is simpler than the one used in Kanno and Takewaki (2006a).

In the sequential SDP, the nonlinear matrix-valued function Ψ in (18b) is linearized at the incumbent solution, denoted x^(k). Also, to prevent too large step length, the quadratic penalty on variations of variables, i.e., ρ∥x −x^(k)∥² and ρ∥v −v^(k)∥², are added to the objective function, where ρ > 0 is a penalty parameter. Accordingly, at the k th iteration we solve the following problem in variables x and ν:

$$\begin{array}{@{}rcl@{}} {\mathrm{Min.}} &{\quad}& {\boldsymbol{l}}^{\top} {\boldsymbol{x}} + \rho (\| {\boldsymbol{x}} - {\boldsymbol{x}}^{(k)} \|^{2} + \| {\boldsymbol{\nu}} - {\boldsymbol{\nu}}^{(k)} \|^{2}) \end{array} $$

(19a)

$$\begin{array}{@{}rcl@{}} {\mathrm{s.{ }t.}} && D\Psi({\boldsymbol{x}}^{(k)}) ({\boldsymbol{x}}- {\boldsymbol{x}}^{(k)}) + \Psi({\boldsymbol{x}}^{(k)}) - \nu_{i} G_{i} \succeq 0 ,\\ && \qquad\qquad\qquad\qquad\qquad i = 1,\dots,m, \end{array} $$

(19b)

$$\begin{array}{@{}rcl@{}} && \nu_{i} \ge 0 , \quad i = 1,\dots,m, \end{array} $$

(19c)

$$\begin{array}{@{}rcl@{}} && x_{i} \ge \underline{x} , \quad i = 1,\dots,m . \end{array} $$

(19d)

Here, DΨ(x^(k)) is the derivative of mapping $\Psi : \mathbb {R}^{m} \to {\mathcal {S}}^{d + 1}$ at x^(k) defined such that DΨ(x^(k))z is a linear function of ${\boldsymbol {z}} = (z_{1},\dots ,z_{m})^{\top } \in \mathbb {R}^{m}$ given by

$$D\Psi({\boldsymbol{x}}^{(k)}) {\boldsymbol{z}} = \sum\limits_{i = 1}^{m} z_{i} \frac{\partial \Psi}{\partial x_{i}}({\boldsymbol{x}}^{(k)}) . $$

Problem (19a)–(19d) is an SDP problem, which can be solved efficiently with a primal-dual interior-point method (Anjos and Lasserre 2012).

5 Numerical experiments

This section presents two numerical examples. Algorithm 1 was implemented in MATLAB ver. 9.0.0. We solved the SDP problem in (19a)–(19d) by using CVX ver. 2.1 (Grant and Boyd 2008, 2018) with SDPT3 ver. 4.0 (Tütüncü et al. 2003). The cvx_precision parameter of CVX is set to best, which means that the solver continues as far as it can make progress (Grant and Boyd 2018). Computation was carried out on a 2.2GHz Intel Core i5 processor with 8GB RAM.

In the following examples, the lower bound for the member cross-sectional areas is set to $\underline {x}= 100 \mathrm {mm^{2}}$. Note that the lower bound constraints on the member cross-sectional areas are inactive for all the solutions obtained in this section. The parameters of Algorithm 1 are ρ = 10^− 3 and 𝜖₀ = 10^− 4mm². The initial point is given as $x^{(0)}_{i}= 2000 \mathrm {mm^{2}} (i = 1,\dots ,m)$.

5.1 Example (I): 2-bar truss

Consider the planar truss shown in Fig. 1. The truss has m = 2 members and d = 2 degrees of freedom of the nodal displacements. The Young modulus of the members is E = 20GPa. The lower and upper bounds for the member stresses are $\underline {\sigma }_{i}=-100 \text {MPa}$ and $\overline {\sigma }_{i}= 100 \text {MPa} (i = 1,2)$, respectively.

Fig. 1

Example (I). A 2-bar truss

The data set $D \subset \mathbb {R}^{2}$ of the external load vector consists of 250 data points drawn from the normal distribution with mean μ and variance-covariance matrix Σ given as

$$ {\boldsymbol{\mu}} = \left[\begin{array}{cccccc} 0 \\ -100 \end{array}\right] \text{kN} , \quad \Sigma = \left[\begin{array}{cccccc} 100 & 50 \\ 50 & 150 \end{array}\right] \mathrm{kN^{2}} . $$

(20)

This does not mean that the external load is assumed to follow the normal distribution. It should be emphasized that no assumption is made on the distribution that uncertain parameters follow.

Figure 2 shows the data points, as well as the uncertainty set obtained from the data set. We used 50 data points, indicated by “∘” in Fig. 2, to determine $\bar {{\boldsymbol {q}}}$ and Ω of the uncertainty set. The mean and the variance-covariance matrix of these data points are

$$\hat{{\boldsymbol{\mu}}}= \left[\begin{array}{cccccc} -1.319 \\ -97.865 \end{array}\right] \text{kN} , \quad \hat{\Sigma}= \left[\begin{array}{cccccc} 115.40 & 49.53 \\ 49.53 & 138.46 \end{array}\right] \mathrm{kN^{2}} , $$

from which we put

$$\bar{{\boldsymbol{q}}} = \left[\begin{array}{cccccc} -1.319 \\ -97.865 \end{array}\right] \text{kN} , \quad \Omega = \left[\begin{array}{cccccc} 0.010237 & -0.003662 \\ -0.003662 & 0.008532 \end{array}\right] \mathrm{kN^{-2}} . $$

The remaining 200 points, indicated by “ ×” in Fig. 2, were used to determine $\tilde {\alpha }$. For instance, if we set 𝜖 = 0.1 and δ = 0.08 (i.e., if we require that the failure probability should not be greater than 10%, with 8% confidence level), then we obtain

$$\tilde{p} = 187, \quad \tilde{\alpha} = 48.947. $$

The boundary of $Q(\tilde {\alpha })$ is shown in Fig. 2 by a solid curve.

Fig. 2

The data set for example (I). “∘” The data points used for learning the shape, i.e., $\bar {{\boldsymbol {q}}}$ and Ω, of the uncertainty set; and “×” for determining the size, $\tilde {\alpha }$

The solution obtained by Algorithm 1 is

$$ {\boldsymbol{x}}^{*}=(1240.7,1752.2) \mathrm{mm^{2}} . $$

(21)

Figure 3a shows this solution, where the width of each member in the figure is proportional to its cross-sectional area. The algorithm terminated after 11 iterations. The computational time was 3.1s. To confirm the feasibility and quality of the obtained solution, we computed the extreme values of the member stresses, when the external load satisfies ${\boldsymbol {q}} \in Q(\tilde {\alpha })$. Figure 3b reports the results, where the member indices are shown in Fig. 1 and $\sigma _{{\mathrm {c}}}:=\overline {\sigma }_{i}=-\underline {\sigma }_{i} (i = 1,2)$. We can confirm that, for each member, there exists an external load with which the stress constraint becomes active.

Fig. 3

The obtained solution of example (I) with 𝜖 = 0.1 and δ = 0.08. a The obtained truss design; and b its maximum and minimum member stresses

The optimal value increases as the required confidence level increases. Figure 4 shows this trade-off relationship. As for the threshold of the failure probability, we here consider three cases: 𝜖 = 0.1, 0.08, and 0.05. It is worth noting that, for 𝜖 = 0.05, the assumption in (6) of Proposition 1 reads δ ≥ (1 − 𝜖)ⁿ = (1 − 0.05)²⁰⁰ ≃ 3.5053 × 10^− 5. This means that, to obtain a solution with a confidence level larger than 1 − (3.5053 × 10^− 5) for 𝜖 = 0.05, the proposed method requires a larger number of data points than the present data set.

Fig. 4

The trade-off between the confidence level and the objective value of the solution obtained by the proposed method. Example (I) with a𝜖 = 0.1; b𝜖 = 0.08; and c𝜖 = 0.05

Figure 5 reports the results of Monte Carlo simulation for the solution obtained with 𝜖 = 0.1 and δ = 0.08. We generated 50000 data sets, each of which consists of 50000 samples drawn as ${\boldsymbol {q}} \sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )$. For each data set, we checked the population of data points with which the stress constraint is violated. Figure 5 shows the ratio of the population divided by the total number of data points. We can see that the ratio of failure is much less than the specified threshold, 𝜖 = 0.1. However, this does not imply that the obtained solution is overly conservative. Namely, although in our problem setting we consider any distribution that can explain the given data in Fig. 2, the Monte Carlo simulation was performed for only one distribution.

Fig. 5

The results of Monte Carlo simulation for a specified normal distribution. Example (I). a The failure probability of the constraint on member 1; and b the one on member 2

We next investigate the gap between the proposed method and methods using an estimated distribution. Namely, we assume the normal distribution, and use all the data points in Fig. 2 to estimate the mean and the variance-covariance matrix. This estimation yields

$$\check{{\boldsymbol{\mu}}}= \left[\begin{array}{cccccc} -0.861 \\ -99.130 \end{array}\right] \text{kN} , \quad \check{\Sigma}= \left[\begin{array}{cccccc} 104.78 & 47.87 \\ 47.87 & 133.48 \end{array}\right] \mathrm{kN^{2}} . $$

Then, we generate 5 × 10⁶ samples drawn as ${\boldsymbol {q}} \sim {\mathcal {N}}(\check {{\boldsymbol {\mu }}},\check {\Sigma })$, and compute the structural response of the solution in (21). Figure 6 reports the values of |σ_i(x^∗;q)|/σ_c for these samples, where |σ_i(x^∗;q)|/σ_c > 1 means that the stress constraint is violated. The obtained failure probabilities for member 1 and member 2, respectively, are 0.01442 and 0.00956. These values are less than the specified lower bound for failure probability, 𝜖 = 0.1, because in the proposed method the distribution type is not identified.

Fig. 6

The results of Monte Carlo simulation for a normal distribution estimated from the data in Fig. 2. Example (I). a Member 1; and b member 2

A solution obtained by the proposed method generally depends on choice of data points used for learning the shape and for calibrating the size of the uncertainty set. In Fig. 7, we investigate robustness of the proposed method against this choice. Here, we used a single data set, consisting of 250 data points. Also, we fixed the number of data points used for shape determination as 50; the remaining 200 data points were used for size calibration. Partition of the data set into these two sets was determined randomly. Figure 7 reports the objective values obtained for 10000 randomly generated partitions. The mean of these objective values is 3.7966 × 10⁶mm², and the standard deviation is 0.0677 × 10⁶mm². Thus, variation of the objective value is quite small. It is worth noting that, since all the solutions in Fig. 7 satisfy the reliability constraint with at least the specified confidence level, we can adopt the best one (i.e., the solution having the minimal objective value) among them as the final solution.

Fig. 7

The objective values obtained for example (I) with (𝜖,δ) = (0.1,0.08), when the given data set is partitioned randomly into a set for shape determination and a set for size calibration of the uncertainty set

We next examine robustness of the proposed method against choice of the number data points for shape determination; the other data points are used for size calibration. Figure 8 shows variation of the obtained solutions, where the the data set, consisting of 250 data points, is fixed. Figure 8a shows the variation of the minimal p satisfying (7) in Proposition 1. This value is used in the size calibration phase. It should be clear that the relation in Fig. 8a is not affine, although it looks almost affine. Figure 8b reports the objective values obtained by the proposed method. We can observe that variation of the objective values is only about 5%. Also, reducing the number of data points for size calibration does not necessarily imply increase in the objective value. Figure 8c and d show the constructed uncertainty set, as well as separation of the data set, when 30 data points and 227 data points are used for shape determination, respectively. In Fig. 8d, all of the remaining 23 data points are used for size calibration. Compared with Fig. 8c, some data points far from the center of the ellipsoid are not selected (accidentally) as the ones for size calibration, the objective value in Fig. 8d is not too overly conservative.

Fig. 8

Variation of the solution for example (I) with (𝜖,δ) = (0.1,0.08) with respect to the number of data points for shape determination of the uncertainty set. a The minimum p satisfying (7) (i.e., $\tilde {p}$ in Section 3); b the objective value; c the uncertainty set when 30 data points are used for shape determination; and d the uncertainty set when 227 data points are used for shape determination. “∘” The data points for shape determination; and “×” for size calibration

Finally, we vary the data set size and observe change in the obtained solutions. As for the data set size, we consider four cases, where data sets consist of 80, 150, 250, and 450 data points drawn from the normal distribution with mean μ and variance-covariance matrix Σ in (20). In each case, we prepared 10000 randomly generated data sets with randomly changing a seed of the random number generator of MATLAB. For every data set, we used 50 randomly chosen data points for shape determination of the uncertainty set; the remaining data points were used for size calibration. Figure 9 and Table 1 report the obtained results. It is natural that the mean and the standard deviation of the obtained objective value decrease as the number of data points increases, because a larger number of data points provide us with more information on the underlying distribution. In other words, the results shown in Fig. 9 and Table 1 do not necessarily mean that a solution obtained with a small number of data points is overly conservative, because, to ensure robustness against uncertainty in a distribution with a smaller number of data points, we need to consider an uncertainty set with a larger size.

Fig. 9

The objective values obtained for example (I) with (𝜖,δ) = (0.1,0.08), when data sets are randomly generated. a 80 data points; b 150 data points; c 250 data points; and d 450 data points. In every case, randomly chosen 50 data points are used for shape determination of the uncertainty set

Table 1 The statistics of the results shown in Fig. 9

5.2 Example (II): 29-bar truss

Consider the planar truss shown in Fig. 10. The truss consists of m = 29 members, and has d = 20 degrees of freedom of the nodal displacements. The undeformed lengths of horizontal members and vertical members are 1m. The Young modulus of the members is E = 20GPa. The lower and upper bounds for the member stresses are $\underline {\sigma }_{i}=-100 \text {MPa}$ and $\overline {\sigma }_{i}= 100 \text {MPa} (i = 1,\dots ,m)$, respectively.

Fig. 10

Example (II). A 29-bar truss

Figure 11 shows the data set $D \subset \mathbb {R}^{d}$ of the external load vector constituting of 300 samples drawn from a normal distribution. Thus, the number of random variables is d = 20. The mean of the external load, denoted μ, is as illustrated in Fig. 10, where the magnitudes of the two nonzero nodal forces are 100kN. The variance-covariance matrix is Σ = 250I in kN². Again, it should be clear that in our framework no assumption is made on the distribution that the external load follows. Namely, the normal distribution mentioned above was used only for generating the data set.

Fig. 11

The data set for example (II). “∘” The data points used for learning the shape, i.e., $\bar {{\boldsymbol {q}}}$ and Ω, of the uncertainty set; and “ ×” for determining the size, $\tilde {\alpha }$

Among 300 data points, we used 100 data points to learn $\bar {{\boldsymbol {q}}}$ and Ω, and the remaining 200 points to determine $\tilde {\alpha }$. We set 𝜖 = 0.1 and δ = 0.08. Figure 12a shows the solution obtained by Algorithm 1. The algorithm terminated after 120 iterations. The total computational time was 799.2s. Concerning the truss design in Fig. 12a, Fig. 12b collects the extreme values of the member stresses corresponding to ${\boldsymbol {q}} \in Q(\tilde {\alpha })$, where the member indices are shown in Fig. 12a and $\sigma _{{\mathrm {c}}}:=\overline {\sigma }_{i}=-\underline {\sigma }_{i} (i = 1,\dots ,m)$. We can observe that, for each member, there exists a load case with which the stress constraint becomes active. For the target reliability 1 − 𝜖 = 0.9, Fig. 13 shows the trade-off between the confidence level, 1 − δ, and the structural volume of the solution obtained by the proposed method.

Fig. 12

The obtained solution of example (II) with 𝜖 = 0.1 and δ = 0.08. a The obtained truss design; and b its maximum and minimum member stresses

Fig. 13

The trade-off between the confidence level and the objective value of the solution obtained with the proposed method. Example (II) with 𝜖 = 0.1

6 Conclusions

This paper has presented a data-driven approach to reliability-based design optimization (RBDO) of structures subjected to the uncertain external load. In this approach, a robust design optimization problem is solved to find a structural design that has the target reliability with the prescribed confidence level. The probability that the reliability of the obtained solution is no smaller than the target reliability is guaranteed to be no smaller than the prescribed confidence level, irrespective of the distribution of the external load. The uncertainty set, used in the robust design optimization problem, is determined from the given data (i.e., the set of given samples of the external load), by using the order statistics. This construction procedure of the uncertainty set basically follows the idea presented in Hong et al. (2017).

The methodology presented in this paper is quite versatile, in the sense that many of existing techniques for robust design optimization can be incorporated into the framework. This suggests possibilities of extensions of the presented method to RBDO problems in diverse problem settings. For instance, uncertainty in stiffnesses of structural elements (Guo et al. 2009, 2011, 2015; Kanno and Takewaki 2006b, 2008) could be explored. Also, for topology optimization, a topology-dependent uncertainty set of the external load, considered in Yonekura and Kanno (2010), Kanno and Guo (2010), and Kanno (2018) for robust design optimization, could be extended for RBDO. A key is that, roughly speaking, robust design optimization can consider a bit more complicated constraints, as well as larger-size problems, than RBDO, although the computational efficiency should be evaluated directly.

The presented method provides a feasible solution of the RBDO problem with a confidence level. The gap between the objective value obtained by the presented method and the optimal value of the original problem remains to be studied. When only very limited number of data points are available, the proposed method cannot provide with us sufficiently high confidence for high reliability. As a remedy, possibility of use of a non-parametric bootstrap method (Hanson and Koopmans 1964), which is often used for assessing allowable stresses of materials in structural design (Bhachu et al. 2016; Edwards et al. 2011), could be explored.

Appendix: Proof of Proposition 2

This section presents a proof of Proposition 2. The following well-known fact, called the S-lemma, plays a pivotal role.

Proposition 3

Let f,$g : \mathbb {R}^{n} \to \mathbb {R}$be quadratic functions. Suppose that there existsan$\hat {{\boldsymbol {x}}} \in \mathbb {R}^{n}$satisfying$f(\hat {{\boldsymbol {x}}}) < 0$.The following two statements are equivalent:

• (a) f(x) ≤ 0 ⇒ g(x) ≥ 0,

• (b) ∃τ ≥ 0:$g({\boldsymbol {x}}) + \tau f({\boldsymbol {x}}) \ge 0 (\forall {\boldsymbol {x}} \in \mathbb {R}^{n})$.

A proof can be found in a survey paper (Pólik and Terlaky 2007). A slight variance is made in the following.

Proposition 4

Let f,$g : \mathbb {R}^{n} \to \mathbb {R}$be quadratic functions. Suppose that there existan$\hat {{\boldsymbol {x}}} \in \mathbb {R}^{n}$satisfying$f(\hat {{\boldsymbol {x}}}) < 0$andan$\tilde {{\boldsymbol {x}}} \in \mathbb {R}^{n}$satisfying$g(\tilde {{\boldsymbol {x}}}) > 0$.The following two statements are equivalent:

• (a) f(x) ≤ 0 ⇒ g(x) ≤ 0,

• (b) ∃ν ≥ 0:$f({\boldsymbol {x}}) - \nu g({\boldsymbol {x}}) \ge 0 (\forall {\boldsymbol {x}} \in \mathbb {R}^{n})$.

Proof

It follows from Proposition 2 that (a) holds if and only if there exists τ ≥ 0 satisfying $\tau f({\boldsymbol {x}}) - g({\boldsymbol {x}}) \ge 0 (\forall {\boldsymbol {x}} \in \mathbb {R}^{n})$. The latter condition is not satisfied with τ = 0, because there exists $\tilde {{\boldsymbol {x}}}$ such that $g(\tilde {{\boldsymbol {x}}})>0$. By putting ν = 1/τ, we obtain (b).

□

The following fact can be found in, e.g., Calafiore and El Ghaoui (2004).

Proposition 5

Let $Q \in {\mathcal {S}}^{n}$ , ${\boldsymbol {p}} \in \mathbb {R}^{n}$ , and $r \in \mathbb {R}$ . The following two statements are equivalent:

• (a) $\displaystyle \left [\begin {array}{cccccc} {\boldsymbol {x}} \\ 1 \end {array}\right ]^{\top } \left [\begin {array}{cccccc} Q & {\boldsymbol {p}} \\ {\boldsymbol {p}}^{\top } & r \end {array}\right ] \left [\begin {array}{cccccc} {\boldsymbol {x}} \\ 1 \end {array}\right ] \ge 0 (\forall {\boldsymbol {x}} \in \mathbb {R}^{n})$ ,

• (b) $\displaystyle \left [\begin {array}{cccccc} Q & {\boldsymbol {p}} \\ {\boldsymbol {p}}^{\top } & r \end {array}\right ] \succeq 0$ .

Proof

It is trivial that (ii) implies (i). We show that (i) implies (ii) by the contradiction. Suppose that (ii) does not holds, i.e., there exist ${\boldsymbol {x}}^{\prime } \in \mathbb {R}^{n}$ and $\xi \in \mathbb {R}$ satisfying

$$ \left[\begin{array}{cccccc} {\boldsymbol{x}}^{\prime} \\ \xi \end{array}\right]^{\top} \left[\begin{array}{cccccc} Q & {\boldsymbol{p}} \\ {\boldsymbol{p}}^{\top} & \gamma \end{array}\right] \left[\begin{array}{cccccc} {\boldsymbol{x}}^{\prime} \\ \xi \end{array}\right] < 0 . $$

(22)

If ξ≠ 0, then (22) is reduced to

$$\left[\begin{array}{cccccc} {\boldsymbol{x}}^{\prime}/\xi \\ 1 \end{array}\right]^{\top} \left[\begin{array}{cccccc} Q & {\boldsymbol{p}} \\ {\boldsymbol{p}}^{\top} & \gamma \end{array}\right] \left[\begin{array}{cccccc} {\boldsymbol{x}}^{\prime}/\xi \\ 1 \end{array}\right] < 0 , $$

which contradicts (i). Alternatively, if ξ = 0, then (22) is reduced to

$$ {{\boldsymbol{x}}^{\prime}}^{\top} Q {\boldsymbol{x}}^{\prime} < 0 . $$

(23)

Put x = ηx^′ to see that the left-hand side of (i) is reduced to

$$ ({{\boldsymbol{x}}}^{\top} Q {\boldsymbol{x}}^{\prime}) \eta^{2} + 2 ({\boldsymbol{p}}^{\top} {\boldsymbol{x}}^{\prime}) \eta + \gamma , $$

(24)

which can be viewed as a quadratic function of η, when we fix x^′. It follows from (23) that (24) is not bounded below. Therefore, there exists an η such that (24) becomes negative, which contradicts (i). □

As an immediate corollary of Proposition 4 and Proposition 5, we can obtain the following fact.

Proposition 6

Suppose that A,$B \in {\mathcal {S}}^{n + 1}$satisfiesA ≱ 0 andB ≰ 0. Thefollowing two statements are equivalent:

• (a) $\displaystyle \left [\begin {array}{cccccc} x \\ 1 \end {array}\right ]^{\top } A \left [\begin {array}{cccccc} x \\ 1 \end {array}\right ] \le 0 \Rightarrow \displaystyle \left [\begin {array}{cccccc} x \\ 1 \end {array}\right ]^{\top } B \left [\begin {array}{cccccc} x \\ 1 \end {array}\right ] \le 0$ ,

• (b) ∃ν ≥ 0:A − νB ≽ 0.

Proof of Proposition 2

Observe that (17) can be rewritten equivalently as

$$\exists {\boldsymbol{q}} \in Q(\tilde{\alpha}) : K({\boldsymbol{x}}) {\boldsymbol{u}} = {\boldsymbol{q}} \quad\Rightarrow\quad |\sigma_{i}({\boldsymbol{u}})| \le \sigma_{{\mathrm{c}}}, $$

which is further rewritten as

$$ \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right]^{\top} \Psi({\boldsymbol{x}}) \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right] \le 0 \quad\Rightarrow\quad \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right]^{\top} G_{i} \left[\begin{array}{cccccc} {\boldsymbol{u}} \\ 1 \end{array}\right] \le 0 . $$

(25)

Since we assume rankK(x) = d, we have

$$\{ {\boldsymbol{u}} \in \mathbb{R}^{d} \mid \exists {\boldsymbol{q}} \in Q(\tilde{\alpha}) : K({\boldsymbol{x}}) {\boldsymbol{u}} = {\boldsymbol{q}} \} \not= \emptyset. $$

Therefore, Ψ(x) ≱ 0. Also, from the definition of G_i in (16), we see that G_i ≰ 0. Therefore, we can apply Proposition 6 to (25), which completes the proof. □