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)

Posted by Trần Quốc Long 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)

bài toán đối ngẫu

\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 Knó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

\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

\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\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_*\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_*\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.

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: