338 ACTIVITY 20: Convex and Concave Functions

WHY:

This activity is designed to introduce the concepts of convex and concave functions of several variables. It is important not to confuse the concepts of convex sets and convex functions, especially since one of the criteria for a function to be convex is that its epigraph form a convex set. Convex and concave functions are especially nice for optimization purposes since they have a unique relative min and max respectively and hence this relative min or max is also its absolute min or max. Although functions encountered in practice may not be convex or concave, they can sometimes be closely approximated by convex or concave functions.

LEARNING OBJECTIVES:

1. Discover from the graph when a function is convex and when it is concave.
2. Review the definiteness properties of quadratic forms.
3. Understand the role of learning journals in the learning process.

PERFORMANCE CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.
   • Completeness
   • Clarity
   • Depth
2. Level of understanding of each member of the team.

VOCABULARY:

In all these definitions we assume that K is a convex set in R_n, X, Y are in K, 0 <= a <= 1, and f:K -> R.

Convex Function

f is convex if f(aX + (1-a)Y) <= af(X) + (1-a)f(Y).

Strictly Convex Function

f is strictly convex if f(aX + (1-a)Y) < af(X) + (1-a)f(Y).

Concave Function

f is concave if f(aX + (1-a)Y) >= af(X) + (1-a)f(Y).

Strictly Concave Function

f is strictly concave if f(aX + (1-a)Y) > af(X) + (1-a)f(Y).

Affine Function

f is affine if f(aX + (1-a)Y) = af(X) + (1-a)f(Y).

Epigraph

The Epigraph of a function f, denoted epi(f), is the set {(X, Y) | Y >= f(X)}. Note that the epigraph is the region above the graph of f.

Hypograph

The Hypograph of a function f, denoted hyp(f), is the set {(X, Y) | Y <= f(X)}. Note that the hypograph is the region below the graph of f.

RESOURCES:

1. Section 4.6, Strategic Mathematics
2. 30 minutes

MODEL:

Examine the following function for convexity and check its Hessian for definiteness:

          f(x, y) = x2 - xy + y2

First, get into Maple and plot the graph of the function using the following commands:

     >with(plots):
     >f:=x^2 + x*y + y^2;
     >plot3d(f, x=-4..4, y=-3..3);

Verify that the epigraph is a convex set and so the function is convex. You may wish to rotate the plot to see this. Also verify that the function g = -f is a concave function.

To find the relative (and hence absolute) min for the function we find the gradient vector and then the Hessian matrix.

           grad f(x, y) = (2x - y, -x + 2y).  

		  | 2  -1 |
              H = |-1   2 | 

It is easy to check that H is positive definite, but let's check it using the definition.

[h1  h2] | 2 -1 || h1 |
        |-1  2 || h2 |

      		= 2h12 - 2h1h2 + 2h22 

                = 2(h12 - h1h2 + h22/4) + 3h22/2 

                = 2(h1 - h2/2)2 + 3h22/2 

                > 0 when (h1, h2) <> (0, 0)  

Observe that the function on the right side of the first equality is 2 * f(h₁, h₂). It is easy to see that the original function was a quadratic form corresponding to the matrix H/2.

CRITICAL THINKING QUESTIONS:

These will be provided in class.

Return to the List of Activities