# Tractable Approximation to Robust Nonlinear Production Frontier Problem

Authors: Lei Wang; Xing Wang; Nan-jing Huang
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

Robust optimization is a rapidly developing methodology for handling optimization problems affected by the uncertain-but-bounded data perturbations. In this paper, we consider the nonlinear production frontier problem where the traditional expected linear cost minimization objective is replaced by one that explicitly addresses cost variability. We propose a robust counterpart for the nonlinear production frontier problem that preserves the computational tractability of the nominal problem. We also provide a guarantee on the probability that the robust solution is feasible when the uncertain coefficients obey independent and identically distributed normal distributions.


---

## Body

## 1. Introduction

Optimization is a leading methodology in engineering design and control. Recently therobust optimization methodology has been introduced and studied [1–10] in order to deal with uncertain optimization problems: those for which part or all of their parameters are uncertain or inexact, or those for which the computed optimal solution cannot be physically implemented exactly. For such problems, a solution based on nominal values of the parameters may deviate severely from feasibility or optimality.In robust optimization one is looking for a solution which satisfies the actual constraints for all possible realizations of the data within a fixed uncertainty set. This new problem is called therobust counterpart of the original problem. The robust counterpart is usually a semi-infinite optimization problem and in many cases can not be converted to explicitly convex optimization programs, solvable by high performance optimization techniques. For these cases the concept of an approximate robust counterpart was proposed by Ben-Tal and Nemirovski [1]. A solution of the approximate robust counterpart is always a robust solution of the original uncertain problem, and as shown in  [1, 4], it can often be computed efficiently.An increasingly active and challenging research area in growth and productivity studies is the nonsmooth frontier problems under a certain production technology as characterized with a production function,y=f(x), x∈X, where y∈ℝ is a scalar output and X⊂ℝ+n is a given set of input possibilities. The non-smooth frontier problems are triggered by facts, as first noted by Solow [11], the production growth in many industries and countries follows a lagging and non-smooth (e.g., stepwise) trajectory as a function of production inputs, such as investments in IT capital and human capital. The interests in the study of nonlinear and non-smooth frontiers were further intensified by the reports at an FOMC meeting in late 1996 that the negative trends in measured productivity observed in many services industries seemed inconsistent with the fact that they ranked among the top computer-using industries (Carrado and Slifman [12]). Similarly, the issue of the nonsmoothness has been encountered in logistics and supply-chain systems. For example, differing container/trailer standards and heterogeneous cargo-handling characteristics of ports have been identified as a major issue of efficiency in ocean transport and short sea shipping as well (Perakis and Denisis [13]). In a recent econometric study on port logistics by Yan et al. [14], it is empirically identified that some heterogeneous and time-variant production factors, such as geographic location and business structure, affect significantly the efficiency of global container ports. With the devoted efforts over the past two decades, productivity researchers have collectively identified two key characteristics of sources of non-smooth growth, namely, degenerative input and nonlinear production cost. A degenerative input is defined as the input that generates stepwise output, and nonlinear production cost is expressed in the form of ωTx+φ(x,D), where the nonlinear term φ(x,D) represents intangible cost, in addition to the standard linear cost ωTx and D is the vector of random coefficient. It shall be noted that production frontier problems studied so far assume a linear cost structure, that is, φ(x,D)≡0. Under the aforementioned nonlinear cost, a nonlinear production frontier problem is constructed herein in the form of a nonlinear-cost minimization problem:
(1.1)minxωTx+φ(x,D)s.t.x∈L(y)={x:f(x)≥y},∀y≥0.We define the nominal problem to be problem (1.1) when the random coefficient D takes value equal to its expected value D0. In order to protect the solution against infeasibility of problem (1.1), we may formulate the problem using chance constraint as follows:
(1.2)minx,ττs.t.P(ωTx+φ(x,D)≤τ)≥1-ϵ,x∈L(y)={x:f(x)≥y},∀y≥0.
It is well known that such chance constraint is nonconvex and generally intractable. However, we will solve a tractable problem and obtain a robust solution that is feasible to the chance constraint problem (1.2) when ϵ is very small and without having to increase the objective function excessively. In order to address problem (1.1), Ben-Tal and Nemirovski [1, 3] and independently by El-Ghaoui et al. [8, 9] propose to solve the following robust optimization problem(1.3)minx,ττs.t.ωTx+maxD∈𝒰φ(x,D)≤τ,x∈L(y)={x:f(x)≥y},∀y≥0,
where 𝒰 is a given uncertainty set. The motivation for solving problem (1.3) is to find a solution x*∈X that immunizes problem (1.1) against parameter uncertainty. That is, by selecting appropriate set 𝒰, we can find a solution x* to problem (1.3) that gives guarantee ϵ in problem (1.2). However, this is done at the expense of increasing the achievable objective. It is important to note that we describe uncertainty in problem (1.3) (using the set 𝒰) in a deterministic manner. In selecting uncertainty set 𝒰, we feel that two criteria are important. (a)
Preserve the computational tractability both theoretically and most importantly practically of the nominal problem. From a theoretical perspective it is desirable that if the nominal problem is solvable in polynomial time, then the robust problem is also polynomially solvable.(b)
Being able to find a guarantee on the probability that the robust solution is feasible, when the uncertain coefficients obey some natural probability distributions.Our goal in this paper is to address (a) and (b) above for robust nonlinear production frontier problem. Specially, we propose a new robust counterpart of problem (1.1) that has the following properties. (a) It inherits the character of the nominal problem; (b) under reasonable probabilistic assumptions on data variation we establish probabilistic guarantee for feasibility that lead to explicit ways for selecting parameters that control the robustness. The structure of this paper is as follows. In Section 2, we describe the proposed robust model and in Section 3, we show that the robust nonlinear production frontier problem can be presented in a tractable manner. In Section 4, we prove probabilistic guarantee for feasibility for this problem.


## 2. Preliminaries

In this section, we outline the ingredients of the proposed framework for robust nonlinear production frontier problem.


### 2.1. Model for Parameter Uncertainty

The model of data uncertainty we consider is(2.1)D=D0+Σj∈NΔDjuj,
where D0 is the nominal value of the data, ΔDj, j∈N is a direction of data perturbation, and uj, j∈N are independent and identically distributed random variables with mean equal to zero, so that E[D]=D0. The cardinality of N may be small, modeling situations involving a small collection of primitive independent uncertainties, or large, potentially as large as the number of entries in the data. In the former case, the elements of D are strongly dependent, while in the latter case the elements of D are weakly dependent or even independent (when |N| is equal to the number of entries in the data). The support of uj, j∈N can be unbounded or bounded. Ben-Tal and Nemirovski [3] and Bertsimas and Sim [6] have considered the case that |N| is equal to the number of entries in the data.


### 2.2. Uncertainty Set and Related Norm

In the robust optimization framework (1.3), we consider the uncertainty set 𝒰 as follows:
(2.2)𝒰={D∣∃u∈ℝ|N|:D=D0+Σj∈NΔDjuj,∥u∥≤Ω},
where Ω is a parameter, which Bertsimas and Sim [7] have showed, related to the probabilistic guarantee against infeasibility. Bertsimas and Sim [7] also restricted the vector norm ∥·∥ by imposing the condition:
(2.3)∥u∥=∥|u|∥,
where |u|=(|u1|,…,|u|N||)T if u=(u1,…,u|N|)T and they called such norm the absolute norm. Given a norm ∥·∥, we consider the dual norm ∥·∥* defined as
(2.4)∥s∥*=max∥x∥≤1sTx.We next show some basic properties of norms satisfying (2.3), which we will subsequently use in our development.Proposition 2.1 (see [7]).
The absolute norm satisfies the following.(1)
∥w∥*=∥|w|∥*;(2)
for allv, w such that |v|≤|w|, ∥v∥*≤∥w∥*;(3)
for allv, w such that |v|≤|w|, ∥v∥≤∥w∥.


### 2.3. The Class of Functionsφ(x,D)

We impose the following restrictions on the functionφ(x,D) in problem (1.1).Assumption 2.2.
The functionφ(x,D) satisfies (a)
the functionφ(x,D) is convex in D for all x∈ℝn;(b)
φ(x,kD)=kφ(x,D), for all k≥0, x∈ℝn. Let the functions satisfy Assumption 2.2. Then it is easy to see that
(2.5)φ(x,A+B)≤12φ(x,2A)+12φ(x,2B)=φ(x,A)+φ(x,B).


## 2.1. Model for Parameter Uncertainty

The model of data uncertainty we consider is(2.1)D=D0+Σj∈NΔDjuj,
where D0 is the nominal value of the data, ΔDj, j∈N is a direction of data perturbation, and uj, j∈N are independent and identically distributed random variables with mean equal to zero, so that E[D]=D0. The cardinality of N may be small, modeling situations involving a small collection of primitive independent uncertainties, or large, potentially as large as the number of entries in the data. In the former case, the elements of D are strongly dependent, while in the latter case the elements of D are weakly dependent or even independent (when |N| is equal to the number of entries in the data). The support of uj, j∈N can be unbounded or bounded. Ben-Tal and Nemirovski [3] and Bertsimas and Sim [6] have considered the case that |N| is equal to the number of entries in the data.


## 2.2. Uncertainty Set and Related Norm

In the robust optimization framework (1.3), we consider the uncertainty set 𝒰 as follows:
(2.2)𝒰={D∣∃u∈ℝ|N|:D=D0+Σj∈NΔDjuj,∥u∥≤Ω},
where Ω is a parameter, which Bertsimas and Sim [7] have showed, related to the probabilistic guarantee against infeasibility. Bertsimas and Sim [7] also restricted the vector norm ∥·∥ by imposing the condition:
(2.3)∥u∥=∥|u|∥,
where |u|=(|u1|,…,|u|N||)T if u=(u1,…,u|N|)T and they called such norm the absolute norm. Given a norm ∥·∥, we consider the dual norm ∥·∥* defined as
(2.4)∥s∥*=max∥x∥≤1sTx.We next show some basic properties of norms satisfying (2.3), which we will subsequently use in our development.Proposition 2.1 (see [7]).
The absolute norm satisfies the following.(1)
∥w∥*=∥|w|∥*;(2)
for allv, w such that |v|≤|w|, ∥v∥*≤∥w∥*;(3)
for allv, w such that |v|≤|w|, ∥v∥≤∥w∥.


## 2.3. The Class of Functionsφ(x,D)

We impose the following restrictions on the functionφ(x,D) in problem (1.1).Assumption 2.2.
The functionφ(x,D) satisfies (a)
the functionφ(x,D) is convex in D for all x∈ℝn;(b)
φ(x,kD)=kφ(x,D), for all k≥0, x∈ℝn. Let the functions satisfy Assumption 2.2. Then it is easy to see that
(2.5)φ(x,A+B)≤12φ(x,2A)+12φ(x,2B)=φ(x,A)+φ(x,B).


## 3. The Proposed Robust Framework and Its Tractability

Specifically, under the model of data uncertainty in (2.1), we propose the constraint for controlling the feasibility of stochastic data uncertainty in constraint (1.3) as follows:
(3.1)ωTx+max(v,w)∈𝒱{φ(x,D0)+Σj∈N(φ(x,ΔDj)vj+φ(x,-ΔDj)wj)}≤τ,
where
(3.2)𝒱={(v,w)∈ℝ+|N|×|N||∥v+w∥≤Ω},
and the norm ∥·∥ satisfies (2.3). We next show that under Assumption 2.2, (3.1) implies the classical definition of robustness:
(3.3)ωTx+φ(x,D)≤τ,∀D∈𝒰,
where 𝒰 is defined in (2.2). Moreover, if the function φ(x,D) is linear in D, then (3.1) is equivalent to (3.3).Proposition 3.1.
Suppose the given norm∥·∥ satisfies (2.3). (a)
Ifφ(x,A+B)=φ(x,A)+φ(x,B), then x satisfies (3.1) if and only if x satisfies (3.3).(b)
Under Assumption2.2, if x is feasible in problem (3.1), then x is feasible in problem (3.3).Proof.
(a) Under the linearity assumption, (3.1) is equivalent to
(3.4)ωTx+φ(x,D0+Σj∈NΔDj(vj-wj))≤τ,∀∥v+w∥≤Ω,v,w≥0,
while (3.3) can be written as
(3.5)ωTx+φ(x,D0+Σj∈NΔDjuj)≤τ,∀∥u∥≤Ω.
Suppose x is infeasible in (3.5). Then there exists u, ∥u∥≤Ω such that
(3.6)ωTx+φ(x,D0+Σj∈NΔDjuj)>τ.
For all j∈N, let vj=max{uj,0} and wj=-min{uj,0}. Clearly, r=v-w and since vj+wj=|uj|, we have from (2.3) that
(3.7)∥v+w∥=∥u∥≤Ω.
Hence, x is infeasible in (3.4) as well.
Conversely, supposex is infeasible in (3.4), then there exists v,w≥0 and ∥v+w∥≤Ω such that
(3.8)ωTx+φ(x,D0+Σj∈NΔDj(vj-wj))>τ.
For all j∈N, we let uj=vj-wj and we observe that |uj|≤vj+wj. Therefore, for norms satisfying (2.3), we have
(3.9)∥u∥=∥|u|∥≤∥v+w∥≤Ω,
and hence, x is infeasible in (3.5).
(b) Supposex is feasible in problem (3.1). Then
(3.10)ωTx+φ(x,D0)+Σj∈N{φ(x,ΔDj)vj+φ(x,-ΔDj)wj}≤τ,∀∥v+w∥≤Ω,v,w≥0.
From (2.5) and Assumption 2.2(3.11)τ≥ωTx+φ(x,D0)+Σj∈N{φ(x,ΔDj)vj+φ(x,-ΔDj)wj}≥ωTx+φ(x,D0+Σj∈NΔDj(vj-wj))
for all ∥v+w∥≤Ω and v,w≥0. In the proof of part (a), we showed that
(3.12)ωTx+φ(x,D0+Σj∈NΔDjuj)≤τ,∀∥u∥≤Ω
is equivalent to
(3.13)ωTx+φ(x,D0+Σj∈NΔDj(vj-wj))≤τ,∀∥v+w∥≤Ω,v,w≥0.
Thus x satisfies (3.3). This completes the proof.


### 3.1. Tractability of the Proposed Framework

Unlike the classical definition of robustness (3.3), which cannot be represented in a tractable manner, we next show that (3.1) can be represented in a tractable manner.Theorem 3.2.
For a norm satisfying (2.3) and a function φ(x,D) satisfying Assumption 2.2, the following statements hold.(a)
Constraint (3.1) is equivalent to
(3.14)ωTx+φ(x,D0)+Ω∥s∥*≤τ,
where
(3.15)sj=max{φ(x,ΔDj),φ(x,-ΔDj)},∀j∈N.(b)
Inequality (3.14) can be written as
(3.16)ωTx+φ(x,D0)+Ωm≤τ,φ(x,ΔDj)-tj≤0,∀j∈N,φ(x,-ΔDj)-tj≤0,∀j∈N,∥t∥*≤m,m∈ℝ,t∈ℝ|N|.Proof.
(a) First, we introduce the following problems:(3.17)z1=maxaTv+bTws.t.∥v+w∥≤Ω,v,w≥0,z2=max∑j∈N‍max{aj,bj,0}uj,s.t.∥u∥≤Ω.
In [7], Bertsimas and Sim showed that z1=z2. Therefore, we observe that
(3.18)max(v,w)∈𝒱∑j∈N‍{φ(x,ΔDj)vj+φ(x,-ΔDj)wj}=max∥u∥≤Ω∑j∈N‍{max{φ(x,ΔDj),φ(x,-ΔDj),0}uj}
and using the definition of dual norm, ∥s∥*=max∥x∥≤1sTx, we obtain that
(3.19)Ω∥s∥*=max∥x∥≤ΩsTx
and so (3.14) follows. Note that
(3.20)sj=max{φ(x,ΔDj),φ(x,-ΔDj)}≥0,
since otherwise there exists an x such that sj<0, that is,
(3.21)φ(x,ΔDj)<0,φ(x,-ΔDj)<0.
From Assumption 2.2(b) φ(x,0)=0, contradicting the convexity of φ(x,D) (Assumption 2.2(a)).
Suppose thatx is feasible in Problem (3.14). Defining t=s and m=∥s∥*, we can easily check that (x,t,m) are feasible in problem (3.16). Conversely, suppose that x is infeasible in (3.14), that is,
(3.22)ωTx+φ(x,D0)+Ω∥s∥*>τ.
Since
(3.23)tj≥sj=max{φ(x,ΔDj),φ(x,-ΔDj)}≥0,
we apply Proposition 2.1(b) to obtain ∥t∥*≥∥s∥* and so
(3.24)τ<ωTx+φ(x,D0)+Ω∥s∥*≤ωTx+φ(x,D0)+Ω∥t∥*≤ωTx+φ(x,D0)+Ωm.
Thus, x is infeasible in (3.16).
(b) It is immediate that (3.14) can be written in the form of (3.16).
This completes the proof.Remark 3.3.
In (1.1), let φ(x,D)=0 and L(yi)={x∣Aix+yi∈Ki},  i=1,…,m. Then the optimization problem (1.1) will be in the conic form:
(3.25)minxωTxs.t.Aix+yi∈Ki,i=1,…,m,
where, for every i,Ki is (i)
either a nonnegative orthantℝ+mi (linear constraints),(ii)
or the Lorentz coneLmi={z∈ℝmi∣zmi≥∑j=1mi-1‍zj2} (conic quadratic constraints),(iii)
or a semidefinite coneS+mi—the cone of positive semidefinite matrices in the space Smi of mi×mi symmetric matrices (Linear Matrix Inequality constraints).The class of problems which can be modeled in the form of (3.16) is extremely wide (see, e.g., [1–5]). It is also clear what is the structure and what are the data in (3.25)—the former is the design dimension n, the number of conic constraints m, and the list of the cones K1,…,Km, while the latter is the collection of matrices and vectors ω,{Ai,yi}i=1m of appropriate sizes. Thus, an uncertain problem of (3.16) is a collection,
(3.26)minx,ττs.t.τ-ωTx∈K0≡ℝ+,Aix+yi∈Ki,(ω,{Ai,yi}i=1m)∈𝒰*,i=1,…,m,
of instances (3.16) of a common structure {n,m,K1,…,Km} and data (ω,{Ai,yi}i=1m) varying in a given set 𝒰*. By specifying reasonable uncertainty sets 𝒰* in specific applications of Ki, Ben-Tal and Nemirovski [1–5] reformulate (3.26) as a computational tractable optimization problem, or at least approximate (3.26) by a tractable problem. Therefore, Theorem 3.2 generalizes model (3.16) from optimization problem with linear object function to a more widely nonlinear object function optimization problem.


### 3.2. Representation of the Functionmax{φ(x,ΔDj),φ(x,-ΔDj)}

The function(3.27)g(x,ΔDj)=max{φ(x,ΔDj),φ(x,-ΔDj)}
naturally arises in Theorem 3.2. Recall that a norm satisfies ∥A∥≥0, ∥kA∥=|k|·∥A∥, ∥A+B∥≤∥A∥+∥B∥, and ∥A∥=0 implies that A=0. We show next that the function g(x,A) satisfies all these properties except the last one, that is, it behaves almost like a norm.Proposition 3.4.
Under Assumption2.2, the function
(3.28)g(x,A)=max{φ(x,A),φ(x,-A)}
has the following properties: (a)
g(x,A)≥0;(b)
g(x,kA)=|k|g(x,A);(c)
g(x,A+B)≤g(x,A)+g(x,B).Proof.
(a) Suppose there existsx such that g(x,A)<0, that is, φ(x,A)<0 and φ(x,-A)<0. From Assumption 2.2(b) φ(x,0)=0, contradicting the convexity of φ(x,A) (Assumption 2.2(a)).
(b) Fork≥0, we apply Assumption 2.2(b) and obtain
(3.29)g(x,kA)=max{φ(x,kA),φ(x,-kA)}=kmax{φ(x,A),φ(x,-A)}=kg(x,A).
Similarly, if k<0 we have
(3.30)g(x,kA)=max{φ(x,-k(-A)),φ(x,-kA)}=-kg(x,A).
(c) Using (2.5) we obtain
(3.31)g(x,A+B)=g(x,12(2A+2B))≤12g(x,2A)+12g(x,2B)=g(x,A)+g(x,B).
This completes the proof.Note that the functiong(x,A) does not necessarily define a norm for A, since g(x,A)=0 does not necessarily imply A=0. However, for specific direction of data perturbation, ΔDj, we can map g(x,ΔDj) to a function of norm such that
(3.32)g(x,ΔDj)=∥ℋ(x,ΔDj)∥g,
where ℋ(x,ΔDj) is linear in ΔDj.


### 3.3. Example

We consider the robust quadratically frontier problem, that is,φ(x,D)=xTAx. Then it is easy to see that D=A, D0=A0, ΔDj=ΔAj, and the uncertainty set
(3.33)𝒰={A∣∃u∈ℝ|N|∣A=A0+Σj∈NΔAjuj,∥u∥≤Ω}.
It follows that
(3.34)g(x,ΔDj)=max{xTΔAjx,-xTΔAjx}=|xTΔAjx|
and so
(3.35)∥ℋ(x,ΔDj)∥g=|xTΔAjx|.
By Theorem 3.2, we know that the robust quadratic frontier problem
(3.36)minx,ττs.t.ωTx+maxA∈𝒰xTAx≤τ,x∈L(y)={x:f(x)≥y},∀y≥0,
is equivalent to the following tractable optimization problem
(3.37)minx,ττs.t.ωTx+xTA0x+Ω∥s∥*≤τ,x∈L(y)={x:f(x)≥y},∀y≥0,
where sj=|xTΔAjx|.


## 3.1. Tractability of the Proposed Framework

Unlike the classical definition of robustness (3.3), which cannot be represented in a tractable manner, we next show that (3.1) can be represented in a tractable manner.Theorem 3.2.
For a norm satisfying (2.3) and a function φ(x,D) satisfying Assumption 2.2, the following statements hold.(a)
Constraint (3.1) is equivalent to
(3.14)ωTx+φ(x,D0)+Ω∥s∥*≤τ,
where
(3.15)sj=max{φ(x,ΔDj),φ(x,-ΔDj)},∀j∈N.(b)
Inequality (3.14) can be written as
(3.16)ωTx+φ(x,D0)+Ωm≤τ,φ(x,ΔDj)-tj≤0,∀j∈N,φ(x,-ΔDj)-tj≤0,∀j∈N,∥t∥*≤m,m∈ℝ,t∈ℝ|N|.Proof.
(a) First, we introduce the following problems:(3.17)z1=maxaTv+bTws.t.∥v+w∥≤Ω,v,w≥0,z2=max∑j∈N‍max{aj,bj,0}uj,s.t.∥u∥≤Ω.
In [7], Bertsimas and Sim showed that z1=z2. Therefore, we observe that
(3.18)max(v,w)∈𝒱∑j∈N‍{φ(x,ΔDj)vj+φ(x,-ΔDj)wj}=max∥u∥≤Ω∑j∈N‍{max{φ(x,ΔDj),φ(x,-ΔDj),0}uj}
and using the definition of dual norm, ∥s∥*=max∥x∥≤1sTx, we obtain that
(3.19)Ω∥s∥*=max∥x∥≤ΩsTx
and so (3.14) follows. Note that
(3.20)sj=max{φ(x,ΔDj),φ(x,-ΔDj)}≥0,
since otherwise there exists an x such that sj<0, that is,
(3.21)φ(x,ΔDj)<0,φ(x,-ΔDj)<0.
From Assumption 2.2(b) φ(x,0)=0, contradicting the convexity of φ(x,D) (Assumption 2.2(a)).
Suppose thatx is feasible in Problem (3.14). Defining t=s and m=∥s∥*, we can easily check that (x,t,m) are feasible in problem (3.16). Conversely, suppose that x is infeasible in (3.14), that is,
(3.22)ωTx+φ(x,D0)+Ω∥s∥*>τ.
Since
(3.23)tj≥sj=max{φ(x,ΔDj),φ(x,-ΔDj)}≥0,
we apply Proposition 2.1(b) to obtain ∥t∥*≥∥s∥* and so
(3.24)τ<ωTx+φ(x,D0)+Ω∥s∥*≤ωTx+φ(x,D0)+Ω∥t∥*≤ωTx+φ(x,D0)+Ωm.
Thus, x is infeasible in (3.16).
(b) It is immediate that (3.14) can be written in the form of (3.16).
This completes the proof.Remark 3.3.
In (1.1), let φ(x,D)=0 and L(yi)={x∣Aix+yi∈Ki},  i=1,…,m. Then the optimization problem (1.1) will be in the conic form:
(3.25)minxωTxs.t.Aix+yi∈Ki,i=1,…,m,
where, for every i,Ki is (i)
either a nonnegative orthantℝ+mi (linear constraints),(ii)
or the Lorentz coneLmi={z∈ℝmi∣zmi≥∑j=1mi-1‍zj2} (conic quadratic constraints),(iii)
or a semidefinite coneS+mi—the cone of positive semidefinite matrices in the space Smi of mi×mi symmetric matrices (Linear Matrix Inequality constraints).The class of problems which can be modeled in the form of (3.16) is extremely wide (see, e.g., [1–5]). It is also clear what is the structure and what are the data in (3.25)—the former is the design dimension n, the number of conic constraints m, and the list of the cones K1,…,Km, while the latter is the collection of matrices and vectors ω,{Ai,yi}i=1m of appropriate sizes. Thus, an uncertain problem of (3.16) is a collection,
(3.26)minx,ττs.t.τ-ωTx∈K0≡ℝ+,Aix+yi∈Ki,(ω,{Ai,yi}i=1m)∈𝒰*,i=1,…,m,
of instances (3.16) of a common structure {n,m,K1,…,Km} and data (ω,{Ai,yi}i=1m) varying in a given set 𝒰*. By specifying reasonable uncertainty sets 𝒰* in specific applications of Ki, Ben-Tal and Nemirovski [1–5] reformulate (3.26) as a computational tractable optimization problem, or at least approximate (3.26) by a tractable problem. Therefore, Theorem 3.2 generalizes model (3.16) from optimization problem with linear object function to a more widely nonlinear object function optimization problem.


## 3.2. Representation of the Functionmax{φ(x,ΔDj),φ(x,-ΔDj)}

The function(3.27)g(x,ΔDj)=max{φ(x,ΔDj),φ(x,-ΔDj)}
naturally arises in Theorem 3.2. Recall that a norm satisfies ∥A∥≥0, ∥kA∥=|k|·∥A∥, ∥A+B∥≤∥A∥+∥B∥, and ∥A∥=0 implies that A=0. We show next that the function g(x,A) satisfies all these properties except the last one, that is, it behaves almost like a norm.Proposition 3.4.
Under Assumption2.2, the function
(3.28)g(x,A)=max{φ(x,A),φ(x,-A)}
has the following properties: (a)
g(x,A)≥0;(b)
g(x,kA)=|k|g(x,A);(c)
g(x,A+B)≤g(x,A)+g(x,B).Proof.
(a) Suppose there existsx such that g(x,A)<0, that is, φ(x,A)<0 and φ(x,-A)<0. From Assumption 2.2(b) φ(x,0)=0, contradicting the convexity of φ(x,A) (Assumption 2.2(a)).
(b) Fork≥0, we apply Assumption 2.2(b) and obtain
(3.29)g(x,kA)=max{φ(x,kA),φ(x,-kA)}=kmax{φ(x,A),φ(x,-A)}=kg(x,A).
Similarly, if k<0 we have
(3.30)g(x,kA)=max{φ(x,-k(-A)),φ(x,-kA)}=-kg(x,A).
(c) Using (2.5) we obtain
(3.31)g(x,A+B)=g(x,12(2A+2B))≤12g(x,2A)+12g(x,2B)=g(x,A)+g(x,B).
This completes the proof.Note that the functiong(x,A) does not necessarily define a norm for A, since g(x,A)=0 does not necessarily imply A=0. However, for specific direction of data perturbation, ΔDj, we can map g(x,ΔDj) to a function of norm such that
(3.32)g(x,ΔDj)=∥ℋ(x,ΔDj)∥g,
where ℋ(x,ΔDj) is linear in ΔDj.


## 3.3. Example

We consider the robust quadratically frontier problem, that is,φ(x,D)=xTAx. Then it is easy to see that D=A, D0=A0, ΔDj=ΔAj, and the uncertainty set
(3.33)𝒰={A∣∃u∈ℝ|N|∣A=A0+Σj∈NΔAjuj,∥u∥≤Ω}.
It follows that
(3.34)g(x,ΔDj)=max{xTΔAjx,-xTΔAjx}=|xTΔAjx|
and so
(3.35)∥ℋ(x,ΔDj)∥g=|xTΔAjx|.
By Theorem 3.2, we know that the robust quadratic frontier problem
(3.36)minx,ττs.t.ωTx+maxA∈𝒰xTAx≤τ,x∈L(y)={x:f(x)≥y},∀y≥0,
is equivalent to the following tractable optimization problem
(3.37)minx,ττs.t.ωTx+xTA0x+Ω∥s∥*≤τ,x∈L(y)={x:f(x)≥y},∀y≥0,
where sj=|xTΔAjx|.


## 4. Probabilistic Guarantee

In this section, we derive a guarantee on the probability that the robust solution is feasible, when the uncertain coefficients obey some natural probability distributions. An important component of our analysis is the relation among different norms. We denote by〈·,·〉 the inner product on a vector space, RM, or the space of m by m symmetric matrices, Sm×m. The inner product induces a norm 〈x,x〉. For a vector space, the natural inner product is the Euclidian inner product, 〈x,y〉=xTy, and the induced norm is the Euclidian norm ∥x∥2.We analyze the relation of the inner product norm〈x,x〉 with the norm ∥x∥g defined in (3.32). Since ∥x∥g and 〈x,x〉 are valid norms in a finite dimensional space, there exist finite α1,α2>0 such that
(4.1)1α1∥r∥g≤〈r,r〉≤α2∥r∥g
for all r in the relevant space.Theorem 4.1.
Under the model of uncertainty in (2.1) and given a feasible solution x in (3.1), then
(4.2)P(ωTx+φ(x,D)≤τ)≤P(∥∑j∈N‍rjuj∥g>Ω∥s∥*),
where
(4.3)rj=ℋ(x,ΔDj),sj=∥rj∥g,j∈N.Proof.
From the assumptions, it is easy to see that(4.4)P(ωTx+φ(x,D)>τ)≤P(ωTx+φ(x,D0)+φ(x,Σj∈NΔDjuj)>τ)(from(2.5))≤P(φ(x,Σj∈NΔDjuj)>Ω∥s∥*)(from(3.14),sj=∥ℋ(x,ΔDj)∥g)≤P(max{φ(x,Σj∈NΔDjuj),φ(x,-Σj∈NΔDjuj)}>Ω∥s∥*)=P(g(x,Σj∈NΔDjuj)>Ω∥s∥*)=P(∥ℋ(x,Σj∈NΔDjuj)∥g>Ω∥s∥*)=P(∥Σj∈Nℋ(x,ΔDj)uj∥g>Ω∥s∥*)(ℋ(x,D)islinearinD)=P(∥∑j∈N‍rjuj∥g>Ω∥s∥*).
This completes the proof.We are naturally led to bound the probabilityP(∥Σj∈Nrjuj∥g>Ω∥s∥*). When we use l2-norm in (3.2), that is, ∥s∥*=∥s∥2, we have
(4.5)P(∥Σj∈Nrjuj∥g>Ω∥s∥*)=P(∥Σj∈Nrjuj∥g>Ω∑j∈N‍∥rj∥g2).By the similar method used in Bertsimas and Sim [7], we can get the following result which provides a bound that is independent of the solution x.Theorem 4.2.
Using thel2-norm in (3.2) and under the assumption that uj are normally and independently distributed with mean zero and variance one, that is, u~𝒩(0,1), then
(4.6)P(∥∑j∈N‍rjuj∥g>Ω∑j∈N‍∥rj∥g2)≤eΩαexp(-Ω22α2),
where α=α1α2 and α1, α2 derived in (4.1) with Ω>α.



---

*Source: 965835-2012-10-11.xml*