Convex and Discrete

Optimization
P R O F. P. C . J H A

D E PA RT M E N T O F O P E R AT I O N A L R E S EA RC H

FA C U LT Y O F M AT H E MAT I C A L S C I E N C ES

U N I V E RS I T Y O F D E L H I
Convex Set
Mathematically:
A set C is a convex set if and only if the convex combination of
points in C lie in C.
The convex combination of points 𝑥1 , 𝑥2 , . . . , 𝑥𝑘 ∈ 𝐶 is any
point of the form
1 x1 +  2 x2 + ... +  k xk
k
Where i  0, i = 1, 2,..., k and 
i =1
i =1
Geometrically:
A set C is convex if the line segment between any two points
in C lies in C.
Convex Function
Mathematically
Let S  R n be a convex set and f : S → R . Then f ( x)
is called a convex function if x, u  S and 0    1,
we have

f [ x + (1 −  )u ]   f ( x) + (1 −  ) f (u )

Examples

x ln x, x  0
x , x
 Concave Function
Mathematically
Let S  R n be a convex set and f : S → R . Then f ( x)
is called a concave function if x, u  S and 0    1,
we have

f [ x + (1 −  )u ]   f ( x) + (1 −  ) f (u )

Examples
− x2 , x  R
log x, 0  x  
− x ,xR
Convex/ Concave Function
Geometrically:
1. If a function is convex (Fig1)/ concave (Fig2),
the midpoint B of each chord A1A2 lies above/
below the corresponding point A0 of the graph
of the function or coincides with this point.
2. The function f(x) is convex (Fig3)/ concave
(Fig4) on the interval [a, b] if and only if its
graph does not lie below/ above the tangent
drawn to it at any point x0 of the segment [a, b].
Properties of Convex Functions
•A linear function is both convex as well as concave.
•A function may neither be convex nor concave.
•The domain of a convex function has to be a convex set.
•A convex function may not be differentiable.
•A convex function may not be continuous. But they are continuous in the interior of their
domain.
•Let f and g be two convex functions defined over a convex set S  R n then (i) f + g, (ii)  f ,   0
and (iii) h( x) = Max( f ( x), g ( x)) are also convex functions.
xS
Epigraph
Let S  R n be a convex set and f : S → R . Then the set E f  R given by
n +1

Is called the epigraph of f.

Level Set/α-cut
Let S  R n be a convex set and f : S → R . Let   R . Then the set   R given by
n

  = {x  S : f ( x)   }
is called the α-level set or the α-cut of the function f.
Hypograph
n +1
Let S  R n be a convex set and f : S → R . Then the set G f  R given by

Is called the hypograph of f.

Visualization of
Epigraph, Hypograph
and Level set for
SR
Theorem 1:
Let S  R n be a convex set and f : S → R . Then f is a convex function on S iff its epigraph 𝐸𝑓 is
a convex set.
Proof: (i) (Necessity) Let f be convex on S and (x, α) and (u, β) ∈ 𝐸𝑓 . Then by the convexity of f
on S, we have that for 0    1,
f ( x + (1 −  )u )   f ( x) + (1 −  ) f (u )
  + (1 −  ) 
Therefore ( x + (1 −  )u,  + (1 −  )  )  E f and hence 𝐸𝑓 is a convex set.
(ii) (Sufficiency) Let 𝐸𝑓 be a convex set in R n +1 . Let x, u  S . Then ( x, f ( x))  E f and(u, f (u ))  E f .
As 𝐸𝑓 is a convex set, we have for 0    1,
( x + (1 −  )u,  f ( x) + (1 −  ) f (u ))  E f
i.e.
f ( x + (1 −  )u )   f ( x) + (1 −  ) f (u )).
Therefore f is a convex function on S.
Corollary 1.1:
Let S  R n be a convex set and f : S → R . Then f is a concave function on S iff its hypograph 𝐺𝑓
is a convex set.

Theorem 2:
Let S  R n be a convex set and f : S → R . Then f be a convex function. Then for all   R , its α-
level sets are convex.
Proof: Let x, u   (  R ). Then by the convexity of f, we have for 0    1
f ( x + (1 −  )u )   f ( x) + (1 −  ) f (u )   + (1 −  ) =  ,
i.e.  x + (1 −  )u   . Hence 𝛤𝛼 is a convex set. Since α is arbitrary, the result holds for all   R
Directional Derivatives
Theorem 3:
Let S  R n be an open convex set and f : S → R be differentiable. Then f is a convex function on S iff
for any x, u  S , we have
f ( x) − f (u )  ( x − u )T f (u ). for all x  S .
𝑃𝑟𝑜𝑜𝑓: 𝐵𝑦 𝑡ℎ𝑒 𝑐𝑜𝑛𝑣𝑒𝑥𝑖𝑡𝑦 𝑜𝑓 𝑓 𝑜𝑛 𝑆, 𝑤𝑒 ℎ𝑎𝑣𝑒 𝑓𝑜𝑟 0 ≤ 𝜆 ≤ 1,

𝑓 𝜆𝑥 + 1 − 𝜆 𝑢 ≤ 𝜆𝑓 𝑥 + 1 − 𝜆 𝑓 𝑢 ,
𝑖. 𝑒.
𝑓 𝑢+𝜆 𝑥−𝑢 −𝑓 𝑢
𝑓 𝑥 −𝑓 𝑢 ≥ ______(1)
𝜆
𝐵𝑢𝑡 𝑤𝑒 𝑎𝑟𝑒 𝑔𝑖𝑣𝑒𝑛 𝑡ℎ𝑎𝑡 𝑓 𝑖𝑠 𝑑𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑡𝑖𝑎𝑏𝑙𝑒 𝑜𝑛 𝑆, 𝑤ℎ𝑖𝑐ℎ 𝑏𝑦 𝑑𝑒𝑓𝑖𝑛𝑖𝑡𝑖𝑜𝑛 𝑚𝑒𝑎𝑛𝑠

𝑓 𝑢 + 𝑤 = 𝑓 𝑢 + 𝑤 𝑇 ∇𝑓 𝑢 + 𝛼 𝑢, 𝑤 𝑤 , ______(2)

𝑤ℎ𝑒𝑟𝑒 𝑢 + 𝑤 ∈ 𝑆 𝑎𝑛𝑑 lim 𝛼 𝑢, 𝑤 = 0. 𝑇ℎ𝑒𝑟𝑒𝑓𝑜𝑟𝑒 𝑢𝑠𝑖𝑛𝑔 2 𝑖𝑛 1 , 𝑤𝑒 𝑔𝑒𝑡

𝑤→0

𝑓 𝑢 + 𝜆 𝑥 − 𝑢 𝑇 ∇𝑓 𝑢 + 𝛼 𝑢, 𝜆 𝑥 − 𝑢 𝜆 𝑥 − 𝑢 − 𝑓 𝑢
𝑓 𝑥 −𝑓 𝑢 ≥ ,
𝜆
𝑖. 𝑒. 𝑓 𝑥 − 𝑓(𝑢) ≥ 𝑥 − 𝑢 𝑇 ∇𝑓 𝑢 + 𝛼 𝑢, 𝜆 𝑥 − 𝑢 𝜆 𝑥 − 𝑢

𝑁𝑜𝑤 𝑜𝑛 𝑡𝑎𝑘𝑖𝑛𝑔 𝑡ℎ𝑒 𝑙𝑖𝑚𝑖𝑡 𝑎𝑠 𝜆 → 0, 𝑤𝑒 𝑔𝑒𝑡 lim 𝛼 𝑢, 𝜆 𝑥 − 𝑢 = 0, 𝑎𝑛𝑑 ℎ𝑒𝑛𝑐𝑒

𝜆→0

𝑓 𝑥 − 𝑓 𝑢 ≥ 𝑥 − 𝑢 𝑇 ∇𝑓 𝑢 .
(Sufficiency)

𝐿𝑒𝑡 𝑥, 𝑢 ∈ 𝑆 𝑏𝑒 𝑎𝑟𝑏𝑖𝑡𝑟𝑎𝑟𝑦 𝑎𝑛𝑑

𝑙𝑒𝑡 𝑥 ∗ = 𝜆𝑥 + 1 − 𝜆 𝑢 𝑓𝑜𝑟 0 ≤ 𝜆 ≤ 1
𝑤𝑒 ℎ𝑎𝑣𝑒,
𝑓 𝑥 ≥ 𝑓 𝑥 ∗ + 𝑥 − 𝑥 ∗ 𝑇 ∇𝑓 𝑥 ∗ _______(3)
𝑓 𝑢 ≥ 𝑓 𝑥 ∗ + 𝑢 − 𝑥 ∗ 𝑇 ∇𝑓 𝑥 ∗ _______(4)
𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑦𝑖𝑛𝑔 3 𝑏𝑦 𝜆, 4 𝑏𝑦 1 − 𝜆 𝑎𝑛𝑑 𝑎𝑑𝑑𝑖𝑛𝑔, 𝑤𝑒 𝑔𝑒𝑡
𝜆𝑓 𝑥 + 1 − 𝜆 𝑓 𝑢 ≥ 𝑓 𝑥 ∗ + ∇𝑓 𝑥 ∗ 𝑇 (𝜆𝑥 + 1 − 𝜆 𝑢 − 𝑥 ∗ )
= 𝑓 𝑥 ∗ + ∇𝑓 𝑥 ∗ 𝑇 (𝑥 ∗ − 𝑥 ∗ )
= 𝑓 𝑥 ∗ (∵ 𝑥 ∗ = 𝜆𝑥 + 1 − 𝜆 𝑢)
= 𝑓(𝜆𝑥 + 1 − 𝜆 𝑢)
∴ 𝑓(𝜆𝑥 + 1 − 𝜆 𝑢) ≤ 𝜆𝑓 𝑥 + 1 − 𝜆 𝑓 𝑢
⇒ 𝑓 𝑖𝑠 𝑎 𝑐𝑜𝑛𝑣𝑒𝑥 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑜𝑛 𝑆.
𝐻𝑒𝑛𝑐𝑒 𝑝𝑟𝑜𝑣𝑒𝑑.
Corollary 3.1:
Let S  R n be an open convex set and f : S → R be differentiable. Then f is a concave function on S iff
for any x, u  S , we have
f ( x) − f (u )  ( x − u )T f (u ). for all x  S .
Theorem 4:
Let S  R n be an open convex set and f : S → R be differentiable. Then f is a convex function on S iff
for all x, u  S , we have
( x − u )T [f ( x) − f (u )]  0.

𝑃𝑟𝑜𝑜𝑓: 𝑁𝑒𝑐𝑒𝑠𝑠𝑖𝑡𝑦 𝐹𝑜𝑟 𝑥, 𝑢 ∈ 𝑆, 𝑤𝑒 ℎ𝑎𝑣𝑒 𝑓𝑟𝑜𝑚 𝑇ℎ𝑒𝑜𝑟𝑒𝑚 3

𝑓 𝑥 − 𝑓 𝑢 − 𝑥 − 𝑢 𝑇 ∇𝑓 𝑢 ≥ 0,
𝑎𝑛𝑑
𝑓 𝑢 − 𝑓 𝑥 − 𝑢 − 𝑥 𝑇 ∇𝑓 𝑥 ≥ 0.
𝐴𝑑𝑑𝑖𝑛𝑔 𝑡ℎ𝑒𝑠𝑒 𝑡𝑤𝑜 𝑖𝑛𝑒𝑢𝑎𝑙𝑖𝑡𝑖𝑒𝑠, 𝑤𝑒 𝑔𝑒𝑡
𝑥 − 𝑢 𝑇 ∇𝑓 𝑥 − ∇𝑓 𝑢 ≥ 0.
𝑆𝑢𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦 𝐿𝑒𝑡 𝑥, 𝑢 ∈ 𝑆 𝑎𝑛𝑑 0 ≤ 𝜆 ≤ 1. 𝑇ℎ𝑒𝑛 𝑏𝑦 𝑡ℎ𝑒 𝑚𝑒𝑎𝑛 𝑣𝑎𝑙𝑢𝑒 𝑡ℎ𝑒𝑜𝑟𝑒𝑚, 𝑤𝑒 ℎ𝑎𝑣𝑒
𝑓 𝑥 − 𝑓 𝑢 = 𝑥 − 𝑢 𝑇 ∇𝑓 𝑢 + 𝜆ҧ 𝑥 − 𝑢 , 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 0 < 𝜆ҧ < 1 ______(1)
𝐴𝑙𝑠𝑜 𝑏𝑦 𝑎𝑠𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛
𝜆ҧ 𝑥 − 𝑢 𝑇 ∇𝑓 𝑢 + 𝜆ҧ 𝑥 − 𝑢 − ∇𝑓 𝑢 ≥ 0.
𝐵𝑢𝑡 𝑡ℎ𝑒𝑛 1 𝑔𝑖𝑣𝑒𝑠
𝑓 𝑥 − 𝑓 𝑢 ≥ 𝑥 − 𝑢 𝑇 ∇𝑓 𝑢
𝐻𝑒𝑛𝑐𝑒 𝑝𝑟𝑜𝑣𝑒𝑑.