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

Learn & Enjoy …

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

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

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: