CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Tập lồi (3) – Phép toán giữ nguyên tính lồi

Posted by Trần Quốc Long on Tháng Hai 11, 2008

Định lý: Các phép toán sau đây giữ nguyên tính lồi

  1. Phép giao: NếuX_\alpha, \alpha\in\Lambda lồi thì\displaystyle \bigcap_{\alpha\in\Lambda}X_\alpha lồi.
  2. Tích Đề-các: NếuX_i\subset \mathbb{R}^{n_i},i=1,\ldots,m lồi thìX=X_1\times\ldots\times X_m\subset \mathbb{R}^{n_1+\ldots+n_m} lồi.
  3. Tổ hợp tuyến tính: NếuX_i\subset \mathbb{R}^n,i=1,\ldots,m lồi thì\lambda_1 X_1+\ldots+\lambda_m X_m lồi.
  4. Biến đổi affine: Nếu X\subset \mathbb{R}^n lồi thì tập Y=\{y:y=Ax+b,x\in X\} lồi.
  5. Biến đổi ngược của biến đổi affine: Nếu X\subset \mathbb{R}^n lồi thì tập Y=\{y:Ay+b\in X\} lồi.

Chứng minh (1): hiển nhiên vì giao của các tập chứa đoạn thẳng \left[x,y \right] nếu đoạn thẳng này nằm trong tất cả các tập.

Chứng minh (2): hiển nhiên (dùng định nghĩa).

Chứng minh (3): hiển nhiên (dùng định nghĩa).

Chứng minh (4): Nếu y_1,y_2\in Y, suy ra y_1=Ax_1+b, y_2=Ax_2+b. Nếu z=\lambda y_1+(1-\lambda)y_2 thì z=A(\lambda x_1+(1-\lambda)x_2)+b, nghĩa là z\in Y.

Chứng minh (5): Nếu y_1,y_2\in Y, suy ra x_1=Ay_1+b, x_2=Ay_2+b\in X. Nếu z=\lambda y_1+(1-\lambda)y_2 thìAz+b=A(\lambda y_1+(1-\lambda)y_2)+b=\lambda x_1+(1-\lambda)x_2\in X, nghĩa là z\in Y.

Ví dụ:

  1. Tập X=\{x:Ax\leq b\} lồi vì X=\bigcap_i\{a_i^Tx\leq b_i\}.
  2. Tập Y=\{y:\exists x\in X, x\leq y\} lồi vì Y=X+\mathbb{R}_+^n.
  3. Tập Z=\{z:\exists y\in Y, |z_i-y_i|\leq \epsilon,\forall i\} lồi vì:
    + Tập Y_i là lân cận \epsilon của phép chiếu Y lên trục y_i là tập lồi.
    + TậpZ=Y_1\times\ldots\times Y_n là tập lồi.

Định lý: Đối với các nón lồi ta có các phép toán sau đây

  1. Giao của các nón lồi là nón lồi.
    \displaystyle \bigcap_{\alpha\in\Lambda}C_\alpha là nón lồi nếuC_\alpha,\alpha\in\Lambda là nón lồi
  2. Tổ hợp tuyến tính các nón lồi là nón lồi.
    \displaystyle \sum_{i=1}^n\lambda_i C_i,\lambda_i\in \mathrm{R} là nón lồi nếu C_i,i=1,\ldots,n là nón lồi.
  3. Tích Đề-các: NếuX_i\subset \mathbb{R}^{n_i},i=1,\ldots,m là nón lồi thìX=X_1\times\ldots\times X_m\subset \mathbb{R}^{n_1+\ldots+n_m} là nón lồi.
  4. Biến đổi affine: Nếu X\subset \mathbb{R}^n là nón lồi thì tập Y=\{y:y=Ax+b,x\in X\} là nón lồi.
  5. Biến đổi ngược của biến đổi affine: Nếu X\subset \mathbb{R}^n là nón lồi thì tập Y=\{y:Ay+b\in X\} là nón lồi.

Chứng minh (1): Giao của nón lồi là tập lồi, đồng thời nếu tia \{\lambda x,\lambda\geq 0\} thuộc vào tất cả các nón thì nó thuộc vào giao của các nón.

Chứng minh (2): Tổ hợp nón của các nón lồi là tập lồi (định lý trên). Nếu tia \{\lambda x,\lambda\geq 0\} với x nằm trong tổ hợp nón của các nón lồi rõ ràng cũng nằm trong tổ hợp nón của các nón lồi. Để thấy tổ hợp tuyến tính của các nón lồi cũng là nón lồi, lưu ý rằng nếu C là nón lồi thì -C cũng là nón lồi.

Chứng minh (3),(4),(5): Tương tự như chứng minh (1),(2).

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: