Convex optimization study notes 2: convex set

2.1.2 Affine Sets:

1. A set C ⊆ Rn is affine if the line through(直线） any two distinct points in C lies in C,  i.e., if for any x1, x2 ∈ C and θ ∈ R, we have θx1+(1 − θ)x2 ∈ C
2. affine combination: a1x1+a2x2+a3x3+… where x1,x2,x3…belongs to affine set C, and a1+a2+…an=1; the affine combination belongs to C too.
3. dimension of an affine set C : is defined as the dimension of the subspace V=C-x0，x0 is any elements belongs to C. a affine set can be expressed  by C = V + x0 = {v + x0 | v ∈ V }
4. subspace: a space closed at sums and scalar multiplication
5. example: solution of Ax=b is a affine set, and the subspace V associated this affine set is the nullspace of A, i.e., the solution of Ax=0.
6. any affine set can be expressed as a solution set of a system of linear equations.
7. affine hull: the set of all affine combinations of points in some set C(C is not necessary to be affine set)  is called affine null, denoted as aff C.
8. The affine hull is the smallest affine set that contains C
9. example of affine  hull：

2.1.3 Affine dimension and relative interior

1. affine dimension of a set C (not dimension of a affine set C): dimension of its affine hull.
2. If the affine dimension of a set C ⊆ Rn is less than n, then the set lies in the affine set aff C  != Rn
3. relative interior of the set C, denoted relint C:  relint C = {x ∈ C | B(x, r) ∩ aff C ⊆ C for some r > 0}, where B(x, r) = {y: norm(y-x) ≤ r}  the ball of radius r and center x in the norm.
4. relative boundary of a set C as cl C \ relint C, where cl C is the closure of C.
5. example:

2.1.4 Convex set

1. convex set: a set C is convex if the line segment (线段） between any two points in C lies in C, i.e., if for any x1, x2 ∈ C and any θ with 0 ≤ θ ≤ 1, we have  θx1 (1 − θ)x2 ∈ C.
2. Roughly speaking, a set is convex if every point in the set can be seen by every other point, along an unobstructed straight path between them, where unobstructed means lying in the set.
3. example of convex/nonconvex set:
4. convex combination: we call a point of the form θ1×1 + · · · + θkxk, where θ1 + · · · + θk= 1 and θi ≥ 0, i = 1, . . . , k, a convex combination of the points x1, . . ., xk; A convex combination of points can be thought of as a mixture or weighted average of the points, with θi the fraction of xi in the mixture.
5. convex hull: conv C = {θ1×1 + · · · + θkxk| xi ∈ C, θi ≥ 0, i = 1, . . . , k, θ1 + · · · + θk= 1}. the convex hull conv C is always convex. It is the smallest convex set that contains C.
6. example of convex hull:
7. The idea of a convex combination can be generalized to include infinite sums, in-tegrals, and, in the most general form, probability distributions.

2.1.5 cones

1. A set C is called a cone, or nonnegative homogeneous, if for every x ∈ C and θ ≥ 0 (no other requirement) we have θx ∈ C.
2. example of cone
3. A set C is a convex cone if it is convex and a cone, which means that for any x1, x2 ∈ C and θ1, θ2 ≥ 0, we have θ1×1 + θ2×2 ∈ C.
4.  conic hull of set C is the set of all conic combinations of points in C, i.e., {θ1×1 + · · · + θkxk|xi ∈ C, θi ≥ 0, i = 1, . . . , k},which is also the smallest convex cone that contains C.
5. example of conic hull: