Description
15. Show that the entropy of a Bernoulli random variable is a concave function (i.e. the
negative entropy is a convex function).
16. Show that the set C={x|Ax ≥ b} , A in Rmxn
, x in Rn
, b in Rm, is a convex set. Note that
this describes the constraint set of a linear program.
17. A function f is said to have a global minimum at x if for all y, f(y) ≥ f(x). It is said to have
a local minimum at x if there exists a neighborhood H around x so that for all y in H, f(y)≥
f(x). Show that, if f is convex, every local minimum is a global minimum. [Hint: Prove by
contradiction using Jensen’s inequality.]
18. Consider the LP: min c
T
x s.t. Ax ≥ b, x ≥ 0, where A is the 4×2 matrix: [ 0 −1; −1 −1; −1
2; 1 −1], b is a 4×1 vector [−5; −9;0; −3] and c is a 2×1 vector [−1; −2]. (a) Draw the
feasible region in R2
. (b) Draw the contours of c
T
x =−12, c
T
x =−14 and c
T
x =−16 and
determine the solution graphically. Does the minimum go through a vertex? Can you
intuitively explain why?
