# Exact Penalization in Stochastic Programming—Calmness and Constraint Qualification

Authors: Martin Branda
Journal: Advances in Decision Sciences
 (2014)

---

## Abstract

We deal with the conditions which ensure exact penalization in stochastic programming problems under finite discrete distributions. We give several sufficient conditions for problem calmness including graph calmness, existence of an error bound, and generalized Mangasarian-Fromowitz constraint qualification. We propose a new version of the theorem on asymptotic equivalence of local minimizers of chance constrained problems and problems with exact penalty objective. We apply the theory to a problem with a stochastic vanishing constraint.


---

## Body

## 1. Introduction

Constraints of real life optimization problems often depend on a random vector. If we know its probability distribution or if we have a good estimate, we can use various stochastic programming formulations to solve the problem and to get a highly reliable solution with respect to the realizations of the random vector. In chance constrained programming problems, a probability for fulfilling the random constraints is prescribed; see Prékopa [1, 2] for an extensive review of the main results. In general, chance constrained problems are difficult to solve. Below, we give an overview of the main recent results in this area. P-level efficient points (pLEPs) introduced by Prékopa [3] can be seen as generalizations of the quantiles for multivariate probabilistic distributions and have been shown to be useful for solving chance constrained problems with random right-hand sides. The new definition of pLEPs proposed by Lejeune [4] uses elements from the combinatorial pattern recognition field. He demonstrated that the collection of pLEPs can be represented as a disjunctive normal form (DNF) and proposed a mixed-integer programming formulation allowing for the construction of the DNF. Bruni et al. [5] presented a heuristic approach EXPRESS for solving mixed-integer programming formulations of chance constrained problems. The heuristic is based on alternating phases of exploration using simplified integer problems and feasibility repairing using penalization. Computational results on a probabilistically constrained version of the multiknapsack problem confirmed good solution quality and time performance of the heuristic. Dentcheva and Martinez [6] analyzed nonlinear stochastic optimization problems with probabilistic constraints described by continuously differentiable nonconvex functions. They described the tangent and the normal cone to the level sets of the probability function and formulated first- and second-order optimality conditions. Moreover, they developed an augmented Lagrangian method for discrete distributions. Henrion and Möller [7] provided an explicit gradient formula for linear chance constraints under a multivariate Gaussian distribution and used the formula to solve a transportation network problem with stochastic demands. An important property of the feasibility set is convexity which can be ensured, for example, by log-concavity of the underlying distribution; see Shapiro et al. [8] for a review and generalizations. A recent result in this area has been proposed by Ninh and Prékopa [9] who investigated log-concavity of the compound distributions, which have many applications in insurance, finance, hydrology, and so forth. Sample approximation techniques were studied by Luedtke and Ahmed [10], Branda [11] who derived exponential rates of convergence of the approximated solutions to the true one. Convergence of approximated probabilistic functions expressed as quantiles is investigated also by Miao et al. [12]. The underlying probability distribution is usually not known precisely and possible influence of its improper choice has to be investigated. Dupačová and Kopa [13] accessed robustness of the probabilistic risk functions using the contamination technique and derived approximate contamination bound for the optimal value.In this paper, we investigate an approach which uses penalized random constraints incorporated into the objective function. It can be verified that under some conditions we obtain an optimal solution with desirable reliability by increasing the penalty parameter and solving the resulting problems. It can be even shown that under mild conditions the penalty approach and the chance constrained problem are asymptotically equivalent; see Branda [14, 15], Branda and Dupačová [16], and Ermoliev et al. [17]. Recently, the equivalence was stated under exact penalization where a finite penalty parameter is sufficient to obtain a local optimal solution which is permanently feasible with respect to the random constraints; see Branda [18]. The exact penalization property is ensured by a very general calmness property of the underlying optimization problem; compare Burke [19, 20], Clarke [21]. However, it is difficult or even impossible to verify the problem calmness directly. Thus, in this paper, some necessary conditions for stochastic programming problems are introduced and discussed. These conditions are based on the relations between constraint set calmness, local error bound property, and constraint qualification conditions. Moreover, we perform the whole analysis on the problems with general abstract constraints. This setting is important, for example, for the problems with vanishing constraints which are extended in this paper to take into account randomness. The deterministic case was considered, for example, by Hoheisel et al. [22].There is an extensive development of the exact penalty methods for deterministic optimization in recent years. Antczak [23] established the exactness of the l
1 penalty function method used for solving nonsmooth constrained optimization problems with both inequality and equality constraints under locally Lipschitz invexity assumptions. Antczak [24] used the exact minimax penalty function method for solving a general nondifferentiable extremum problem with both inequality and equality constraints. Lian and Han [25] proposed a method to smooth the square-order exact penalty function for inequality constrained optimization and showed convergence of their algorithm under mild conditions. Liu et al. [26] solved nonconvex optimization problems using a penalty algorithm based on smooth functions that approximate the usual exact penalty function. Under a generalized Mangasarian-Fromovitz constraint qualification condition they proved the convergence of the generated points to Karush-Kuhn-Tucker points of the original problem. Zaslavski [27] developed an approach in order to prove the existence of an exact penalty involving Palais-Smale condition and nonexistence of a solution which is a critical point for the constraint map. In his recent paper, Zaslavski [28] studied a class of constrained minimization problems on complete metric spaces; he established the generalized exact penalty property and obtained an estimate of the exact penalty. Applications of the exact penalty method in stochastic programming are limited to problems with second-order stochastic dominance constraints; see Meskarian et al. [29], Sun et al. [30].The paper is organized as follows. The basic notation and problem formulations are proposed in Section2. In Section 3, the necessary conditions for the problem calmness are summarized. In Section 4, we propose a theorem which states an asymptotic equivalence of the chance constrained problems and problems with exact penalty objective. An example of the problem with a stochastic vanishing constraint is given in Section 5. Section 6 concludes the paper.


## 2. Problem Statement

Letξ be a real random vector on the probability space (
Ω
,
ℱ
,
P
) with values in ℝ
k and known probability measure P. A general chance constrained problem with an abstract random constraint can be formulated as
(1)
ψ
ε
=
min
⁡
x
f
(
x
)
s
.
t
.
P
(
F
(
x
,
ξ
)
∈
Λ
)
≥
1
-
ε
,
where f
:
ℝ
n
→
ℝ, F
:
ℝ
n
×
ℝ
k
→
ℝ
m, and F
(
x
,
ξ
) are continuous in x for arbitrary ξ and measurable in ξ for arbitrary x, Λ
⊆
ℝ
m is closed, and ε
∈
[
0,1
] is a small prescribed level. We will focus on the case when the distribution is finite discrete with realizations ξ
1
,
…
,
ξ
S and positive probabilities p
1
,
…
,
p
S such that ∑
s
=
1
S
‍
p
s
=
1. Then the problem can be rewritten as
(2)
min
⁡
x
⁡
f
(
x
)
s
.
t
.
∑
s
=
1
S
‍
p
s
I
(
F
(
x
,
ξ
s
)
∈
Λ
)
≥
1
-
ε
,
where I denotes the indicator function which is equal to one if the condition in the brackets is satisfied and to zero otherwise. We will use the following modified l
1-norm for a vector u
∈
ℝ
m
S defined as
(3)
∥
u
∥
=
∑
s
=
1
S
‍
p
s
∑
i
=
1
m
‍
|
u
i
s
|
,
which is necessary for further steps and to show the asymptotic equivalence of the considered stochastic programming problems; compare Branda [18].An important role is put to the problem where all random constraints are fulfilled. To simplify the notation, we set(4)
ℱ
S
(
x
)
=
(
F
(
x
,
ξ
1
)
,
…
,
F
(
x
,
ξ
S
)
)
T
,
and Λ
S
=
x
s
=
1
S
Λ. For u
∈
ℝ
m
S, we formulate a perturbed mathematical program:
(5)
min
⁡
x
f
(
x
)
s
.
t
.
ℱ
S
(
x
)
+
u
∈
Λ
S
.
The unperturbed problem for which u
=
0 corresponds to the case when ε
=
0 in the problem (2); that is, the feasible solutions are permanently feasible with respect to the considered realizations of the random vector ξ. We denote by
(6)
d
Λ
S
(
u
)
=
min
⁡
u
′
∈
Λ
S
∥
u
-
u
′
∥
the distance of a point u and the set Λ
S which will serve as the penalty function later on.We will employ two concepts of calmness. The first is related directly to the perturbed problem (5); compare Burke [19, Definition  1.1].Definition 1.
Letx
* be feasible for the unperturbed problem, that is, for u
=
0. Then the problem (5) is said to be calm at x
* if there exist constant N
~
≥
0 (modulus) and ϵ
>
0 (radius) such that for all (
x
,
u
)
∈
ℝ
n
×
ℝ
m
S satisfying x
∈
B
ϵ
(
x
*
) and ℱ
S
(
x
)
+
u
∈
Λ
S, one has
(7)
f
(
x
)
+
N
~
∥
u
∥
≥
f
(
x
*
)
.Note that if the problem (5) is calm at x
*, then x
* is necessarily a local solution to the unperturbed problem.The following proposition was formulated by Burke [19, Theorem  1.1], and gives the equivalence of the exact penalty property and problem calmness.Proposition 2.
Letx
* be feasible for the unperturbed problem, that is, for u
=
0. Then the unperturbed problem is calm at x
* with modulus N
~ and radius ϵ
>
0 if and only if x
* is a local minimum of the function
(8)
f
(
x
)
+
N
·
d
Λ
S
(
ℱ
S
(
x
)
)
over the neighbourhood B
ϵ
(
x
*
) for all N
≥
N
~.The form of the penalty problem follows from the theorem:(9)
φ
N
=
min
⁡
x
f
(
x
)
+
N
·
d
Λ
S
(
ℱ
S
(
x
)
)
.


## 3. Necessary Conditions for Problem Calmness

In this section, we give necessary conditions to ensure calmness of the problem (5) which can be hardly verified directly from its definition. First, we review the Lipschitz-like properties of the set-valued mappings M
:
ℝ
m
⇒
ℝ
n with graphs defined by
(10)
Gph
M
=
{
(
y
,
x
)
∈
ℝ
m
×
ℝ
n
:
x
∈
M
(
y
)
}
;
see, for example, Henrion and Outrata [31], Rockafellar and Wets [32] for further details.Definition 3.
LetM
:
ℝ
m
⇒
ℝ
n be a set-valued mapping. One says that M fulfills(i)
local Lipschitz property aty
¯ if and only if ∃
L
,
ϵ
>
0,
(11)
d
M
(
y
1
)
(
x
)
≤
L
·
d
(
y
1
,
y
2
)
,
∀
x
∈
M
(
y
2
)
,
h
h
h
h
i
∀
y
1
,
y
2
∈
B
ϵ
(
y
¯
)
,
(ii)
Aubin property aty
¯ if and only if ∃
L
,
ϵ
>
0,
(12)
d
M
(
y
1
)
(
x
)
≤
L
·
d
(
y
1
,
y
2
)
,
∀
x
∈
M
(
y
2
)
∩
B
ϵ
(
x
¯
)
,
h
h
h
h
h
h
i
∀
y
1
,
y
2
∈
B
ϵ
(
y
¯
)
,
where x
¯
∈
M
(
y
¯
)
),
(iii)
local upper Lipschitz property aty
¯ if and only if ∃
L
,
ϵ
>
0,
(13)
d
M
(
y
¯
)
(
x
)
≤
L
·
d
(
y
¯
,
y
)
,
∀
x
∈
M
(
y
)
,
h
h
h
h
i
∀
y
∈
B
ϵ
(
y
¯
)
,
(iv)
(graph) calmness at(
y
¯
,
x
¯
)
∈
Gph
M if and only if ∃
L
,
ϵ
>
0,
(14)
d
M
(
y
¯
)
(
x
)
≤
L
·
d
(
y
¯
,
y
)
,
∀
x
∈
M
(
y
)
∩
B
ϵ
(
x
¯
)
,
hhhhhhhhhhhhhhhhhiihhhhh
∀
y
∈
B
ϵ
(
y
¯
)
.It can be seen directly from the definitions that the calmness is the weakest of the conditions and is implied by the local upper Lipschitz property or by the Aubin property, whereas these two conditions are ensured by the local Lipschitz property.Foru
∈
ℝ
m
S, denote by
(15)
M
(
u
)
=
{
x
∈
ℝ
n
:
ℱ
S
(
x
)
+
u
∈
Λ
S
}
the perturbation of the (original) constraint set M
(
0
)
=
(
ℱ
S
)
-
1
(
Λ
). The following preposition gives us an important result which shows that the graph calmness together with the local Lipschitz continuity of the objective function is sufficient conditions for the problem calmness.Proposition 4.
Letx
* be a local minimizer such that M is calm at (
0
,
x
*
). Let the objective function f be locally Lipschitz continuous around x
*. Then the original problem is calm at x
* with modulus which is equal to the product of the moduli of the constraint set and the objective function.Proof.
See Hoheisel et al. [22, Proposition 3.5 and its proof].The preposition shows that sufficient conditions for calmness of the constrained set are desirable. Global graph calmness is ensured in the following important case.Proposition 5.
The set-valued mappingM is calm at each point of its graph whenever this graph is polyhedral.Proof .
See Rockafellar and Wets [32, Example  9.57].In general, it is not possible to obtain such strong result. Thus, we have to focus on conditions which ensure the calmness at least locally. These conditions are based on constraint qualification; see, for example, Bazaraa et al. [33], Kruger et al. [34] for a review. We start with the definitions of important cones. The Fréchet normal cone to Π
⊆
ℝ
p at a
∈
cl
⁡
Π is defined as
(16)
N
^
Π
(
a
)
=
{
y
∈
ℝ
p
:
lim
⁡
sup
⁡
a
′
→
Π
a
⁡
〈
y
,
a
′
-
a
〉
∥
a
-
a
′
∥
≤
0
}
.
Note that in finite dimensional setting the Fréchet normal cone corresponds to the polar of the tangent cone. Limiting normal cone to Π at a is defined by N
Π
(
a
)
=
lim
⁡
su
p
a
′
→
a
N
^
Π
(
a
), where a
∈
cl
⁡
Π and the limes-superior is considered in the Painléve-Kuratowski sense; see [32].Definition 6.
Letℱ
S be continuously differentiable. Generalized Mangasarian-Fromowitz constraint qualification (GMFCQ) is fulfilled at x
* if
(17)
λ
T
(
ℱ
S
)
′
(
x
*
)
=
0
,
λ
∈
N
Λ
S
(
ℱ
S
(
x
*
)
)
⟹
λ
=
0
.The relevance of the GMFCQ to our analysis is confirmed by the following proposition.Proposition 7.
Letℱ
S be continuously differentiable. If the generalized Mangasarian-Fromowitz constraint qualification is fulfilled at x
*, then the perturbation map M is calm at (
0
,
x
*
). Moreover, if f is continuously differentiable, then the problem is calm at x
*.Proof.
For the first part see Flegel et al. [35, Corollary  5]. Note that Mordukhovich [36] even showed that GMFCQ implies the stronger Aubin property. The second part follows directly from Proposition 4.Another important property, which is equivalent to graph calmness, is the existence of a local error bound of the constraint set.Proposition 8.
Calmness of the constraints system (15) at (
0
,
x
*
) is equivalent to the existence of a local error bound:
(18)
d
(
ℱ
S
)
-
1
(
Λ
S
)
(
x
)
≤
L
~
·
d
Λ
S
(
ℱ
S
(
x
)
)
,
∀
x
∈
B
ϵ
(
x
*
)
,
for some constants L
~
>
0 and ϵ
>
0.Proof.
See Hoheisel et al. [22, Proposition  3.4].


## 4. An Asymptotic Equivalence of Stochastic Programming Problems

In this section, we propose a new version of the theorem which concerns asymptotic equivalence of chance constrained problems and problems with penalty objective. We use the notion of optimal values for local optimal values; that is, the vector of decision variablesx is restricted to B
ϵ
(
x
*
) for some local optimal solution x
* of (5) in the following theorem.Theorem 9.
One considers the chance constrained problem (1) and the problem with the penalty objective (9). One assumes that (i)
the problem (5) has a local solution x
*,
(ii)
f, F
(
·
,
ξ
) are continuously differentiable around the local solution x
*,
(iii)
the GMFCQ is satisfied at the local solutionx
*.For arbitrary γ
∈
(
0,1
), N
>
0, and ε
∈
(
0,1
) put
(19)
α
N
(
x
)
=
N
·
d
Λ
S
(
ℱ
S
(
x
)
)
,
β
ε
(
x
)
=
1
ε
γ
·
d
Λ
S
(
ℱ
S
(
x
)
)
,
(20)
ε
(
x
)
=
∑
s
=
1
S
‍
p
s
I
(
F
(
x
,
ξ
s
)
∉
Λ
)
.
Then for any prescribedε
∈
(
0,1
) there always exists N
≤
N
~ large enough so that minimization (9) generates local optimal solutions x
N which also satisfy the probabilistic constraint with the given ε, where N
~ denotes the calmness modulus of the problem (9).
Moreover, bounds on the local optimal valueψ
ε of (1) based on the local optimal value φ
N of (9) and vice versa can be constructed:
(21)
φ
1
/
ε
γ
(
x
N
)
-
β
ε
(
x
N
)
(
x
ε
(
x
N
)
C
C
P
)
≤
ψ
ε
(
N
)
≤
φ
N
-
α
N
(
x
N
)
,
ψ
ε
(
x
N
)
+
α
N
(
x
N
)
≤
φ
N
≤
ψ
N
-
1
/
γ
+
β
N
-
1
/
γ
(
x
N
-
1
/
γ
C
C
P
)
,
with
(22)
lim
⁡
N
→
N
~
-
α
N
(
x
N
)
=
lim
⁡
N
→
N
~
-
ε
(
x
N
)
=
lim
⁡
ε
→
ε
~
+
β
ε
(
x
ε
C
C
P
)
=
0
,
for any sequences of the local optimal solutions of the chance constrained problem x
ε
C
C
P and the problem with penalty objective x
N, where ε
~
<
min
⁡
s
p
s.Proof.
The proof is analogous to Theorem 3 proposed by Branda [18] if we realize that the GMFCQ together with differentiability implies calmness of the problem (5) and that the local solution of (5) is permanently feasible.


## 5. Problem with a Stochastic Vanishing Constraint

Letg
1
(
x
,
ξ
)
,
g
2
(
x
,
ξ
)
:
ℝ
n
×
ℝ
k
→
ℝ be continuously differentiable in x for arbitrary ξ and measurable in ξ for arbitrary x. Then the joint chance constrained problem with a stochastic vanishing constraint can be formulated as
(23)
min
⁡
x
f
(
x
)
s
.
t
.
P
(
g
1
(
x
,
ξ
)
≥
0
,
g
1
(
x
,
ξ
)
g
2
(
x
,
ξ
)
≤
0
)
≥
1
-
ε
.
Note that if the function g
1 is equal to zero for some x and ξ, then the constraint g
2
(
x
,
ξ
)
≤
0 vanishes. If we denote
(24)
Λ
=
{
(
x
1
,
x
2
)
∈
ℝ
2
:
x
1
≥
0
,
x
1
x
2
≤
0
}
F
(
x
,
ξ
)
=
(
g
1
(
x
,
ξ
)
,
g
2
(
x
,
ξ
)
)
T
:
ℝ
n
×
ℝ
k
⟶
ℝ
2
,
we can rewrite the chance constraint in the abstract form as follows:
(25)
P
(
F
(
x
,
ξ
)
∈
Λ
)
≥
1
-
ε
.Letξ have a finite discrete distribution with realizations ξ
1
,
…
,
ξ
S. Denote Λ
S
=
x
s
=
1
S
Λ, ℱ
S
(
x
)
=
(
F
(
x
,
ξ
1
)
,
…
,
F
(
x
,
ξ
S
)
)
T. For a given permanently feasible point x
* we define the following partitioning of the set of scenarios:
(26)
S
+
0
=
{
s
:
g
1
(
x
*
,
ξ
s
)
>
0
,
g
2
(
x
*
,
ξ
s
)
=
0
}
,
S
+
-
=
{
s
:
g
1
(
x
*
,
ξ
s
)
>
0
,
g
2
(
x
*
,
ξ
s
)
<
0
}
,
S
0
+
=
{
s
:
g
1
(
x
*
,
ξ
s
)
=
0
,
g
2
(
x
*
,
ξ
s
)
>
0
}
,
S
00
=
{
s
:
g
1
(
x
*
,
ξ
s
)
=
0
,
g
2
(
x
*
,
ξ
s
)
=
0
}
,
S
0
-
=
{
s
:
g
1
(
x
*
,
ξ
s
)
=
0
,
g
2
(
x
*
,
ξ
s
)
<
0
}
.
According to Hoheisel et al. [22, Theorem  4.2], the GMFCQ is satisfied at x
* if the gradients
(27)
∇
x
g
1
(
x
*
,
ξ
s
)
,
s
∈
S
0
+
∪
S
00
are linearly independent and there is a vector d
∈
ℝ
n such that
(28)
d
T
∇
x
g
1
(
x
*
,
ξ
s
)
>
0
,
s
∈
S
0
-
,
d
T
∇
x
g
1
(
x
*
,
ξ
s
)
=
0
,
s
∈
S
0
+
∪
S
00
,
d
T
∇
x
g
2
(
x
*
,
ξ
s
)
<
0
,
s
∈
S
+
0
∪
S
00
.
Moreover, it follows from Hoheisel et al. [22, Corollary 4.7], that the penalty can be expressed under our settings in the form
(29)
d
Λ
S
(
ℱ
S
(
x
)
)
=
∑
s
‍
p
s
max
⁡
{
0
,
-
g
1
(
x
,
ξ
s
)
,
min
⁡
{
g
1
(
x
,
ξ
s
)
,
g
2
(
x
,
ξ
s
)
}
}
=
𝔼
[
max
⁡
{
0
,
-
g
1
(
x
,
ξ
)
,
min
⁡
{
g
1
(
x
,
ξ
)
,
g
2
(
x
,
ξ
)
}
}
]
.
If the GMFCQ is fulfilled and the objective function is continuously differentiable, then the problem (5) is calm and the corresponding problem with the penalty objective derived above is exact. Thus, in this case Theorem 9 applies to the problem with a stochastic vanishing constraint.


## 6. Conclusions

In this paper, we have discussed conditions which ensure exact penalization in stochastic programming. We have started with a general calmness condition of the underlying problem, which is equivalent to the exact penalty property. However, this condition cannot be verified directly; therefore necessary conditions have been proposed. We have shown that the local Lipschitz continuity of the objective function together with the calmness of the constraint set, which is implied, for example, by generalized Mangasarian-Fromovitz constraint qualification, is sufficient. These findings have enabled us to propose a new version of the theorem concerning asymptotic equivalence of the chance constrained problems and the problems with exact penalty objective, which is the main contribution of this paper. The theoretical results have been applied to the problem with a stochastic vanishing constraint where a sufficient condition for fulfilling the GMFCQ has been formulated.



---

*Source: 569458-2014-02-23.xml*