DOI 10.4134/JKMS.2010.47.1.017
DUALITY FOR LINEAR CHANCE-CONSTRAINED OPTIMIZATION PROBLEMS
Radu Ioan Bot ¸, Nicole Lorenz, and Gert Wanka
Abstract. In this paper we deal with linear chance-constrained opti- mization problems, a class of problems which naturally arise in practical applications in finance, engineering, transportation and scheduling, where decisions are made in presence of uncertainty. After giving the determin- istic equivalent formulation of a linear chance-constrained optimization problem we construct a conjugate dual problem to it. Then we provide for this primal-dual pair weak sufficient conditions which ensure strong duality. In this way we generalize some results recently given in the litera- ture. We also apply the general duality scheme to a portfolio optimization problem, a fact that allows us to derive necessary and sufficient optimality conditions for it.
1. Introduction
Stochastic programming is an important topic in the optimization theory with applications in various fields like financial systems, engineering, location and transportation problems or the study of physical and chemical systems.
The optimization problems occurring in all these fields usually contain uncer- tain variables either in the objective functions or in the constraints or even in both. The interest in optimization under uncertainty was revived in the 1950s and is still of importance. We refer for an overview on stochastic programming to [16].
In this paper we work with stochastic programming problems with deter- ministic objective functions and chance (probabilistic)-constraints, a class of problems that has been first investigated by Charnes and Cooper in [6, 7, 8].
Other authors which dealt with such problems very early were van de Panne and Popp in [18] and Kataoka in [12]. The problem we consider in this article
Received December 10, 2007; Revised February 9, 2009.
2000 Mathematics Subject Classification. 49N15, 90C46, 46N10.
Key words and phrases. stochastic programming, conjugate duality, optimality condi- tions, chance-constraints, portfolio optimization.
c
°2010 The Korean Mathematical Society
17
is
(P mix ) inf f (x),
s.t. P(g i (x) ≤ 0) ≥ 1 − α i , i = 1, . . . , m, h j (x) ≤ 0, j = 1, . . . , k,
x ∈ R n
where f and h j , j = 1, . . . , k, are convex functions while g i , i = 1, . . . , m, are linear functions with random values. These constraints are called single chance-constraints since individual probabilities ensure that every inequality holds.
In many papers the use of the theory of chance-constraints in practical appli- cations is considered and in this setting the case of the single chance-constraints play an important role. Single chance-constraints may be for instance used when some constraints are more critical then other ones. Practical applica- tions using single chance-constraints have been given e.g. for portfolio opti- mization problems (cf. [4]), but also for problems in production, transport and operations planning.
The approach considered in this paper assumes giving a deterministic equiv- alent formulation of the linear single chance-constraints (see [4, 7, 11]). This transforms (P mix ) into a convex deterministic optimization problem. To this aim one has to assume that the distribution of the uncertain variables is known.
In this paper we even postulate a normal distribution, but in general also other distributions can be considered (cf. [1, 5, 9]). It is worth mentioning that in general the chance-constraints can be assumed to be also nonlinear, even if in this case the determining of their distribution functions could be a difficult task.
The paper is organized as follows. In the next section we introduce some definitions and notations from the convex analysis and employ some results from the stochastic theory in order to give an equivalent deterministic formula- tion to (P mix ). In Section 3 we construct a conjugate dual to (P mix ) and give a strong duality theorem along with a regularity condition which guarantees it.
As a special case of (P mix ) we consider first in Section 4 an optimization prob-
lem with linear objective function and linear (chance)-constraints and provide
a dual problem to it. In this way we rediscover and extend a result recently
given by Scott and Jefferson in [17], which turns out to be a special case of our
considerations. As a practical application to financial mathematics we further
provide the dual of a portfolio optimization problem with chance-constraints
by means of the general duality scheme and derive necessary and sufficient
optimality conditions for it. The last section gives some directions for future
research.
2. Preliminary notions and results
In this section we introduce some notations we use within the paper along with some well-known results. Throughout this paper all the vectors are con- sidered as being column vectors. An upper index T transposes a column vector into a row one and viceversa. For two arbitrary vectors x, y ∈ R n the usual in- ner product in the n-dimensional real space is denoted by x T y. For i = 1, . . . , n by e i we denote the i-th unit vector in R n and by e = (1, . . . , 1) T ∈ R n .
The prefix ri is used for the relative interior of a set, while for the effec- tive domain of a function f : R n → R := R ∪ {±∞} we use the notation dom(f ) = {x ∈ R n : f (x) < +∞}. The function f is said to be proper if dom(f ) 6= ∅ and f (x) > −∞ ∀x ∈ R n . For f : R n → R we consider the conjugate function relative to the nonempty set D ⊆ R n that is defined by f D ∗ (x ∗ ) = sup x∈D {x T x ∗ − f (x)}. Obviously, for D = R n , f D ∗ becomes the (Fenchel-Moreau) conjugate function of f , which is denoted by f ∗ . For an opti- mization problem (P ) we denote by v(P ) its optimal objective value. We write min (max) instead of inf (sup) if the infimum (supremum) is attained.
Let (Ω, F, P) be a probability space, where Ω is a basic space, F a σ-algebra on Ω and P a probability measure on the measurable space (Ω, F). Furthermore, let L 2 be the following space of random variables:
L 2 := L 2 (Ω, F, P, R) =
½
x : Ω → R, x measurable, Z
Ω
x(ω) 2 dP(ω) < +∞
¾ . By η ∼ N (0, 1) we denote a standard normal distributed random variable.
For z ∈ R it holds P(η ≤ z) = Φ(z) and P(z ≤ η) = 1 − Φ(z), where Φ is the distribution function of the standard normal distribution. For θ ∼ N (µ, σ 2 ) we have θ−µ σ ∼ N (0, 1) and so
P(θ ≤ z) = P
µ θ − µ
σ ≤ z − µ σ
¶
= Φ µ z − µ
σ
¶ .
Let K α := Φ −1 (1 − α) be the (1 − α)-quantile of the standard normal distri- bution, which is a positive number when α ∈ (0, 0.5].
For x, y two random variables we denote by E(x) the expected value of x, by D 2 (x) its variance and by cov(x, y) = E((x − E(x))(y − E(y)) the covariance between x and y. Let a j ∈ L 2 , j = 1, . . . , n and b ∈ L 2 be normal distributed random variables. We denote a := (a 1 , . . . , a n ) and introduce the notation E(a) := (E(a 1 ), . . . , E(a n )) T for the vector having as components the expected value of the components of a. For x ∈ R n let be a T x := P n
j=1 a j x j . The symmetric positive semidefinite so-called variance-covariance matrix of a will be denoted by
Σ(a) =
D 2 (a 1 ) cov(a 1 , a 2 ) . . . cov(a 1 , a n ) cov(a 2 , a 1 ) D 2 (a 2 ) . . . cov(a 2 , a n )
.. . . .. .. .
cov(a n , a 1 ) . . . . . . D 2 (a n )
.
Next we assume a multinormal distribution a j , j = 1, . . . , k, and b and define the function g : R n → L 2 by g(x) := a T x − b. For α ∈ (0, 0.5] we con- sider the following chance-constraint P(g(x) ≤ 0) ≥ 1 − α. Since for x ∈ R n g(x) is a linear combination of normal distributed random variables, it has an (one-dimensional) joint normal distribution with the expected value E(g(x)) = P n
j=1 E(a j )x j − E(b) = x T E(a) − E(b).
Let be further C(a, b) := (cov(a 1 , b), . . . , cov(a n , b)) T ∈ R n . The n + 1-tuple (a 1 , . . . , a n , b) of random variables has a normal distribution and a symmetric positive semidefinite variance-covariance matrix
(1) S(a, b) :=
µ Σ(a) C(a, b) C(a, b) T D 2 (b)
¶
∈ R (n+1)×(n+1) .
Then g(x) has as variance D 2 (g(x)) := z(x) T S(a, b)z(x) = x T Σx−2C(a, b) T x+
D 2 (b), where z(x) := (x 1 , . . . , x n , −1) T ∈ R n+1 , and, consequently, it holds D 2 (g(x)) ≥ 0 for all x ∈ R n . Therefore the standard deviation of g(x) is D(g(x)) = p
z(x) T S(a, b)z(x) = p
x T Σ(a)x − 2C T (a, b)x + D 2 (b).
As well-known from the literature the constraint P(g(x) ≤ 0) ≥ 1 − α has as equivalent deterministic formulation ˜ g(x) := E(g(x)) + D(g(x)) · K α ≤ 0. It also holds P(g(x) ≤ 0) > 1 − α ⇔ E(g(x)) + D(g(x)) · K α < 0. As mentioned above, for α ∈ (0, 0.5] one has K α > 0. In this situation the function ˜ g turns out to be a convex function (cf. [12, 14, 18]).
Let us mention that one can also consider in this setting distributions in the chance-constraints that are different from the normal one, like the elliptical symmetric and the log-concave symmetric distributions (cf. [10, 13]). In this situations an equivalent deterministic reformulation of the chance-constraints is possible, too.
On can notice that the function f : R n → R, f (x) =
q
x T Σ(a)x − 2C(a, b) T x + D 2 (b),
with a = (a 1 , . . . , a n ), b, Σ(a) and C(a, b) as above, will play an important role in our investigations. The calculation of its conjugate function is not a trivial task and employs some knowledge from the convex duality theory. This leads for all x ∗ ∈ R n to the following formula
f ∗ (x ∗ ) = min
λ
2∈R {λ 2 + s ∗ (x ∗ , λ 2 )}, where by s : R n → R we denote the function s(x) = p
x T S(a, b)x for all x ∈ R n . For an arbitrary λ ∈ R n+1 we have that s ∗ (λ) = 0 if there exists w ∈ R n+1 such that λ = S(a, b)w and w T S(a, b)w ≤ 1 and s ∗ (λ) = +∞ otherwise. This provides the following formula for the conjugate of f for all x ∗ ∈ R n :
f ∗ (x ∗ ) = min
u∈R
n,v∈R, x
∗=Σ(a)u+C(a,b)v, u
TΣ(a)u+2vC(a,b)
Tu+v
2D
2(b)≤1
{C(a, b) T u + D 2 (b)v}.
3. Duality for the chance-constrained problem
In this section we develop a duality scheme for the optimization problem with mixed (chance- and convex) constraints:
(P mix ) inf f (x).
s.t. P(g i (x) ≤ 0) ≥ 1 − α i , i = 1, . . . , m, h j (x) ≤ 0, j = 1, . . . , k,
x ∈ R n
To this aim we assume that f : R n → R and h j : R n → R, j = 1, . . . , k, are convex functions and that g i : R n → L 2 are defined by g i (x) = P n
j=1 a ij x j − b i = a T i x − b i for i = 1, . . . , m,. Here a ij , b i ∈ L 2 , i = 1, . . . , m, j = 1, . . . , m, are random variables, α i ∈ (0, 0.5] and a i := (a i1 , . . . , a in ) for i = 1, . . . , m.
The investigations done in this section concerning (P mix ) extend the ones recently made by Scott and Jefferson in [17]. As a byproduct, by using the dual- ity theory, we derive in the following section necessary and sufficient optimality conditions for the portfolio optimization problem with chance-constraints.
We start by noticing that, keeping the notation from the previous section, the problem (P mix ) can be equivalently written as:
(P mix ) inf f (x).
s.t. x T E(a i )−E(b i )+ p
x T Σ(a i )x−2C(a i , b i ) T x + D 2 (b i ) · K αi≤ 0, i = 1, . . . , m,
h j (x) ≤ 0, j = 1, . . . , k, x ∈ R n
For further calculations we denote for i = 1, . . . , m by f i : R n → R and ˜ g i : R n → R the functions defined as f i (x) = p
x T Σ(a i , b i )x−2C(a i , b i ) T x + D 2 (b i ) and ˜ g i (x) = E(g i (x))+D(g i (x))·K αi, respectively. Let also be ˜ g := (˜ g 1 , . . . , ˜ g m ) T and h := (h 1 , . . . , h k ) T . First we construct the Lagrange dual problem to (P mix ).
This has the following formulation (D mix ) sup
β∈R
m+,γ∈R
k+x∈R infn{f (x) + β T g(x) + γ ˜ T h(x)}
or, equivalently,
(D mix ) sup
β∈R
m+,γ∈R
k+½
−
f + X m
i=1
β i K α
if i + X k
j=1
γ j h j
∗ Ã
− X m
i=1
β i E(a i )
!
− X m
i=1
β i E(b i )
¾ .
For the conjugates of f i , i = 1, . . . , k, one can use now the formula given in
the previous section. On the other hand, the conjugate of the sum of convex
functions can be written in this setting as being equal to the infimal convolu-
tion of the conjugates of the summands (cf. [15]). Consequently, after some
calculations and transformations we obtain the following dual problem:
(D mix ) sup
β
i∈R
+,u
i∈R
n,v
i∈R, u
TiΣ(a
i)u
i+2v
iC(a
i,b
i)
Tu
i+v
i2D
2(b
i)≤1,i=1,...,m, γ
j∈R
+,q
j∈R
n,j=1,...,k
8 <
: −f
∗„
− X
mi=1
β
i[E(a
i) + K
αi(Σ(a
i)u
i+ C(a
i, b
i)v
i)] − X
kj=1
γ
jq
j«
− X
mi=1
β
iE(b
i) − X
mi=1
β
iK
αi[C(a
i, b
i)
Tu
i+ D
2(b
i)v
i] − X
kj=1
γ
jh
∗j(q
j) 9 =
; .
For having strong duality for the primal-dual pair (P mix ) − (D mix ) one needs to have a constraint qualification fulfilled. In our situation it is enough to demand that (see [15])
(CQ mix ) ∃x 0 ∈ ri(dom(f )) :
˜
g i (x 0 ) < 0, i = 1, . . . , m, h j (x 0 ) ≤ 0, j ∈ L, h j (x 0 ) < 0, j ∈ N
is fulfilled, where L = {j ∈ {1, . . . , k} : h j is affine} and N = {1, . . . , k} \ L. It is easy to see that this constraint qualification can be equivalently written as
(CQ mix ) ∃x 0 ∈ ri(dom(f )) :
P(g i (x 0 ) ≤ 0) > 1 − α i , i = 1, . . . , m, h j (x 0 ) ≤ 0, j ∈ L,
h j (x 0 ) < 0, j ∈ N.
Now we can state the so-called strong duality theorem.
Theorem 3.1 (strong duality for (P mix )−(D mix )). Let us assume that (CQ mix ) is fulfilled. Then it holds v(P mix ) = v(D mix ) and the dual (D mix ) has an optimal solution.
4. Particular cases
Within this section we show first how a recent result due to Scott and Jef- ferson follows as a particular case of our general duality scheme, while in the second part we derive necessary and sufficient optimality conditions for a port- folio optimization problem with linear chance-constraints.
4.1. The linear case
Consider the optimization problem (P lin ) inf a T x,
s.t. P Ã P n
j=1
a ij x j ≤ b i
!
≥ 1 − α i , i = 1, . . . , m, x = 0
where a ∈ R n and a ij , b i ∈ L 2 , i = 1, . . . , m, j = 1, . . . , m are random variables,
α i ∈ (0, 0.5] and a i := (a i1 , . . . , a in ) for i = 1, . . . , m.
A dual problem to (P lin ) will be constructed by applying the general theory in Section 3, namely by particularizing (D mix ). This will have the following formulation
(D lin ) sup
β
i∈R
+,u
i∈R
n,v
i∈R, u
TiΣ(a
i)u
i+2v
iC(a
i,b
i)
Tu
i+v
2iD
2(b
i)≤1,
i=1,...,m,
− P
mi=1
β
i[E(a
i)+K
αi(Σ(a
i)u
i+C(a
i,b
i)v
i)]
− P
nj=1
γ
jq
j=a,γ
j∈R
+,q
j=−e
j,j=1,...,n
½
− P m
i=1
β i [µ i b + K α
i(C(a i , b i ) T u i + D 2 (b i )v i )]
¾
or, equivalently,
(D lin ) sup
β
i∈R
+,u
i∈R
n,v
i∈R, u
TiΣ(a
i)u
i+2v
iC(a
i,b
i)
Tu
i+v
2iD
2(b
i)≤1,i=1,...,m, a+ P
mi=1
β
i[E(a
i)+K
αi(Σ(a
i)u
i+C(a
i,b
i)v
i)]≥0
½
− P m
i=1
β i [E(b i ) + K α
i(C(a i , b i ) T u i + D 2 (b i )v i )]
¾ .
A particular instance of (P lin ) was recently treated by Scott and Jefferson in [17] by means of geometric programming duality. The primal problem in the probabilistic formulation is given in the form of (P lin ) while the deterministic equivalent formulation of it is
(P lin,SJ ) inf a T x.
s.t. x T E(a i ) − b i + K αi
p x T Σ(a i )x ≤ 0, i = 1, . . . , k, x T a i − E(b i ) + K αiD(b i ) ≤ 0, i = k + 1, . . . , m, x = 0
In [17] the authors actually suppose that for 1 < k < m, a ij , j = 1, . . . , n, are normal distributed for i = 1, . . . , k and deterministic for i = k + 1, . . . , m, while b i are normal distributed for i = k + 1, . . . , m and deterministic for i = 1, . . . , k.
Further, Σ(a i ) are assumed to be positive definite for i = 1, . . . , k . This implies that
D 2 (b i ) = 0 and E(b i ) = b i , ∀i ≤ k, Σ(a i ) = 0 and E(a i ) = a i , ∀i ≥ k + 1, C(a i , b i ) = 0, ∀i = 1, . . . , m.
(2)
The dual (D lin ) provides under the usage of (2) the following dual problem to (P lin,SJ )
(D lin,SJ ) sup
β
i∈R
+,u
i∈R
n,u
TiΣ(a
i)u
i≤1, i=1,...,k,v
i∈R,v
2iD
2(b
i)≤1,i=k+1,...,m, a+ P
ki=1
β
i[E(a
i)+K
αiΣ(a
i)u
i]+ P
m i=k+1β
ia
i≥0
½
− P k
i=1
β i b i − P m
i=k+1
β i [E(b i ) + K α
iD 2 (b i )v i ]
¾
.
Some further treatments (in particular introducing the new variables p i :=
−β i K αiΣ i u i for i = 1, . . . , k) yield the following formulation of the dual prob- lem to (P lin,SJ )
(D lin,SJ ) sup
β
i∈R
+,p
i∈R
n, √
p
TiΣ(a
i)
−1p
i≤β
iK
αi, i=1,...,k,a+ P
ki=1
β
iE(a
i)− P
ki=1
p
i+ P
mi=k+1
β
ia
i≥0
½
− P k
i=1
β i b i − P m
i=k+1
β i [E(b i ) − K α
iD(b i )]
¾ .
The constraint qualification given in Section 3 becomes in this special case:
(CQ lin,SJ ) ∃x 0 ∈ R n + :
½ P(a T i x 0 − b i ≤ 0) > 1 − α i , i = 1, . . . , k, P(a T i x 0 − b i ≤ 0) ≥ 1 − α i , i = k + 1, . . . , m.
Theorem 4.1 (strong duality (P lin,SJ ) − (D lin,SJ ) ). Let us assume that (CQ lin,SJ ) is fulfilled. Then it holds v(P lin,SJ ) = v(D lin,SJ ) and (D lin,SJ ) has an optimal solution.
Remark 4.1. With the exception of a sign in the objective function, Scott and Jefferson give in [17] for (P lin,SJ ) the same dual optimization problem as (D lin,SJ ). Nevertheless, in that paper the problem of giving sufficient regularity conditions or of stating a strong duality theorem is not addressed.
4.2. Application to portfolio optimization theory
In this part we consider a portfolio optimization problem for which we derive necessary and sufficient optimality conditions as an application of the gen- eral duality scheme developed in Section 3. We assume that n + 1 assets are given, where the first one is riskless with the riskless return r 0 = E(r 0 ).
The return of asset j is given by the random variable r j ∈ L 2 with an ex- pected return of E(r j ) for j = 1, . . . , n. We denote by E(r) the vector E(r) :=
(E(r 0 ), E(r 1 ), . . . , E(r n )) T . Further let Σ(r) ∈ R (n+1)×(n+1) be the symmetric positive semidefinite variance-covariance matrix of r := (r 0 , r 1 , . . . , r n ) T . The classical portfolio optimization problem has the following formulation
(P po ) inf f (x).
s.t. x 0 E(r 0 ) + P n
j=1
x j E(r j ) ≥ b, P n
j=0
x j = 1,
x = (x 0 , x 1 , . . . , x n ) T = 0
where x = (x 0 , x 1 , . . . , x n ) T is the vector having as components the proportions of the assets in the whole portfolio, f : R n → R is a function measuring the risk of the portfolio (e.g. the variance or any deviation or risk measure).
Here b ∈ R is a return benchmark and in our approach should be assumed to be a constant random variable in L 2 . Let g : R n+1 → L 2 be defined by g(x) = b− P n
j=0 x j r j = b−x T r. We have E(g(x)) = b−x T E(r) and D 2 (g(x)) =
x T Σ(r)x for all x ∈ R n+1 . When applying the previous model to this particular situations one has to take C(r, b) = 0 and D(b) = 0.
Remark 4.2. As proved in the previous section, one can construct a dual prob- lem and also provide necessary and sufficient optimality conditions even if it considers that b is a random variable in L 2 . This is of importance if our target is to construct a portfolio that hits or at least reaches any benchmark port- folio or market index (e.g. the DAX (Deutscher Aktienindex)) with a certain probability. Therefore one can consider b = P n
j=1 y j r j with given and fixed proportions y j ∈ (0, 1), j = 1, . . . , n, and random returns r j , j = 1, . . . , n, as above.
The following portfolio optimization problem with mixed (linear and chance-) constraints was treated in [4]
(P pomix ) inf f (x), s.t. P
Ã
x 0 r 0 + P n
j=1
x j r j ≥ b
!
≥ 1 − α, P n
j=0
x j = 1,
x = (x 0 , x 1 , . . . , x n ) T = 0
where for f the variance of the portfolio return was considered. Here we let f being the standard deviation f (x) = p
x T Σ(r)x, x ∈ R n+1 . Its equivalent deterministic formulation is
(P pomix ) inf f (x),
s.t. b − x T E(r) + K α
p x T Σ(r)x ≤ 0, P n
j=0
x j = 1,
x = (x 0 , x 1 , . . . , x n ) T = 0
By means of the general considerations made in Section 3 we obtain the following dual problem to (P pomix )
(D pomix ) sup
β∈R
+,u,w∈R
n+1,u
TΣ(r)u≤1,w
TΣ(r)w≤1, γ
j∈R
+,j=0,...,n+2,
−β(−E(r)+K
αΣ(r)u)+ P
nj=0