Bộ lồi

WebSlides: Why WebSlides is so inspiring?

Tập lồi (convex sets)

Tập hợp affine và tập lồi
Một số ví dụ quan trọng
Các phép toán bảo toàn độ lồi
Bất bình đẳng tổng quát
Tách và hỗ trợ siêu phẳng
Hình nón kép và bất đẳng thức tổng quát

Affine set

đường thẳng: đi qua hai đểm $x_{1}, x_{2}$

x = θ x_{1} + (1 - θ) x_{2} (θ \in R)

tập hợp affine: chứa đường thẳng đi qua hai điểm phân biệt bất kỳ trong tập hợp

ví dụ: tập nghiệm của phương trình tuyến tính ${x ∣ A x = b}$

(ngược lại, mọi tập hợp affine có thể được biểu diễn dưới dạng tập nghiệm của hệ phương trình tuyến tính)

Tập lồi

đoạn thẳng: giữa hai đểm $x_{1}, x_{2}$

x = θ x_{1} + (1 - θ) x_{2}

với $0 \leq θ \leq 1$

tập lồi: chứa đoạn thẳng giữa hai điểm bất kỳ trong tập hợp

x_{1}, x_{2} \in C, 0 \leq θ \leq 1 ⟹ θ x_{1} + (1 - θ) x_{2} \in C

ví dụ: (một tập hợp lồi, hai tập hợp không lồi)

Tổ hợp lồi và bao lồi

tổ hợp lồi (Convex combination): của $x_{1}, \dots, x_{k} :$ là bất kỳ điểm $x$ của hình thức

x = θ_{1} x_{1} + θ_{2} x_{2} + \dots + θ_{k} x_{k}

với $θ_{1} + \dots + θ_{k} = 1, θ_{i} \geq 0$

$P$ thuộc tổ hợp lồi của $x_{1}, x_{2}, x_{3}$ còn $Q$ thì không

bao lồi (convex hull, conv $S$ ): tập hợp lồi nhỏ nhất chứa $S$

Nón lồi

tổ hợp lồi không âm:(conic nonnegative combination) của $x_{1} v à x_{2}$ là bất kỳ điểm $x$ của hình thức

x = θ_{1} x_{1} + θ_{2} x_{2}

với $θ_{1} \geq 0, θ_{2} \geq 0$

hình nón lồi:(convex cone) tập hợp chứa tất cả các tổ hợp hình nón của các điểm trong tập hợp

Siêu phẳng và nửa không gian

siêu phẳng:tập hợp của hình thức ${x ∣ a^{T} x = b} (a \neq 0)$

Trong không gian Euclid $n$ chiều, siêu phẳng là khái niệm mở rộng của mặt phẳng lên thành $n - 1$ chiều. Ví dụ, trong không gian 3 chiều, siêu phẳng chính là mặt phẳng 2 chiều. Trong không gian 2 chiều, siêu phẳng là đường thẳng 1 chiều. Siêu phẳng tách đôi không gian.

nửa không gian:tập hợp của hình thức ${x ∣ a^{T} x \leq b} (a \neq 0)$

hình nón lồi:(convex cone) tập hợp chứa tất cả các tổ hợp hình nón của các điểm trong tập hợp

$a$ là vectơ pháp tuyến
siêu mặt phẳng là affine và lồi; nửa không gian lồi

Euclidean balls và ellipsoids

(Euclidean) ball với tâm $x_{c}$ và bán kính $r$

B (x_{c}, r) = {x ∣ {‖ x - x_{c} ‖}_{2} \leq r} = {x_{c} + r u ∣ ‖ u ‖_{2} \leq 1}

ellipsoid: tập hợp có dạng

{x ∣ {(x - x_{c})}^{T} P^{- 1} (x - x_{c}) \leq 1}

với $P \in S_{+ +}^{n} ($ i.e., $P$ symmetric positive definite)

đại diện khác: ${x_{c} + A u ∣ ‖ u ‖_{2} \leq 1}$ với A square và nonsingular

Tham khảo:

Norm balls và norm cones

norm: một function $‖ \cdot ‖$ thỏa mãn

$‖ x ‖ \geq 0; ‖ x ‖ = 0$ nếu và chỉ nếu $x = 0$
$‖ t x ‖ = | t | ‖ x ‖$ với $t \in R$
$‖ x + y ‖ \leq ‖ x ‖ + ‖ y ‖$

ký hiệu: $‖ \cdot ‖$ là chung chung (không xác định) của norm; $‖ \cdot ‖_{symb}$ là trường hợp cụ thể của norm

norm ball với tâm $x_{c}$ và bán kính $r : {x ∣ ‖ x - x_{c} ‖ \leq r}$

norm cone: ${(x, t) ∣ ‖ x ‖ \leq t}$

Khối đa diện

tập nghiệm của nhiều bất phương trình tuyến tính và phương trình bằng nhau (siêu phẳng)

A x ⪯ b, C x = d

$(A \in R^{m \times n}, C \in R^{p \times n}, ⪯$ là bất bình đẳng từng thành phần $)$

đa diện là giao của một số hữu hạn các nửa không gian và siêu mặt phẳng

Positive semidefinite cone

ký hiệu:

$S^{n}$ tập hợp $n \times n$ matrix đối xứng
$S_{+}^{n} = {X \in S^{n} ∣ X ⪰ 0}$ : positive semidefinite $n \times n$ matrices $X \in S_{+}^{n} ⟺ z^{T} X z \geq 0 for all z$ $S_{+}^{n}$ là một hình nón lồi
$S_{+ +}^{n} = {X \in S^{n} ∣ X ≻ 0}$ : positive definite $n \times n$ matrices

ví dụ: $X = [\begin{array}{ll} x & y \\ y & z \end{array}] \in S_{+}^{2} ⟺ x \geq 0, z \geq 0, x z \geq y^{2}$

Các phép toán bảo toàn độ lồi

các phương pháp thực tế để xác định độ lồi của một tập hợp $C$

áp dụng định nghĩa: $x_{1}, x_{2} \in C, 0 \leq θ \leq 1 ⟹ θ x_{1} + (1 - θ) x_{2} \in C$
chỉ ra rằng $C$ nhận được từ các tập lồi đơn giản (siêu phẳng, nửa không gian, norm balls,...) bằng các phép toán bảo toàn độ lồi
- intersection
- affine functions
- perspective function
- linear-fractional functions

Affine function

giả sử $f : R^{n} \to R^{m}$ là affine $(f (x) = A x + b$ với $A \in R^{m \times n}, b \in R^{m})$ khi đó

ảnh của một tập lồi dưới $f$ là tập lồi $S \subseteq R^{n} convex ⟹ f (S) = {f (x) ∣ x \in S} convex$
ảnh nghịch đảo ảnh $f^{- 1} (C)$ của một tập lồi dưới $f$ là lồi $C \subseteq R^{m} convex ⟹ f^{- 1} (C) = {x \in R^{n} ∣ f (x) \in C} convex$

ví dụ: scaling, translation, projection

Perspective và hàm phân số tuyến tính

perspective function $P : R^{n + 1} \to R^{n}$ $P (x, t) = x / t, dom P = {(x, t) ∣ t > 0}$

ảnh và ảnh nghịch đảo của tập lồi dưới perspective là tập lồi

hàm phân số tuyến tính $f : R^{n} \to R^{m}$ $f (x) = \frac{A x + b}{c^{T} x + d}, dom f = {x ∣ c^{T} x + d > 0}$

ảnh và ảnh nghịch đảo của tập lồi theo hàm phân số tuyến tính là lồi

Affine set

đường thẳng: đi qua hai đểm $x_{1}, x_{2}$

x = θ x_{1} + (1 - θ) x_{2} (θ \in R)

tập hợp affine: chứa đường thẳng đi qua hai điểm phân biệt bất kỳ trong tập hợp

ví dụ: tập nghiệm của phương trình tuyến tính ${x ∣ A x = b}$

(ngược lại, mọi tập hợp affine có thể được biểu diễn dưới dạng tập nghiệm của hệ phương trình tuyến tính)

Tập lồi

đoạn thẳng: giữa hai đểm $x_{1}, x_{2}$

x = θ x_{1} + (1 - θ) x_{2}

với $0 \leq θ \leq 1$

tập lồi: chứa đoạn thẳng giữa hai điểm bất kỳ trong tập hợp

x_{1}, x_{2} \in C, 0 \leq θ \leq 1 ⟹ θ x_{1} + (1 - θ) x_{2} \in C

ví dụ: (một tập hợp lồi, hai tập hợp không lồi)

Tổ hợp lồi và bao lồi

tổ hợp lồi (Convex combination): của $x_{1}, \dots, x_{k} :$ là bất kỳ điểm $x$ của hình thức

x = θ_{1} x_{1} + θ_{2} x_{2} + \dots + θ_{k} x_{k}

với $θ_{1} + \dots + θ_{k} = 1, θ_{i} \geq 0$

$P$ thuộc tổ hợp lồi của $x_{1}, x_{2}, x_{3}$ còn $Q$ thì không

bao lồi (convex hull, conv $S$ ): tập hợp lồi nhỏ nhất chứa $S$

Nón lồi

tổ hợp lồi không âm:(conic nonnegative combination) của $x_{1} v à x_{2}$ là bất kỳ điểm $x$ của hình thức

x = θ_{1} x_{1} + θ_{2} x_{2}

với $θ_{1} \geq 0, θ_{2} \geq 0$

hình nón lồi:(convex cone) tập hợp chứa tất cả các tổ hợp hình nón của các điểm trong tập hợp

Siêu phẳng và nửa không gian

siêu phẳng:tập hợp của hình thức ${x ∣ a^{T} x = b} (a \neq 0)$

nửa không gian:tập hợp của hình thức ${x ∣ a^{T} x \leq b} (a \neq 0)$

hình nón lồi:(convex cone) tập hợp chứa tất cả các tổ hợp hình nón của các điểm trong tập hợp

$a$ là vectơ pháp tuyến
siêu mặt phẳng là affine và lồi; nửa không gian lồi

Euclidean balls và ellipsoids

(Euclidean) ball với tâm $x_{c}$ và bán kính $r$

B (x_{c}, r) = {x ∣ {‖ x - x_{c} ‖}_{2} \leq r} = {x_{c} + r u ∣ ‖ u ‖_{2} \leq 1}

ellipsoid: tập hợp có dạng

{x ∣ {(x - x_{c})}^{T} P^{- 1} (x - x_{c}) \leq 1}

với $P \in S_{+ +}^{n} ($ i.e., $P$ symmetric positive definite)

đại diện khác: ${x_{c} + A u ∣ ‖ u ‖_{2} \leq 1}$ với A square và nonsingular

Tham khảo:

Norm balls và norm cones

norm: một function $‖ \cdot ‖$ thỏa mãn

$‖ x ‖ \geq 0; ‖ x ‖ = 0$ nếu và chỉ nếu $x = 0$
$‖ t x ‖ = | t | ‖ x ‖$ với $t \in R$
$‖ x + y ‖ \leq ‖ x ‖ + ‖ y ‖$

ký hiệu: $‖ \cdot ‖$ là chung chung (không xác định) của norm; $‖ \cdot ‖_{symb}$ là trường hợp cụ thể của norm

norm ball với tâm $x_{c}$ và bán kính $r : {x ∣ ‖ x - x_{c} ‖ \leq r}$

norm cone: ${(x, t) ∣ ‖ x ‖ \leq t}$

Khối đa diện

tập nghiệm của nhiều bất phương trình tuyến tính và phương trình bằng nhau (siêu phẳng)

A x ⪯ b, C x = d

$(A \in R^{m \times n}, C \in R^{p \times n}, ⪯$ là bất bình đẳng từng thành phần $)$

đa diện là giao của một số hữu hạn các nửa không gian và siêu mặt phẳng

Positive semidefinite cone

ký hiệu:

$S^{n}$ tập hợp $n \times n$ matrix đối xứng
$S_{+}^{n} = {X \in S^{n} ∣ X ⪰ 0}$ : positive semidefinite $n \times n$ matrices $X \in S_{+}^{n} ⟺ z^{T} X z \geq 0 for all z$ $S_{+}^{n}$ là một hình nón lồi
$S_{+ +}^{n} = {X \in S^{n} ∣ X ≻ 0}$ : positive definite $n \times n$ matrices

ví dụ: $X = [\begin{array}{ll} x & y \\ y & z \end{array}] \in S_{+}^{2} ⟺ x \geq 0, z \geq 0, x z \geq y^{2}$

Các phép toán bảo toàn độ lồi

các phương pháp thực tế để xác định độ lồi của một tập hợp $C$

áp dụng định nghĩa: $x_{1}, x_{2} \in C, 0 \leq θ \leq 1 ⟹ θ x_{1} + (1 - θ) x_{2} \in C$
chỉ ra rằng $C$ nhận được từ các tập lồi đơn giản (siêu phẳng, nửa không gian, norm balls,...) bằng các phép toán bảo toàn độ lồi
- intersection
- affine functions
- perspective function
- linear-fractional functions

Affine function

giả sử $f : R^{n} \to R^{m}$ là affine $(f (x) = A x + b$ với $A \in R^{m \times n}, b \in R^{m})$ khi đó

ảnh của một tập lồi dưới $f$ là tập lồi $S \subseteq R^{n} convex ⟹ f (S) = {f (x) ∣ x \in S} convex$
ảnh nghịch đảo ảnh $f^{- 1} (C)$ của một tập lồi dưới $f$ là lồi $C \subseteq R^{m} convex ⟹ f^{- 1} (C) = {x \in R^{n} ∣ f (x) \in C} convex$

ví dụ: scaling, translation, projection

Perspective và hàm phân số tuyến tính

perspective function $P : R^{n + 1} \to R^{n}$ $P (x, t) = x / t, dom P = {(x, t) ∣ t > 0}$

ảnh và ảnh nghịch đảo của tập lồi dưới perspective là tập lồi

hàm phân số tuyến tính $f : R^{n} \to R^{m}$ $f (x) = \frac{A x + b}{c^{T} x + d}, dom f = {x ∣ c^{T} x + d > 0}$

ảnh và ảnh nghịch đảo của tập lồi theo hàm phân số tuyến tính là lồi

Tập lồi (convex sets)

Affine set

Tập lồi

Tổ hợp lồi và bao lồi

Nón lồi

Siêu phẳng và nửa không gian

Euclidean balls và ellipsoids

Norm balls và norm cones

Khối đa diện

Positive semidefinite cone

Các phép toán bảo toàn độ lồi

Intersection

Affine function

Perspective và hàm phân số tuyến tính

Bất bình đẳng tổng quát

Intersection

Intersection

Tập lồi (convex sets)

Affine set

Tập lồi

Tổ hợp lồi và bao lồi

Nón lồi

Siêu phẳng và nửa không gian

Euclidean balls và ellipsoids

Norm balls và norm cones

Khối đa diện

Positive semidefinite cone

Các phép toán bảo toàn độ lồi

Intersection

Affine function

Perspective và hàm phân số tuyến tính

Bất bình đẳng tổng quát

Intersection

Intersection