Line Segments:
• The line segment between two points x and y in ℝn is the set of points on the straight line joining points x and y.
Note that if z lies on the line segment between x and y, then
○ where α is a real number from the interval [0, 1].
• The equation above can be rewritten as z = ax + (1 – α)y. Hence, the line segment between x and y can be represented as
Hyperplanes and Linear Varieties:
Let u1, u2,…, un, υ ∈ ℝ, where at least one of the ui is nonzero. The set of all points x = [x1, x2,…, xn]⊤ that satisfy the linear equation
is called a hyperplane of the space ℝn.
• We may describe the hyperplane by
• A hyperplane is not necessarily a subspace of ℝn since, in general, it does not contain the origin.
○ For n = 2, the equation of the hyperplane has the form u1x1 + u2x2 = υ , which is the equation of a straight line.
• Thus, straight lines are hyperplanes in ℝ2.
○ In ℝ3 (three-dimensional space), hyperplanes are ordinary planes.
• By translating a hyperplane so that it contains the origin of ℝn, it becomes a subspace of ℝn.
• Because the dimension of this subspace is n – 1, we say that the hyperplane has dimension n – 1.
• The hyperplane H = {x : u1x1 +…+ unxn = υ} divides ℝn into two half-spaces.
○ One of these half-spaces consists of the points satisfying the inequality u1x1 +…+ unxn ≥ υ, denoted
○ The other half-space consists of the points satisfying the inequality u1x1 +…+ unxn ≤ υ, denoted
• A linear variety is a set of the form
for some matrix A ∈ ℝm×n and vector b ∈ ℝm.
○ If dim N(A) = r, we say that the linear variety has dimension r.
○ A linear variety is a subspace if and only if b = 0.
○ If A = O, the linear variety is ℝn. Why?
○ If the dimension of the linear variety is less than n, then it is the intersection of a finite number of hyperplanes.
Convex Sets:
Recall that the line segment between two points u, υ ∈ ℝn is the set {w ∈ ℝn : w = αu+ (1 – α)υ, α ∈ [0, 1]}.
• A point w = αu + (1 – α)υ (where α ∈ [0, 1]) is called a convex combination of the points u and υ.
• A set Θ ⊂ ℝn is convex if for all u, υ ∈ Θ, the line segment between u and υ; is in Θ.
○ Here are some examples of convex and non-convex sets.
• Note that Θ is convex if and only if αu + (1 – α)υ ∈ Θ for all u, υ ∈ Θ and α ∈ (0, 1)
• Examples of convex sets include the following:
○ The empty set
○ A set consisting of a single point. How about two points?
○ A line or a line segment
○ A subspace
○ A hyperplane
○ A linear variety
○ A half-space
○ ℝn
Theorem 1
Convex subsets of ℝn have the following properties:
a. If Θ is a convex set and β is a real number, then the set
is also convex.
b. If Θ1 and Θ2 are convex sets, then the set
is also convex.
c. The intersection of any collection of convex sets is convex.
• A point x in a convex set Θ is said to be an extreme point of Θ if there are no two distinct points u and υ in Θ such that x = αu + (1 – α)υ for
some α ∈ (0, 1). Can show some extreme points on the above examples?
Neighborhoods:
A neighborhood of a point x ∈ ℝn is the set
where ε is some positive number.
The neighborhood is also called a ball with radius ε and center x.
• In the plane ℝ2, a neighborhood of x = [x1, x2]⊤ consists of all the points inside a disk centered at x.
• In ℝ3, a neighborhood of x = [x1, x2, x3]⊤ consists of all the points inside a sphere centered at x.
• A point x ∈ S is said to be an interior point of the set S if the set S contains some neighborhood of x; that is, if all points within some
neighborhood of x are also in S.
○ The set of all the interior points of S is called the interior of S.
• A point x is said to be a boundary point of the set S if every neighborhood of x contains a point in S and a point not in S.
○ Note that a boundary point of S may or may not be an element of S. The set of all boundary points of S is called the boundary of S.
• A set S is said to be open if it contains a neighborhood of each of its points; that is, if each of its points is an interior point, or
• equivalently, if S contains no boundary points.
• A set S is said to be closed if it contains its boundary. We can show that a set is closed if and only if its complement is open.
• A set that is contained in a ball (neighborhood) of finite radius is said to be bounded.
• A set is compact if it is both closed and bounded.
Theorem of Weierstrass:
Let f : Ω → ℝ be a continuous function, where Ω ⊂ ℝn is a compact set. Then, there exists a point x0 ∈ Ω such that f(x0) ≤ f(x) for all x ∈
Ω. In other words, f achieves its minimum on Ω.
Polytopes and Polyhedra:
Let Θ be a convex set, and suppose that y is a boundary point of Θ.
• A hyperplane passing through y is called a hyperplane of support (or supporting hyperplane) of the set Θ if the entire set Θ lies completely in
one of the two half-spaces into which this hyperplane divides the space ℝn.
Recall that by Theorem 1 , the intersection of any number of convex sets is convex.
○ In what follows we are concerned with the intersection of a finite number of half-spaces.
• Because every half-space H+ or H– is convex in ℝn, the intersection of any number of half-spaces is a convex set.
• A set that can be expressed as the intersection of a finite number of half-spaces is called a convex polytope
• A nonempty bounded polytope is called a polyhedron
• What is the different of polyhedron and polytope then? Can you show a two-dimensional polyhedron?