Convexity, Schur convexity, and majorization theory - Signal Processing and Optimization for Transceiver Systems - page 695

punctured
hexagon

crescent moon

oval

octagon

convex convex not convex not convex

segment on the
real axis

union of segments on the
real axis convex not convex

Figure 21.1 . Examples of convex and non-convex sets.

Figure 21.1 shows examples of convex and non convex sets. Geometrically speak-
ing, if we draw a chord from one point to another in a convex set then all points
on this chord are still contained in the set.

Definition 21.2. Convex functions. Let f ( x ) be a real function defined on a
convex set

♠

S .Wesay f ( x ) is a convex function if

f ( α x 1 +(1 − α ) x 2 ) ≤ αf ( x 1 )+(1 − α ) f ( x 2 ) (21 . 1)

for any α in 0 ≤ α ≤ 1 and any x 1 , x 2 ∈S . A function f ( x )issaidtobe concave

if − f ( x )isconvex. ♦

By repeated application of the definition we can show that f ( x )isconvexifand
only if

f α k x k

P− 1 P− 1

≤ α k f ( x k ) (21 . 2)

k =0 k =0

for any set of non-negative numbers α k such that α k =1 . A function is said
to be strictly convex if equality holds in Eq. (21.1) only for the trivial choices
α = 0 and α = 1. A function f ( x )is strictly concave if

− f ( x )isstrictlyconvex.

Why is convexity important? In engineering sciences, one often encounters the
need to minimize an objective function f ( x ) subject to some constraint on the
variables x i (components of x ). If an objective function is convex and the con-
straint set (i.e., the set from which x is allowed to be drawn) is a convex set,

then the optimization problem is said to be a convex optimization problem. In this
case a local minimum is also global. Furthermore, first-order necessary conditions
for optimality based on derivatives are also su cient, that is, there is no need to
look at second-order derivative information such as Hessian matrices [Chong and
Zak, 2001]. Examples of convex optimization includes linear programming prob-
lems and problems where the objective functions are quadratic and constraints are
linear. Many excellent references exist for this topic; for example, see Chong and
Zak [2001], Boyd and Vandenberghe [2004], and Antoniou and Lu [2007].

X