Appendix A
Convex sets and cones
A.1
Convex Sets
The concept of convexity is one of the most important and popular in Mathe-matics. The reason is that, in the presence of convexity, a problem enjoys nice properties. This is generally believed, but not always true; indeed, we will show in the next section that, in some cases, − even if very few − convexity may behave very badly.
Definition A.1.1. A nonempty set K ⊆Rn is convex, iff
(1 − α)x1+ αx2 ∈ K, ∀α ∈ [0, 1], ∀x1, x2 ∈ K. (A.1.1)
We stipulate to consider convex both a singleton and ∅. K is concave , iff ∼K is convex. K is a convex body, iff it is convex, clK is compact and int K 6= ∅. If int K 6= ∅, K is strictly convex, iff
(1 − α)x1+ αx2 ∈ int K, ∀α ∈]0, 1[, ∀x1, x2 ∈ cl K, x1 6= x2. K is strictly concave iff ∼ K is strictly convex.
Proposition A.1.1.
(i) K ⊆Rn is convex, if and only if any its translation is convex.
(ii) The intersection of any family of convex sets is convex. Proof.
(i) The relation (A.1.1) of Definition A.1.1 holds, iff (1 − α)(x1 − x) +
α(x2− x) ∈ K − x, whatever x ∈Rn may be.
(ii) Let {K(ξ), ξ ∈ Ξ} denote any finite or infinite family of convex sets. If the family is empty or a singleton, then the claim is trivial. Otherwise, because of the convexity of every K(ξ), we have x′, x′′ ∈ ∩
ξ∈ΞK(ξ) ⇒
x′, x′′ ∈ K(ξ), ∀ξ ∈ Ξ ⇒ (1 − α)x′+ αx′′∈ K(ξ), ∀α ∈ [0, 1], ∀ξ ∈ Ξ ⇔
(1 − α)x′ + αx′′∈ ∩ ξ∈ΞK(ξ).
Proposition A.1.2. Let K, K1, K2 ⊆Rn be nonempty and convex.
(i) ri K, int K and cl K are convex. (ii) ri(K1+ K2) = ri K1+ ri K2.
(iii) ˆx ∈ ri K and x◦ ∈ cl K with x◦ 6= ˆx imply ]x◦, ˆx] ⊂ ri K.
(4i) cl ri K = cl K. (5i) ri cl K = riK.
Proof. Call Sε(x) the intersection between aff K and a neighbourhood of x
with radius ε > 0.
(i) It is obvious, if card K = 1. Let card K > 1, and x1, x2 ∈ ri K with
x1 6= x2. There exists a sufficiently small radius ε > 0 s.t. S ε(x1),
Sε(x2) ⊂ ri K. Therefore, we have:
[x1, x2] ⊂ conv{Sε(x1), Sε(x2)} ⊂ ri K,
which (account taken that conv{Sε(x1), Sε(x2)} is an open set of aff K)
shows the convexity of ri K. Either int K = ∅ or the above reasoning can be repeated with the entire space in place of aff K. Ab absurdo, suppose that cl K be not convex, so that (card K > 1 and) ∃x1, x2 ∈
cl K s.t. [x1, x2]* cl K.
Then, ∃x ∈ ]x1, x2[ s.t. x /∈ cl K. If, ∀ε > 0, S
ε(x) ∩ K 6= ∅, then x is an
accumulation point of K, so that x ∈ cl K, which contradicts x /∈ cl K. Otherwise, ∃ε > 0 s.t. Sε(x) ∩ K = ∅, and then Sε(x) ∩ cl K = ∅.
Let Sε(x1) and Sε(x2) be as above with x1 6= x2. Whatever the radius
ε may be, ∃y1 ∈ S
ε(x1) and ∃y2 ∈ Sε(x2), so that [y1, y2] ⊆ K. By
choosing ε small enough, we achieve an absurdo: [y1, y2] ∩ S
A.1 CONVEX SETS (ii) ∀S1, S2 ⊆Rn, cl S1+ cl S2 ⊆ cl (S1+ S2). Then, because of (4i),
cl(ri K1+ri K2) ⊇ cl ri K1+cl ri K2 = cl K1+cl K2 ⊇ K1+K2 ⊇ ri K1+ri K2.
Since we evidently have:
aff cl(ri K1+ ri K2) = aff(ri K1 + ri K2) = aff(K1+ K2);
then we have also (for any sets A, B in general, A ⊇ B does not imply ri A ⊇ ri B; take for instance A as a (convex) square and B as an edge of A):
ri cl(ri K1+ ri K2) ⊇ ri(K1+ K2);
and, because of (5i),
ri cl(ri K1+ ri K2) = ri(ri K1+ ri K2)
Therefore,
ri(ri K1+ ri K2) ⊇ ri(K1+ K2),
so that (A ⊆ ri B ⇒ A ⊆ B, whatever the sets A, B ⊆ Rn may be):
ri K1 + riK2 ⊇ ri(K1+ K2).
The reverse inclusion is achieved this way. k ∈ ri K1 + ri K2 implies
k = k1+ k2 with k1 ∈ ri K
1, k2 ∈ ri K2. For i = 1, 2, as above, call Si
an open set (of aff Ki) containing ki and contained into ri Ki. We find
k ∈ S1+ S2 ⊂ ri(K1+ K2). The last inclusion being consequence of the
obvious equality (k1+ ε1) + (k2+ ε2) = (k1+ k2) + ε, where ε := ε1+ ε2,
εi ∈ aff K
i, kεik is small enough, i = 1, 2.
(iii) We have to show that:
x := (1 − α)x0+ αˆx ∈ ri K, ∀α ∈]0, 1[, (A.1.2) or that ∃τ > 0 s.t. Sτ(x) ⊂ K; call y a generic element of Sτ(x)
(the dependences on α are understood). x0 ∈ cl K implies that, ∀ε >
0, Sε(x0) contains elements of K; call y0 one of them. ˆx ∈ ri K implies
that ∃ρ > 0 s.t. Sρ(ˆx) ⊂ K. ∀y ∈ Sτ(x), and ∀y0 ∈ Sε(x0), ∩K we can
obviously find ˆy ∈ Rn, s.t.y = (1 − α)y0+ αˆy. By disposing of ε and τ ,
we will show that, it is possible to obtain that ˆy ∈ K (indeed, this will be done by achieving ˆy ∈ Sρ(ˆx)). Consequently, we will draw y ∈ K
and hence Sτ(x) ⊂ K and then) the thesis will follow. ρ being given,
we choose ε and τ in such way that: 1 − α
α ε + 1 ατ < ρ. Consequently, for y0 ∈ S
ε(x0) ∩ K we have k y0− x0k < ε, and ∀y ∈
Sτ(x), we have: 1 αky − xk + 1 − α α ky 0− x0k < ρ.
From this inequality, taking into account the equality in (A.1.2), we draw the strict inequality:
kˆy − ˆxk = 1 αy − 1 − α α y 0− ˆx = 1 α y − (1 − α)y0− αˆx = 1 α y − (1 − α)y0− [x − (1 − α)x0] ≤ 1 αky − xk + 1 − α α x0− y0 < ρ. which shows that ˆy ∈ Sρ(ˆx) and hence ˆy ∈ K.
(4i) Since ri K ⊆ K, cl ri K ⊆ cl K and the inclusion ⊆ holds. The reverse inclusion holds, since (i) implies that, ∀x ∈ cl K, ∃ˆx ∈ K \ {x} s.t. [ˆx, x[⊆ ri K, so that x ∈ cl([ˆx, x[) ⊆ cl ri K.
(5i) Since cl K ⊇ K, so that ri cl K ⊇ ri K, then the inclusion ⊇ holds. With regard to the reverse inclusion, note that, ∀x ∈ ri cl K, ∃ε > 0 s.t. Sε(x) ⊆ cl K. Because of (4i), we have x ∈ cl ri K. By definition
of closure, Sε(x) ∩ ri K 6= ∅. Let y1 := x + εz ∈ Sε(x) ∩ ri K, where
z ∈ aff K, kzk ≤ 1. If z = O, then y1 = x and the thesis is achieved.
Otherwise, set y2 := x − εz ∈ S
ε(x) ⊆ cl K. Since x = 12y1 + 12y2,
because of (iii), we have x ∈ [y1, y2[⊆ ri K
Definition A.1.2. A nonempty set K ⊆Rn is affine iff
(1 − θ)x1 + θx2 ∈ K, ∀θ ∈R, ∀x1, x2 ∈ K, x1 6= x2. (A.1.3)
Definition A.1.3. The affine hull of the set K ⊆Rn is the intersection of
all the affine sets that contains K; ifìt is denoted by aff K.
Definition A.1.4. The orthogonal complement of a subspace S of the vector space Rn is the set of vectors which are orthogonal to all elements of S; it is
A.2 CONES
A.2
Cones
Definition A.2.1. A set K ⊆Rn is a cone with apex at x ∈ cl K if and only
if
∀x ∈ K, ∀α ∈]0, +∞[ x + α(x − x) ∈ K. (A.2.1a) For x = O, (A.2.1a) becomes:
∀x ∈ K, ∀α ∈]0, +∞[ αx ∈ K, (A.2.1b) and K is called a cone with apex at the origin or simply a cone. Iff further-more K is convex, it is called a convex cone.
Definition A.2.2. A cone (with apex at O) is called pointed (or acute, if it is also convex) iff
(cl K) ∩ (− cl K) = {O}, (A.2.2) when the apex is at x, then (A.2.2) must be verified by K − x. A cone K is properly pointed, iff conv K is pointed.
Proposition A.2.1. K ⊆Rn is a convex cone with apex at x ∈ cl K, if and
only if
x1, x2 ∈ K, (α, β) ∈R2
+\ {O} ⇒ x + α(x1− x) + β(x2− x) ∈ K. (A.2.3)
Proof. Because of Proposition A.1.1(i), it is not restrictive to assume x = O. (If) By setting α = 1 − β with β ∈ [0, 1], (A.2.3) shows the convexity of K; by setting x2 = x1, (A.2.3) becomes (A.2.1b).
(Only If) Set δ := α + β and γ := β/δ. ∀x1, x2 ∈ K, the convexity of K
implies ˜x := (1 − γ)x1+ γx2 ∈ K; K being a cone, the last relation implies
δ˜x ∈ K. (A.2.3) follows.
Proposition A.2.1 characterizes the convex cones as the sets which are closed under vector addition and non-negative scalar multiplication. Some-times, it is useful to consider a cone as generated by a set. To this end, consider the following:
Definition A.2.3. Let x ∈ Rn and X ⊂ Rn with X 6= {x}. The cone
generated by X from x is the set: cone(x; X) := {x ∈Rn
which, for x = O, becomes:
cone X := {x ∈Rn | x = αy, y ∈ X, α ∈]0, +∞[}. (A.2.4b)
Of course, (A.2.4) are cones; their convex hulls are called cone spanned by X from x and cone spanned by X, and denoted by span(x; X) and span(X) respectively.
Proposition A.2.2. If X ⊂Rn is convex, then
cone(x; X) = conv cone(x; X). (A.2.5) Proof. It is enough to show that cone(x; X) is convex. Let x1, x2 ∈ cone(x; X),
so that ∃ y1, y2 ∈ X and ∃ α 1, α2 ∈R+\{O}, s.t. xi−x = αi(yi−x), i = 1, 2. Then (x1− x) + (x2 − x) = (α 1+ α2) α1 α1+ α2 y1+ α2 α1+ α2 y2 − x . Because of Proposition A.2.1 and of Definition A.2.3, taking into account that α1 α1+ α2 y1+ α2 α1+ α2 y2 ∈ X, we achieve the thesis.
An important class of convex cones (with apex at the origin) is defined by the following condition:
K + cl K = K. (A.2.6) The above condition is satisfied if K is convex and either closed (in which case (A.2.6) is trivial) or open, as it is easy to show. A convex cone, which is not closed and fulfils (A.2.6), cannot contain the origin; in fact, assuming the contrary case, for a = O ∈ K, and for b ∈ (cl K) \ (K ∪ O)we would have a+b /∈ K, which contradicts (A.2.6). Note also that if a convex cone K fulfils (A.2.6) and K = (cl K) \ {O}, then K is pointed. In fact, if ab absurdo we deny (A.2.2), so that ∃k ∈ (cl K) ∩ (− cl K) \ {O}, then we have k, −k ∈ K and, because of the convexity of K, O = k + (−k) ∈ K, which contradicts the assumption. Of course, the above intersection contains convex cones K 6= (cl K) \ {O}; for instance, those that are closed and pointed.
One of the most important roles played by a cone occurs when it is used to replace locally a set. Unfortunately, in general, there is not a unique way to do
A.2 CONES it. As a consequence, several cones have been introduced for approximating a given set; the choice depends on the purpose which is pursuited. Here, only the main types are briefly analysed.
Definition A.2.4. Let the nonempty set X ⊆ Rn and x ∈ cl X be given.
The set of x + x ∈ Rn for which ∃{xi}∞
1 ⊆ cl X with limi→+∞x
i = x, and ∃{αi} ∞ 1 ⊂R+\ {0}, such that: lim i→+∞αi(x i− x) = x, (A.2.7)
is called tangent cone to X at x and denoted by TC(x; X). We stipulate that TC(x; ∅) = ∅. If x = O, then the notation TC(X) is used.
It is immediate to see that TC(x; X) is a cone with apex at x, that x ∈ int X ⇒ TC(x; X) = Rn, and that TC(x; Rn) = Rn, T C(x; Qn) = Rn,
TC(x;Zn) = {x} (of course, with x ∈Zn, since cl Zn =Zn).
It is immediate to see that, unless x be an isolated point of cl K, or x = O, (A.2.7) implies lim
i→+∞αi = +∞.
Therefore, setting βi := 1/αi, (A.2.7) can be equivalently written in the
following way: lim βi↓0 1 βi (xi− x) = x, (A.2.8) which shows x as a sort of generalized derivative, (1/βi)(xi− x) being a sort
of quotient ratio.
For some classes of sets, like the convex ones, the tangent cone is an excellent local approximation; in general, it enjoys the nice property shown by the next theorem.
Theorem A.2.3. Let X ⊂Rn be nonempty and x ∈ cl X.
(i) TC(x; X) is closed.
(ii) If X is convex, then TC(x; X) contains cl X, equals cl cone(x; X) and is convex.
Proof. Without any loss of generality, we can assume that x = O and card X > 1.
(i) y ∈ cl TC(X) implies that, ∀ε > 0, ∃x(ε) ∈ TC(X) s.t. kx(ε) − yk < ε
2. (A.2.9) Because of the Definition A.2.4, x(ε) ∈ TC(X) means that ∃{xi(ε)}∞
1 ⊆ cl X, with lim i→+∞x i(ε) = O and ∃{α i(ε) > 0} ∞ 1 , s.t. (the notation of
those sequences is slightly improper: the dependence on ε should be referred, first of all, to the entire sequence):
lim
i→+∞αi(ε)x i
(ε) = x(ε), so that ∃i(ε) ∈ N s.t., ∀i > i(ε), we have:
kαi(ε) xi(ε) − x(ε)k <
ε
2. (A.2.10) From (A.2.9) and (A.2.10), ∀i > i(ε), we draw:
kαi(ε)xi(ε) − yk = kαi(ε)xi(ε) − x(ε) + x(ε) − yk ≤ ≤ kαi(ε)xi(ε) − x(ε)k + kx(ε) − yk < ε 2+ ε 2 = ε. (A.2.11) Let n ∈ N. From the sequence {xi(1
n)} ∞
i=1, let us extract the
ele-ment which corresponds to i = in := i(1n) + 1, namely yn := xin(1n);
analogously, from {αi(1n)}∞i=1 let us extract βn := αin(
1
n). The pair
of sequences {yn}∞
1 and {βn}∞1 fulfils Definition A.2.4. In fact, from
(A.2.11) ∀ε ∈ R+\ {0} (as above), we have:
kβnyn− yk ≤ kβnyn− x( 1 n)k + kx( 1 n) − yk < ε. (A.2.12) Hence y ∈ TC(X).
(ii) If card X = 1, then the thesis is trivial. Otherwise, let x 6= x and x ∈ cl X. The convexity of X imply that cl X is convex; so ∀i ∈ N, xi := x + 1
i(x = x) ∈ cl X. Then, ∀ε > 0, and ∀i ∈ N, ∃ x
i(ε) ∈ X
s.t. kxi(ε) − xik < ε
i or ki[x
i(ε) − x] − (x − x)k < ε, which implies that
x ∈ TC(x; X), because of (A.2.7) where α, x2 and x must be replaced
by i, xi(ε) and x − x, respectively. Now we prove that:
A.3 CONVEX FUNCTIONS If x + x ∈ cl cone(x; X), then ∃{yi}∞
1 ⊂ cone(x; X), s.t.: x = lim i→+∞(y i− x). (A.2.14) yi ∈ cone(x; X) ⇒ ∃ xi ∈ X and ∃ α r > 0, s.t. yi− x = αi(xi− x).
Thus, we have the equality: x = lim
i→+∞αi(x
i− x), (A.2.15)
which, being (A.2.7), shows that cl cone(x; X) ⊆ TC(x; X). If x ∈ TC(x; X), then (A.2.7), being equal to (A.2.15), because of (ii), implies that TC(x; X) ⊆ cl cone(x; X). Hence (A.2.13) follows. (A.2.13) and Proposition A.2.2 give the convexity of TC(x; X).
If in Definition A.2.4 we require that, ∀{αi}
∞
1 ⊂R+\ {0} with limi→+∞αi =
+∞, ∃{xi}∞
1 ⊆ cl X, such that (A.2.7) holds, then we have a strengthening
of the tangent cone. For instance, in the example of Fig. 2.1.13, only the edge e′ is admitted.
A.3
Convex Functions
The concept of convex function is fundamental for the theory of constrained extrema. Even if it might be carried out as a special case of the theory of convex sets, it is useful to develop it in a functional language, as usual. Definition A.3.1. Let K ⊆ Rn be nonempty and convex. f : K → R is
called convex, if and only if
(1 − α)f (x1) + αf (x2) − f (x(α)) ≥ 0, ∀x1, x2 ∈ K, ∀α ∈ [0, 1], (A.3.1)
where x(α) := (1 − α)x1 + αx2.
Iff the above inequality is verified as strict inequality ∀α ∈]0, 1[ and ∀x1, x2 ∈
K with x1 6= x2, f is called strictly convex.
f is (strictly) concave iff −f is (strictly) convex. f is affine, iff is both convex and concave or, equivalently, iff (A.3.1) holds as equality or iff differs from a linear function because of a constant.
In the above definition, by convex function is meant what often is called proper convex function: a function whose epigraph is nonempty and does not contain vertical lines, or f(x) < +∞ for at least one x ∈ K and f (x) > −∞, ∀x ∈ K, or dom f 6= ∅ and f is finite on K . The graph of a strictly convex function does not contain any (nondegenerate) segment (of K × R). If n ≥ 2, f is strictly convex, and card lev≤0αf > 1 with
α ∈ Im f , then frt lev≤0αf does not contain any (nondegenerate) segment
(of K). The contrary happens, for n ≥ 1, if f is convex, but not strictly. Theorem A.3.1. Let K ⊆Rn be nonempty and convex, and f : K → R.
(i) f is convex if and only if epif is convex.
(ii) If, ∀x ∈ ri K, there exists σ ∈Rn (depending on x), such that:
E(x, x, σ) := f (x) − f (x) − hσ, x − xi ≥ 0, ∀x ∈ K, (A.3.2a) then f is convex on ri K; if f is convex on K, then (A.3.2a) holds, ∀x ∈ ri K; if f is differentiable, then (A.3.2a) becomes:
E(x, x, f′(x)) = f (x) − f (x) − hf′(x), x − xi ≥ 0, ∀x ∈ K. (A.3.2b) If f is continuous on K , then (A.3.2a) with x ∈ K is necessary and sufficient for the convexity of f on K.
Glossary of Notation
a := b a equals b by definition a ≡ b a equals b identically
a /≡ b a does not equal b identically a ⇒ b a implies b
a ⇔ b a implies b and is implicated by b ∃ there exist(s)
∄ there is (are) no
∀ for each
{x | P } set of all x with the property P
∅ empty set
a ∈ A a is an element of set A card A cardinality of set A ∼ A complement of set A
int A orAo topological interior of set A
ri A relative topological interior of set A ∂A or frt A boundary (or frontier) of set A
(∂ is used also for denoting subgradient) cl A closure of set A
A ⊆ B the set A is contained in the set B (A is subset of B )
A ⊇ B the set A contains the set B (A is superset of B)
A ⊂ B the set A is contained in the set B, but A 6= B (A is proper subset of B)
A ⊃ B the set A contains the set B, but A 6= B (A is proper subset of B)
respectively
dim A dimension of set A
aff A affine hull of set A; aff ∅ := {O} A × B Cartesian product of sets A and B An := ×n
i=1Ai = A1× ... × An Cartesian product of sets A1, ..., An
A − B denotes vector difference between sets A and B P (A) denotes the power set of A
conv A convex hull of set A cl conv A convex closure of set A P, Q denote continued sum and,
continued product, respectively N(x) denotes neighbourhood of x
Nε(x) denotes open hypersphere with centre at x and
radius ε sgn (x) signum of x
f : X → Y denotes function with domain within X and image within Y
gr f graph of function f; i.e. {(x, y) | y = f(x)} epi f epigraph of function f; i.e. {(x, y) | y ≥ f(x)} hypo f hypograph of function f; i.e. {(x, y) | y ≤ f(x)} dom f effective domain of f; i.e.
{x | ∃y such that (x, y) ∈ epi f } = = {x | f (x) < +∞}
Im f image of function f
lev⋚α f denotes the various level sets of function f, defined, respectively, by {x | f(x)⋚ α}
levZ f denotes the generalized level set of function f,
defined by {x | f(x) ∈ Z} lim inf
x→x f (x) denotes the lower limit of function f, defined by
sup
ε>0 x∈Nεinf(x)\{O}
f (x) lim sup
x→x
f (x) denotes the upper limit of function f, defined by inf
ε>0 x∈Nsupε(x)\{O}f (x)
f ◦ g = f (g(x)) composition of functions
f (•; y) denotes the restriction of f to the 1st argument at the fixed value y for the 2nd argument
GLOSSARY OF NOTATION
f|A denotes the restriction of function f to the set A
Ck(T ) set of all continuous functions x : T → R, having
the first k derivatives continuous on T ;
C0(T ) is the set of all continuous function on T
{xi}∞
1 denotes the sequence x
1, x2, . . . , xk, . . .;
xi = (xi
1, . . . , xin) is the ith vector;
a subfix denotes scalar; a superfix relates to vector {A(ξ)}ξ∈Ξ denotes a family of sets
d(x, A) Euclidean distance of the point x from the set A d(A, B) Euclidean distance between the sets A and B A⊥ orthogonal complement of A; in particular:
{O}⊥=Rn, (Rn)⊥= {O}.
A∗ positive polar (or dual) of cone (or set) A (a star as apex
denotes polarity, iff it is applied to a set); we stipulate that A∗∗:= (A∗)∗
cone(x; S), cone S denote the cones generated by the set S from x or from the origin, respectively
projBA denotes projection of set A upon set B
MT denotes the transpose of matrix M
det M denotes the determinant of the (square) matrix M rank M denotes the rank of the (square) matrix M
Rm×n is the set of matrices of dimension m × n, and with
real entries
N, Z, Q, R, C, B sets of (positive) natural, integer, rational, real, com-plex, zero-one numbers, respectively
R := R ∪ {±∞} = [−∞, +∞] set of extended reals
R+:= [0, +∞[ sets of non-negative real numbers,
R+:=R+∪ {+∞} = [0, +∞] set of extended non-negative reals
Rn sets of n-tuples with real entries; R1 =R
B, B Banach spaces
B+ closed and convex cone of B with apex at the origin On n-tuple, whose entries are zero; when there is no
fear of confusion, the subfix is omitted; for n = 1, without no fear of confusion, the 1-tuple O1 is
iden-tified with its elements, namely we set O1 = 0
|x| denotes absolute value of x ∈ R
kxk2 = hx, xi
1
2 is the Euclidean norm;
kxk∞= max{|x1|, . . . , |xn|} is the Tchebycheff norm
(ai i ∈ I) := (a1, . . . , am) with I = {1, . . . , m}
ar denotes either r-th vector (of a sequence of vectors) or r-th power of the
real a; the context should resolve the alternative
[a, b] := {x ∈Rn| a ≤ x ≤ b}, with a, b ∈Rn
]a, b[ := {x ∈Rn| a < x < b} = ri[a, b], with a, b ∈Rn
]a, b] := {x ∈Rn
| a < x ≤ b}, with a, b ∈Rn [a, b[ := {x ∈Rn| a ≤ x < b}, with a, b ∈Rn
Special Symbols
I set of indices of constraining functions
I0 set of indices of constraining functions of bilateral
constraints
I+ set of indices of constraining functions of unilateral constraints
H set of Image Space which identifies the kind of con-straints
Kx image set
E(Kx) conic extension of Kx
Lw denotes the generalized Lagrangian function
L denotes the Lagrangian function, unless differently said 1 ≤ p < ∞
argmin • set of minimum points of • argmax • set of maximum points of •
C denotes usually a cone; C0 := C\{O}; o
C := int C Ax(x) is the map which sends the variable x of a problem
into its image variable z
cone(x; X) is the cone generated by X from x; cone(X) := cone (O; X)
TC(x; X) is the tangent cone to x with apex at x; TC(X) := TC(O; X)
x≧ y, x, y ∈ Rn x − y ∈Rn +
GLOSSARY OF NOTATION x ≤C y means y − x ∈ C
x ≥C y means x − y ∈ C
xC y means y − x /∈ C
xC y means x − y /∈ C
minC denotes vector minimum with respect to cone C
Acronyms
i.e. id est
s.t. subject to or such that iff if and only if
l.s.c. lower semicontinuous min, max minimum, maximum inf, sup infimum, supremum m.p. minimum point(s)
g.m.p. global minimum point(s) IS Image Space
Bibliography
[1] Albouy M. and Breton A., Interpretation economique du principe du maximum. R.I.R.O., 2e année, No. 14, 1968, pp. 37-68.
[2] Andersen K.D., An efficient Newton barrier method for minimizing a sum of Euclidean norms. SIAM J. Optim.Vol. 6, 1996, No. 1, pp.74-95. [3] Antoni C., Su una teoria generale della dualità per problemi di estremo
vincolato e per le disuguaglianze variazionali.
[4] Auchmuty G., Duality for Non-Convex Variational Principles. Jou. of Differential Equations, Vol. 50, 1983, pp. 80-145.
[5] Banach S., Sur les lignes rectifiables et les surfaces dont l’aire est finie. Fundam. Math., Vol.7, 1925, pp.225-237.
[6] Bazaraa M.S. and Shetty C.M., Foundations of Optimization. Springer-Verlag, Berlin, 1976.
[7] Bellman R., Dynamic Programming. Princeton Univ. Press, 1957. [8] Ben-Israel A., Charnes A. and Kortanek, Asymptotic Duality over closed
convex Sets. Jou. of Mathem. Analysis and Appls. Vol. 35, 1971, pp. 677-691.
[9] Beoni C., A generalization of Fenchel duality theory. Jou. Optimiz. The-ory Appls. Vol. 49, No. 3, 1986, pp. 357-387.
[10] Bussotti P., On the Genesis of the Lagrange Multipliers. Jou. of Optimiz. Theory and Appls., Vol.117, No.3, 2003, pp.453-459.
[11] Camerini P.M., Galbiati G. and Maffioli F., The image of weighted com-binatorial problems. Annals of Operation Research, Vol.33, 1991, pp.181-197.
[12] Carathéodory C., Calculus of Variations and Partial Differential Equa-tions of the First Order. Chelsea Publ.Co., New York, 1982 (translation of the volume Variationsrechnung und Partielle Differential Gleichungen Erster Ordnung-B.G, Teubner, Berlin, 1935).
[13] Chen G.-Y., Huang X. and Yang X.Q., Vector Optimization. Set-Valued and Variational Analysis. Lecture Notes in Econ. and Mathemat. Sys-tems No. 541, Springer-Verlag, Berlin, 2005.
[14] Clarke F.H., Optimization and Nonsmooth Ana1ysis. J. Wiley, New York, 1983.
[15] Craven B.D. and Mond B., Transposition theorems for cone-convex func-tions. SIAM Jou. Appl. Mathem., Vol.24, No.4, 1973, pp.603-612. [16] Dietze S., Schäuble M., On the Relationship between Fenchel and
La-grange Duality for Optimization Problems in General Spaces. Optimiza-tion, Vol.16, No.1, 1985, pp.7-14.
[17] Ekeland I., Témam R., Analyse convexe et problèmes variationnels. (French) Collection Études Mathématiques. Dunod; Gauthier-Villars, Paris-Brussels-Montreal, Que., 1974.
[18] Elster K.H. and Sutti C. (Eds.), Mathematical Optimization. Theory Methods and Applications. Proc. Workshop Days (Verona, Dec.9,1992), Published by Univ.of Verona, Via dell’Artigliere, 19-Verona, Italy, 1993. [19] Floudas C.A. and Pardalos P.M. (Eds.), Encyclopedia of Optimization.
Kluver Academic Publishers, Dordrecht, 2001, Vols.I-V.
[20] Gauvin J., Shadowprices in nonconvex mathematical programming. Mathem. Programming, North-Holland, Vol. 19, 1980, pp. 300-312. [21] Giannessi F., On Lagrangian Non-Linear Multipliers Theory for
Con-strained Optimization and related topics, Tech.Report No.123, Dept. of Mathem., Univ.of Pisa, Sect. of Optimization, 1984, pp.1-79. Pub-lished as General Optimality Conditions via a Separation Scheme. In Algorithms for Continuous Optimization. E. Spedicato (Ed.), Kluwer Acad.Publishers, Dordrecht, Boston, 1994, pp.1-23.
BIBLIOGRAPHY [22] Giannessi F., Constrained Optimization and Image Space Analysis.
Springer-Verlag, 2005, Vol.1.
[23] Giannessi F., On the theory of Lagrangian duality. Optimization Letters, Vol.1, Springer-Verlag, 2006, pp 9-20.
[24] Giannessi F., Theorems of the Alternative and Optimization. In [18], Vol.V, pp.437-444.
[25] Giannessi F., Theorems of the Alternative and Optimality Conditions. Tech. Report No.83, Dept. of Mathem., Univ.of Pisa, Sect. of Optimiza-tion, 1982, pp.1-30. Published with the same title in Jou. Optimiz. Th. Appls., Vol.42, No. 3, 1984, pp.331-365.
[26] Giannessi F., Image Space Approach to Optimization. In [19]. vol.II, pp.457-464.
[27] Goh C.J. and Yang X.Q., Duality in Optimization and Variational In-equalities Taylor and Francis, London, 2002.
[28] Hahn H., Über lineare Gleichungen in lineare Räumen. Jou.Mathem., Vol.157, 1927, pp.214-229.
[29] Hestenes M.R., Calculus of Variations and Optimal Control Theory. J. Wiley, New York, 1966.
[30] Hestenes M.R., Optimization Theory: The finite dimensional case. J. Wiley, New York, 1975.
[31] Jeyakumar V., Convexlike Alternative Theorems and Mathematical Pro-gramming. Optimization, Vol.16, No.5, 1985, pp.643-652.
[32] Jung H.W.E., "Uber die kleinste Kugel, die eine r.. ..aumliche Figur ein-schliesst". Jou.Reine Angew.Math., Vol.123, 1901, pp.241-257.
[33] Khun H.W., On a Pair of Dual Nonlinear Programs. Nonlinear program-ming, 1967, J. Abadie, North Holland Publishing company, pp.37-54 [34] Magnanti T.L., Fenchel and Lagrange duality are equivalent.
Mathe-matical Programming, Vol.7, 1974, North-Holland Publishing Company, pp.253-258.
[35] Mangasarian O.L., Nonlinear Programming. SIAM Monograph in Ap-plied Mathematics, Philadelphia, 1994.
[36] Martínez-Legaz J.-E., Singer I., Some Caracterizations of ϕ-Lagrangian Dual Problems. Optimization, Vol.22, No.6, 1991, pp 835-843.
[37] Minkowski H., Theorie der Konvexen Körper. Insbesondere Begründung ihres Oberflächenbegriffs, Gesammelte Abhandlungen II, Leipzig, 1911. [38] Pourciau B.H., Multipliers rules. Amer.Mathem.Monthly, Vol.87, 1980,
pp.443-452.
[39] Pourciau B.H., Multipliers rules and separation of convex sets. Jou.Optimiz.Th. Appls., Vol.40, 1983, pp.321-331.
[40] Rockafellar R.T., Convex Analysis. Princeton Univ. Press, Princeton, N.J., 1970.
[41] Rockafellar R.T., Extension of Fenchel’s Duality Theorem for Convex Functions. Duke Math. J., Vol.33, No.1, 1966, pp 81-89.
[42] Rockafellar R.T. and Wets J.B., Variational Analysis. Springer-Verlag, Berlin, 1998.
[43] Tardella F., On the image of a constrained extremum problem and some applications to the existence of a minimum. Jou. of Optimiz. Theory and Appls., Vol.60, No.1, 1989, pp.93-104.
[44] Tind J., Wolsey L. A., An elementary survey of General Duality The-ory in Mathematical Programming. Mathematical Programming, Vol.21, 1981, North-Holland Publishing Company, pp.240-261.
[45] Toland J. F., Duality in nonconvex optimization. J. Math. Anal. Appl., Vol.66, No.2, 1978, pp 399-415.
[46] Weyl H., Elementare Theorie der konvexen Polyheder. Commentarii Math. Helvetici, Vo1.7, 1935, pp.290-306.
[47] Zeidler E., Nonlinear function analysis and its applications III. New York, Springer, 1985.
