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

Learn & Enjoy …

«
»

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.

Bài viết này được đăng vào Tháng Một 14, 2009 lúc 7:09 chiều và tập tin được lưu ở Quy hoạch lồi, Quy hoạch nón. Tagged: , , , . Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể bỏ qua phần còn lại và gửi phản hồi. Ping đã bị khóa.

Để lại hồi âm

XHTML: Bạn có thể sử dụng những thẻ sau: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

«
»