Home
> Uncategorized > Convex optimization study notes 2: convex set
Convex optimization study notes 2: convex set
2.1.2 Affine Sets:
- 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
- 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.
- 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 }
- subspace: a space closed at sums and scalar multiplication
- 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.
- any affine set can be expressed as a solution set of a system of linear equations.
- 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.
- The affine hull is the smallest affine set that contains C
- example of affine hull:
2.1.3 Affine dimension and relative interior
- affine dimension of a set C (not dimension of a affine set C): dimension of its affine hull.
- If the affine dimension of a set C ⊆ Rn is less than n, then the set lies in the affine set aff C != Rn
- 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.
- relative boundary of a set C as cl C \ relint C, where cl C is the closure of C.
- example:
2.1.4 Convex set
- 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.
- 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.
- example of convex/nonconvex set:
- 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.
- 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.
- example of convex hull:
- 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
- A set C is called a cone, or nonnegative homogeneous, if for every x ∈ C and θ ≥ 0 (no other requirement) we have θx ∈ C.
- example of cone
- 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.
- 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.
- example of conic hull:
Categories: Uncategorized
math, study note
Comments (0)
Trackbacks (0)
Leave a comment
Trackback