Math 438 ACTIVITY 7:Convex sets, Hyperplanes, Hulls

WHY:This activity is designed to help you understand the structure of convex sets in Rn. We are interested in situations in which the feasible region of our problem is convex - in Linear Programming, this always occurs, because intersections of halfspaces and of hyperplanes (the form of our constraints) are always convex. The key technique for solving linear programming problems hinges on the representation of the feasible region in terms of a convex hull of a set of points plus (not “union with” – but “plus”) hte conical hull of a set of vectors.

VOCABULARY:

Line Segment

The line segment joining two points/vectors X1 and X2 in Rn is the set {X Rn |X1 + (1 - )X2 for some 0  1}

Convex Set

A set S in Rn is convex if for any two distinct points of S the line segment joining these points is contained completely in S.

Hyperplane

The set of points in Rn satisfying a linear equation CTX = k [where C is a nonzero n –dimensional vector of coefficient and k is a number] is called a hyperplane. A hyperplane divides space into upper and lower halfspaces.

Halfspaces

The halfspaces in Rn determined by a linear equationCTX = k are the sets of points satisfying (respectively) {X Rn | CTX ≥ k} [the closed upper halfplane] and {X Rn |CTX ≤ k} [the closed lower halfplane] –[there are also “open” versions that do not include the hyperplane – which is the boundary– but we will work primarily with the closed halfspaces]. Which is “upper” and which is “lower” depends on the way in which the equation is written – but is not important for out purposes.

Linear Hull

The linear hull L(S) of a set is the set of all linear combinations of vectors in S. It is the same as the space spanned by the vectors in S.

Affine Hull

The affine hull Aff(S) of a set S is the set of all affine combinations of vectors in S. It is the lowest dimensional hyperplane which passes through all the points of S. (For example, in R3, if S has one point Aff(S) is the point; if S has two distinct points, Aff(S) is the line determined by them; if S has three noncollinear points, Aff(S) is the plane determined by them; if S contains at least four noncoplanar points, Aff(S) is all of R3. – for general Rn these numbers shift accordingly)

Conical Hull

The conical hull Coni(S) of a set S is the set of all conical combinations of vectors in S. Coni(S) is the smallest cone (usually not a circular cone) with vertex at the origin containing the points of S.

Convex Hull

The convex hull Conv(S) of a set S is the set of all convex combinations (combinations that are both affine and conical) of vectors in S . Conv(S) is the smallest convex set containing the points of S. The convex hull of a finite set of points is called a Convex Polytope.

Convex Polyhedron, Convex polytope
A convex polyhedron is the intersection of halfspaces. The feasible region of a linear programming problem is a convex polyhedron. A bounded convex polyhedron is convex polytopes [convex hull of some finite set of points].

LEARNING OBJECTIVES:

1.Gain an understanding of what makes a set convex (or not convex)

2.Learn the shapes (in three dimensions) and become familiar with the definitions of the "hulls" of a set of points (certain convex sets determined by the points) [Conv(S) and Coni(S) will be important for our work]

CRITERIA:

1.Quality of the answers to the Critical Thinking Questions.

2.Quality of group interaction.

RESOURCES:

1.Sections 2.1 & 2.2: Strategic Mathematics.

2.MAPLE 10 and the help system

3.File Activity7.mw on the Public server (the p:-drive - file is Public/Courses/Math/Math438/Activity7.mw)

4.40 minutes

PLAN:

1.Assess the team's understanding of the terms listed in the vocabulary section.

2.Execute the model Activity7.mw [all information is in the Maple document]. Have the recorder write down what happened at each step and any discoveries the team made as the model was executed.

3.Use the understanding you gain to answer the critical thinking questions

CRITICAL THINKING QUESTIONS:

1.In R2 , let C = [3 5]T and k = 15 and sketch the hyperplane { X |CTX = k} , the upper halfspace { X | CTX ≥ k} and the lower halfspace {X | CTX ≤ k}

2.Why will the feasible region for a linear programming problem always be a convex set? Can you prove it? [It’s enough to show that if X, Y satisfy a linear inequality then so does tX + (1-t)Y for every t between 0 and 1]

3.Suppose that we form the set of points {[1 1]T, [1 -1]T }. What is the linear hull of these two points? Draw the affine, conical and convex hulls on paper.

4.Suppose that we form the set of points {[1 1]T, [1 -1]T, [1 2]T }. What is the linear hull of these three points? Draw the affine, conical and convex hulls on paper.

5.Can the convex hull of a finite set of vectors (points) be all of Rn? Why /why not?

6.Can the conical hull of a finite set of vectors (points) be all of Rn? Why /why not?