Affine set
đường thẳng: đi qua hai đểm $x_{1}, x_{2}$
$$ x=\theta x_{1}+(1-\theta) x_{2} \quad(\theta \in \mathbf{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 \mid 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=\theta x_{1}+(1-\theta) x_{2} $$với $0 \leq \theta \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, \quad 0 \leq \theta \leq 1 \quad \Longrightarrow \quad \theta x_{1}+(1-\theta) 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}, \ldots, x_{k}:$ là bất kỳ điểm $x$ của hình thức
$$ x=\theta_{1} x_{1}+\theta_{2} x_{2}+\cdots+\theta_{k} x_{k} $$với $\theta_{1}+\cdots+\theta_{k}=1, \theta_{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=\theta_{1} x_{1}+\theta_{2} x_{2} $$với $\theta_{1} \geq 0, \theta_{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 $\left\{x \mid a^{T} x=b\right\}(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 $\left\{x \mid a^{T} x \leq b\right\}(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
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 \preceq b, \quad C x=d $$$\left(A \in \mathbf{R}^{m \times n}, C \in \mathbf{R}^{p \times n}, \preceq\right.$ 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:
- $\mathbf{S}^{n}$ tập hợp $n \times n$ matrix đối xứng
- $\mathbf{S}_{+}^{n}=\left\{X \in \mathbf{S}^{n} \mid X \succeq 0\right\}$ : positive semidefinite $n \times n$ matrices $$ X \in \mathbf{S}_{+}^{n} \Longleftrightarrow z^{T} X z \geq 0 \text { for all } z $$ $\mathbf{S}_{+}^{n}$ là một hình nón lồi
- $\mathbf{S}_{++}^{n}=\left\{X \in \mathbf{S}^{n} \mid X \succ 0\right\}$ : positive definite $n \times n$ matrices
ví dụ: $X=\left[\begin{array}{ll}x & y \\ y & z\end{array}\right] \in \mathbf{S}_{+}^{2} \Longleftrightarrow x \geq 0, \quad z \geq 0, \quad x z \geq y^{2}$
