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

Learn & Enjoy …

Archive for Tháng Một, 2009

« Những bài viết trước

Quy hoạch nón (Conic Programming) (3) – Bài toán đối ngẫu (1)

Đăng bởi tqlong on Tháng Một 14, 2009

Ta biết rằng, bài toán quy hoạch tuyến tính

\displaystyle \min_x\{c^Tx: Ax\geq b\} hay \displaystyle Ax-b\in \mathbb{R}^m_+\}\displaystyle (P)

có bài toán đối ngẫu là

\displaystyle \min_\lambda \{b^T\lambda: A^T\lambda = c, \lambda\geq 0\} hay \displaystyle \min_\lambda \{b^T\lambda: A^T\lambda = c, \lambda\in \mathbb{R}^m_+\}\displaystyle (D)

Trong bài này, ta sẽ xem xét khái niệm đối ngẫu của bài toán quy hoạch nón

\displaystyle \min_x \{c^Tx : Ax \geq_K b\} hay \displaystyle \min_x \{c^Tx : Ax-b \in K\}\displaystyle (P)

với \displaystyle K là nón lồi có đỉnh, đóng và có phần trong khác rỗng.

Ta thấy, trong bài toán quy hoạch tuyến tính, bất cứ véctơ \displaystyle \lambda nào thỏa mãn \displaystyle A^T\lambda = c, \lambda \geq 0 \displaystyle (1) thì với mọi \displaystyle x, ta có

\displaystyle c^Tx = (A^T\lambda)^T x = \lambda^T Ax \geq \lambda^T b

Như vậy, nếu \displaystyle \lambda thỏa mãn \displaystyle (1) ta luôn có \displaystyle b^T\lambda là cận dưới của giá trị tối ưu \displaystyle OPT(P) của bài toán gốc. Nghĩa là, về bản chất, bài toán đối ngẫu tìm cách cực đại hóa cận dưới này. Vậy trong bài toán quy hoạch nón thì sao, các điều kiện cần có của \displaystyle \lambda để \displaystyle b^T\lambda luôn là cận dưới của giá trị tối ưu của bài toán gốc là gì ?

Điều kiện đầu tiên vẫn là \displaystyle A^T\lambda = c, còn điều kiện thứ hai chính là

\displaystyle \forall a, b\in \mathbb{R}^m: a\geq_K b \Rightarrow \lambda^T a\geq \lambda^T b
hoặc
\displaystyle \forall a\in K: \lambda^T a\geq 0

với 2 điều kiện này, với mọi \displaystyle x, ta có thể viết

\displaystyle c^Tx = (A^T\lambda)^T x = \lambda^T Ax \geq \lambda^T b

vì \displaystyle Ax\geq_K b. Như vậy, các véctơ \displaystyle \lambda cần thỏa mãn 2 điều kiện

\displaystyle A^T\lambda = c
\displaystyle \lambda\in K_* = \{\xi: \xi^T a\geq 0,\forall a\in K\}

Ta có thể viết bài toán đối ngẫu của bài toán quy hoạch nón gốc như sau

\displaystyle \max_\lambda \{b^T\lambda : A^T\lambda = c, \lambda \in K_*\}

Trong đó \displaystyle K_* gọi là nón đối ngẫu (dual cone) của nón \displaystyle K.

Một số tính chất của nón đối ngẫu:

Tính chất 1: Đối ngẫu \displaystyle (K_*)_* của nón đối ngẫu \displaystyle K_* chính là nón \displaystyle K.

Chứng minh: Xét \displaystyle a\in K, ta có \displaystyle \xi^Ta\geq 0,\forall \xi\in K_*, suy ra \displaystyle a\in (K_*)_*, vậy \displaystyle K\subset (K_*)_*

Xét \displaystyle b\in (K_*)_*, ta có

\displaystyle \forall \xi\in K_*\Rightarrow b^T\xi\geq 0

Vì \displaystyle K là nón lồi thuộc \displaystyle \mathbb{R}^m nên \displaystyle \forall a\in K tồn tại \displaystyle a_1, \ldots, a_m\in K sao cho

\displaystyle a = \alpha_1 a_1 + \ldots \alpha_m a_m, \alpha_i\geq 0 (tổ hợp nón)

Suy ra

\displaystyle \xi^Ta\geq 0,\forall a\in K \Leftrightarrow \xi^Ta_i \geq 0, i=1,\ldots,m

Vậy \displaystyle b^T\xi\geq 0 là hệ quả của hệ bất đẳng thức \displaystyle \xi^Ta_i \geq 0, i=1,\ldots,m. Theo định lý Farkas thuần nhất, phải tồn tại các hệ số không âm \displaystyle \beta_1,\ldots,\beta_m sao cho

\displaystyle b =\beta_1 a_1+\ldots+\beta_m a_m

nghĩa là \displaystyle b\in K, vậy \displaystyle (K_*)_*\subset K. Kết luận \displaystyle (K_*)_*= K.

Tính chất 2: Nếu nón lồi \displaystyle K có đỉnh, đóng và có phần trong khác rỗng thì nón đối ngẫu \displaystyle K_* cũng là nón lồi có đỉnh, đóng và có phần trong khác rỗng.

Chứng minh:

(1): \displaystyle K_* đóng, thật vậy, xét \displaystyle x_i\in K_*, \lim_{i\rightarrow\infty} x_i = x và \displaystyle a\in K bất kì. Do \displaystyle x_i^T a\geq 0 và hàm tuyến tính là hàm liên tục, ta cũng có \displaystyle x^Ta\geq 0 nghĩa là \displaystyle x\in K_*.

(2): \displaystyle K_* là nón lồi, thật vậy nếu \displaystyle x,y\in K_*, hiển nhiên \displaystyle x+y\in K_* và \displaystyle \alpha x\in K_*.

Lưu ý: Chứng minh (1) và (2) không phụ thuộc vào việc \displaystyle K có là nón lồi, có đỉnh, đóng, có phần trong khác rỗng hay không. Nghĩa là \displaystyle K_* luôn là nón lồi đóng với mọi tập \displaystyle K.

(3): \displaystyle K có phần trong khác rỗng \displaystyle \Rightarrow K_* có đỉnh. Thật vậy, xét \displaystyle a,-a\in K_* và \displaystyle a\neq 0. Vì \displaystyle \mathrm{int}K\neq \emptyset, tồn tại \displaystyle x\in \mathrm{int}K, a^Tx \neq 0. Suy ra \displaystyle a^Tx > 0, -a^Tx >0, mâu thuẫn. Vậy \displaystyle a = 0.

(4): \displaystyle K có đỉnh \displaystyle \Rightarrow K_* có phần trong khác rỗng. Để chứng minh (4), ta chỉ cần chứng minh \displaystyle \mathrm{int}K=\emptyset \Rightarrow K_* không có đỉnh và sử dụng tính chất 1 \displaystyle K=(K_*)_* ở trên.

Thật vậy, vì \displaystyle\mathrm{int}K=\emptyset nên \displaystyle \dim K < m nghĩa là nón \displaystyle K nằm trong một không gian \displaystyle L có số chiều nhỏ hơn \displaystyle m. Vậy \displaystyle L^\perp \subset K_*, nghĩa là \displaystyle K_* không có đỉnh.

Nhận xét: Do tính chất (1), mệnh đề ngược lại của tính chất (2) cũng đúng.

Tính chất 3: Đối ngẫu của tích Descartes các nón \displaystyle K_i là tích Descartes của các nón đối ngẫu \displaystyle {K_i}_*.

Nhận xét: Với tính chất này ta có thể nhóm các điều kiện \displaystyle \lambda_i\in {K_i}_* thành một điều kiện duy nhất \displaystyle \lambda=(\lambda_1,\ldots,\lambda_i,\ldots)\in {K_1}_*\times \ldots \times {K_i}_*\times\ldots.

Ví dụ:

  1. Nón tự đối ngẫu (self-dual cone): Dễ thấy nón đối ngẫu của \displaystyle \mathbb{R}^m_+ chính là \displaystyle \mathbb{R}^m_+. Ngoài ra ta còn có nón Lorentz \displaystyle L^m, nón xác định dương \displaystyle S^m_+ cũng là các nón tự đối ngẫu.

Đăng trong Quy hoạch lồi, Quy hoạch nón | Tagged: , , , | Leave a Comment »

Quy hoạch nón (Conic Programming) (2) – Một số nón lồi

Đăng bởi tqlong on Tháng Một 13, 2009

Trong bài toán quy hoạch nón

\displaystyle \min_x \{c^Tx : Ax-b\geq_K 0\}

ta cần định nghĩa nón lồi \displaystyle K.

Nón lồi trong bài toán quy hoạch tuyến tính chính là tập các véc tơ không âm \displaystyle K = \mathbb{R}^m_+ = \{x\in \mathbb{R}^m: x\geq 0\}. Ngoài các tính chất của nón lồi có đỉnh như

  • Khác rỗng
  • Đóng với phép cộng véctơ và phép nhân véctơ với số thực không âm
  • Có đỉnh

thì \displaystyle \mathbb{R}^m_+ còn có 2 tính chất tôpô quan trọng, đó là

  • Là tập đóng: \displaystyle a_i\in \mathbb{R}^m_+, \lim_{i\rightarrow\infty} a_i = a\Rightarrow a\in \mathbb{R}^m_+
  • Có phần trong khác rỗng: \displaystyle \exists x\in \mathrm{int} \mathbb{R}^m_+

Từ giờ trở đi, ta chỉ xét các nón lồi có 5 tính chất trên: khác rỗng, đóng với 2 phép toán véctơ, có đỉnh, là tập đóng và có phần trong khác rỗng.

Ngoài nón lồi \displaystyle \mathbb{R}^m_+, ta còn có

Nón Lorentz (Lorentz cone – còn gọi là nón lồi hình kem ốc quế): là epi-graph của chuẩn \displaystyle L_2.

\displaystyle L^{m} = \left\{x\in \mathbb{R}^m: x_m\geq \sqrt{x_1^2+x_2^2+\ldots+x_{m-1}^2}\right\}

Nón Lorentz

Nón Lorentz

Nón các ma trận đối xứng xác định dương (semi-definite cone):

\displaystyle S^m_+ = \left\{A\in \mathbb{R}^{m\times m}: A=A^T, A\succcurlyeq 0\right\}

Một số bài toán quy hoạch phát biểu thông qua các nón lồi trên:

\displaystyle \min_x \{c^Tx : Ax-b\geq_K 0\}

Quy hoạch tuyến tính (Linear Programming – LP): \displaystyle K = \mathbb{R}^m_+

Quy hoạch nón bậc 2 (Conic Quadratic Programming – CODP): \displaystyle K = L^{m_1}\times L^{m_2}\times\ldots L^{m_k} – tích Descartes của các nón Lorentz

Ví dụ: \displaystyle \min_x \{c^Tx : \|B_i x+ d_i\|_2\leq e_i^Tx+f_i\}

trong đó \displaystyle x\in \mathbb{R}^n, B_i\in \mathbb{R}^{m_i\times n}, d_i\in \mathbb{R}^{m_i}, e_i\in \mathbb{R}^n, f_i\in \mathbb{R}, i=1,\ldots,k. Ta chọn \displaystyle A, b sao cho

\displaystyle Ax-b = \left[\begin{array}{c}B_1 x+ d_1\\e_1^Tx+f_1 \\ \ldots \\ B_k x+ d_k\\e_k^Tx+f_k\end{array} \right]

do \displaystyle\left[\begin{array}{c}B_1 x+ d_1\\e_1^Tx+f_1\end{array} \right]\in L^{m_1+1} nên \displaystyle Ax-b\in K=L^{m_1+1}\times L^{m_2+1}\times\ldots L^{m_k+1}.

Quy hoạch xác định dương (Semi Definite Programming – SDP): \displaystyle K=S^m_+

Ví dụ: \displaystyle \min_x \{c^Tx : A_1 x + A_2 x+\ldots+A_k x-B\succcurlyeq 0\}

Đăng trong Quy hoạch lồi, Quy hoạch nón | Tagged: , , , , , , , , , , | Leave a Comment »

« Những bài viết trước