Homework 4

Due: Nov. 2, 14:00:00

First and second order conditions for convexity

  1. We claimed that a function f(x) differentiable on an open convex set is a strictly convex function if and only if f(y)>f(x)+f(x)T(yx) for all xy. The "" direction is easy. We now prove the "" direction. Suppose f(x) is a differentiable and strictly convex function. Fix xy, and let d=yx.

    • Show that for all 0<α<1, we have f(x+αd)f(x)α<f(y)f(x).
    • For all 0<α<β<1, show that f(x+αd)f(x)α<f(x+βd)f(x)β.
    • Use above results to show that f(y)>f(x)+f(x)T(yx).
  2. The second-order condition tells us that a twice differentiable f(x) is strictly convex if f(x) has 2f(x)0 for all xdomf, but not vice versa. Here we verify two examples.

    • Show that f(x)=x4 is a strictly convex function.
    • Show that f:R2R,f(x1,x2)=x12+x24 is a strictly convex function, and there exists xR2 such that 2f(x)0 (i.e., there exists v0R2 such that vT2f(x)v0).
  3. For each of the following functions determine whether it is convex, concave, or neither.

    • f(x1,x2)=1/(x1x2) on R>02.
    • f(x1,x2)=x12/(x2+1) on R>02.
    • f(x1,x2)=x1αx21α on R>02, where 0α1.
  4. We've showed that any norm is a convex function. In particular, for all p1, Lp-norm defined by x(i=1n|xi|p)1/p is a convex function on Rn. Now we consider the case where 0<p<1.

    Is the function f(x)=(i=1n|xi|p)1/p convex or concave? Prove your conclusion.

Convexity-preserving operations

  1. Let f(x)=log(i=1newiTx+bi) where wi,xRm and biR. We are going to show that f(x) is a convex function on Rm.

    Let g(y)=log(i=1neyi) where yRn.

    • Use Hölder's inequality to show that g(θy1+θ¯y2)θg(y1)+θ¯g(y2) for all θ[0,1].
    • Use composition rules to verify the convexity of f(x).
  2. Let f(x)=i=1r|x|[i] on Rn, where rn is a fixed integer, |x| denotes the vector with |x|i=|xi|, and |x|[i] is the i-th largest component of |x|. In other words, |x|[1],|x|[2],,|x|[n] are the absolute values of the components of x, sorted in nonincreasing order.

    Show that f(x) is a convex function.

    (Hint: Express f(x) as the pointwise maximum of a family of convex functions.)

Optimization problems

  1. Determine whether the following optimization problem is a convex optimization or not. Give your reasons.


    subject to (x1x2)2+4x1x2+ex2x10, and 5x17x2=0.