Study notes from Convex Optimization by Stephen Boyd, Lieven Vandenberghe.
1. Affine and convex sets
1.1 Lines and line segments
Suppose are two points in . Points of the form
where ，form the line passing through and . The parameter value corresponds to , and the parameter value corresponds to . Values of the parameter between and corresponds to the line segment between and .
1.2 Affine sets
A set is affine sets if the line through any two distinct points in lies in , ,
In other words, contains the linear combination of any two points in , provided the coefficients in the linear combination sum to one. This idea can be generalized to more than two points. We refer to a point of the form , where , as an affine combination of the points .
Using induction from the definition of affine, it can be shown that an affine set contains every affine combination of its points: if is an affine set, , and , the the point . If is an affine set and , then the set
is a subspace, , closed under sums and scalar multiplication. Thus, the affine set can be expressed as , , as a subplace plus an offset. We define the dimension of an affine set as the dimension of the subspace , where is any element of .
The set of all affine combinations of points in some set is called the affine hull of , and denoted :
The affine hull is the smallest affine set that contains , in the following sense: if is any affine set with , then .
We define the affine dimension of a set as the dimension of its affine hull. Affine dimension is useful in the context of convex analysis and optimization, but is not always consistent with other definitions of dimension. If the affine dimension of a set is less than , then the set lies in the affine set . We define the releative interior of the set , denoted , as its interior relative to :
where , the ball of radius and center in the norm . (Here is any norm, all norms define the same relative interior.) We can the define the relative boundary of a set as , where is the closure of .
1.3 Convex sets
A set is convex if the line segment between any two points in lies in , , if for any and any with , we have
Every affine set is also convex, since it contains the entire line between any two distinct points in it, and therefor also the line segment between the points.
We call a point of the form , where and , a convex combination of the points . As with affine sets, it can be shown that a set is convex if and only if it contains every convex combination of its points.
The convex hull of a set , denoted , is the set of all convex combinations of points in :
As the name suggests, the convex hull is always convex. It is the smallest convex set that contains : If is any convex set that contains , then .
The idea of a convex combination can be generalized to include infinite sums, integrals, and, in the most general form, probability distributions. Suppose satisfy
and , where is convex. Then
if the series converges. More generally, suppose satisfies for all and , where is convex. Then
if the integral exists.
In the most general form, suppose is convex and is a random vector with with probability one. The . Indeed, this form includes all the others as special cases.
A set is called a cone, or nonnegative homogeneous, if for every and we have
A set is a convex cone is it is convex and a cone, which means that for any and , we have
A point of the form with is called a conic combination (or a nonnegative linear combination) of . If are in a convex cone , then every conic combination of is in . Conversely, a set is a convex cone if and only if it contains all conic combinations of its elements.
The conic hull of a set is the set of all conic combinations of points in , ,
The conic hull is also the the smallest convex cone that contains .
3. Hyperplanes and halfspaces
A hyperplane is a set of the form
where and . Analytically it is the solution set of a nontrivial linear equation among the components of (and hence an affine set). The geometric interpretation can be understood by expressing the hyperplane in the form
where is any point in the hyperplane (, any point that satisfies ). This representation can in turn be expressed as
where denotes the orthogonal complement of , , the set of all vectors orthogonal to it:
This shows that the hyperplane consists of an offset , plus all vectors orthogonal to the vector .
A hyperplane divides into two halfspaces. A (closed) halfspace is a set of the form
where , , the solution set of one (nontrivial) linear inequality. Halfspaces are convex, but not affine. The halfspace can also be expressed as
Where is any point on the associated hyperplane, , satisfies . The representation suggest a simple geometric interpretation: the halfspace consists of plus any vector makes an obtuse (or right) angle with the vector . The boundary of the halfspace is the hyperplane . The set , which is the interior of the halfspace , is called an open halfspace.
4. Euclidean balls and ellipsoids
4.1 Euclidean balls
A Euclidean ball (or just ball) in has the form
where , and denotes the Euclidean norm, , . The vector is the center of the ball and the scalar is its radius. consists of all points within a distance of the center . Another common representation for Euclidean ball is
A Euclidean ball is a convex set: if ,and , then
A related family of convex sets is the ellipsoids, which have the form
where , , is symmetric and positive definite. The vector is the center of the ellipsoid. The matrix determines how far the ellipsoid extends in every direction from . The lengths of the semi-axes of are given by , where are the eigenvalues of . A ball is an ellipsoid with . Another common representation of an ellipsoid is
where is square and nonsingular. In this representation we can assume without loss of generality that is symmetric and positive definite. By taking , this representation gives the ellipsoid defined in . When the matrix in is symmetric positive semidefinite but singular, the set in is called a degenerate ellipsoid. Its affine dimension is equal to the rank of . Degenrate elliposids are also convex.
5. Norm balls and norm cones
5.1 Norm balls
Suppose is any norm on . From the general properties of norms it can be shown that a norm ball of radius and center , given by
Norm ball is convex.
5.2 Norm cones
The norm cone associated with the norm is the set
Norm cone is also a convex cone.
A polyhedron is defined as the solution set of a finite number of linear equalities and inequalities:
A polyhedron is thus the intersection of a finite number of halfspaces and hyperplanes. Affine sets, rays, line segments, and halfspaces are all polyhedra. It is easily shown that polyhedra are convex sets. A bounded polyhedron is sometimes called a polytope, but some authors use the opposite convention (, polytope for any set of the form , and polyhedron when it is bounded). It will be convenient to use the compact notation
where the symbol denotes vector inequality or componentwise inequality in : means for .
Simplexes are another important family of polyhedra. Suppose the points are affinely independent, which means are linearly independent. The simplex determined by them is given by
Where denotes the vector with all entries one. The affine dimension of this simplex is , so it is sometimes referred to as a -dimensional simplex in .
8. Positive semidefinite cone
We use the notation to denote the set of symmetric matrices,
which is a vector space with dimension . We use the notation to denote the set of symmetric positive semidefinite matrices:
and the notation to denote the set of symmetric positive definite matrices:
(This notation is meant to be analogous to , which denotes the nonnegative reals, and , which denotes the positive reals.)
The set is a positive semidefinite cone. Obviously, is also a convex cone: if and , then . This can be seen directly from the definition of positive semidefiniteness: for any , we have
if and .
- 1. Affine and convex sets
- 2. Cones
- 3. Hyperplanes and halfspaces
- 4. Euclidean balls and ellipsoids
- 5. Norm balls and norm cones
- 6. Polyhedra
- 7. Simplexes
- 8. Positive semidefinite cone