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

Learn & Enjoy …

Quy hoạch lồi (3) – Bài toán đối ngẫu Lagrange

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

Định nghĩa (hàm Lagrange): Cho bài toán quy hoạch

\mathrm{Opt}(P)=\displaystyle \min_x\left\{f(x):\begin{array}{r} g(x)=(g_1(x),\ldots,g_m(x))^T\leq 0\\ x\in X\end{array}\right\}~~(P)

hàm Lagrange tương ứng của (P)

L(x,\lambda)=f(x)+\displaystyle \sum_{i=1}^m\lambda_i g_i(x), (x,\lambda)\in X\times R.

Định nghĩa (bài toán đối ngẫu Lagrange): Cho bài toán quy hoạch (P) và hàm Lagrange L(x,\lambda) của nó. Nếu đặt

\underline{L}(\lambda)=\displaystyle \inf_{x\in X}L(x,\lambda)

thì bài toán đối ngẫu Lagrange của (P) là bài toán

\displaystyle \mathrm{Opt}(D)=\sup_{\lambda\geq 0} \underline{L}(\lambda)=\sup_{\lambda\geq 0}\inf_{x\in X}L(x,\lambda)~~(D).

Nhận xét:

  1. Hàm L(x,\lambda) được định nghĩa trên tập X\times R và không chịu ràng buộc g_i(x)\leq 0,\forall i.
  2. Hàm \underline{L}(\lambda) là hàm của \lambda vì ta lấy giá trị nhỏ nhất củaL(x,\lambda) trên toàn bộ x\in X.
  3. Khi \lambda\geq 0 ta có L(x,\lambda)\leq f(x), \forall x\in X.

Định lý (tính chất đối ngẫu của bài toán quy hoạch lồi):

  1. Với mọi \lambda\geq 0 ta có \underline{L}(\lambda)\leq\mathrm{Opt}(D) và vì thế
    \mathrm{Opt}(D)\leq \mathrm{Opt}(P)
  2. Nếu (P) là bài toán quy hoạch lồi, bị chặn (dưới) và thỏa mãn điều kiện Slater thì (D) giải được và giá trị tối ưu của hai bài toán (P),(D) bằng nhau:
    \mathrm{Opt}(D)= \mathrm{Opt}(P)

Chứng minh (1): Gọi S_P\subset X là tập các nghiệm chấp nhận được của (P), với mọi \lambda \geq 0, ta có

\underline{L}(\lambda)=\displaystyle \inf_{x\in X}L(x,\lambda)\leq \inf_{x\in S_P}L(x,\lambda)\leq \inf_{x\in S_P}f(x)=\mathrm{Opt}(P).

Suy ra

\mathrm{Opt}(D)=\displaystyle \sup_{\lambda\geq 0}\underline{L}(\lambda)\leq \mathrm{Opt}(P).

Chứng minh (2):(P) bị chặn dưới nên có thể đặt \mathrm{Opt}(P) =\displaystyle\inf_{x\in S_P}f(x), ta có hệ bất phương trình

\begin{cases}f(x)<\mathrm{Opt}(P)\\x\in S_P\end{cases}

\Leftrightarrow \begin{cases}f(x)<\mathrm{Opt}(P)\\g_i(x)\leq 0,i=1,\ldots,m\\x\in X\end{cases}

vô nghiệm. Do X lồi, f,g_i,i=1,\ldots,m là các hàm lồi trên X, các ràng buộc thỏa mãn điều kiện Slater nên theo định lý đảo phải tồn tại \lambda^*\geq 0 sao cho

\displaystyle  \inf_{x\in X}\left[f(x)+\sum_{i=1}^m\lambda_i^*g_i(x) \right] \geq \mathrm{Opt}(P).

tức là \mathrm{Opt}(P)\leq\underline{L}(\lambda^*)\leq \mathrm{Opt}(D). Theo (1), ta có

\underline{L}(\lambda^*)=\mathrm{Opt}(D)=\mathrm{Opt}(P).

Tức là (D) giải được.

Nhận xét:

  1. Kết quả về tính đối ngẫu ở bài toán quy hoạch lồi không cân xứng như bài toán quy hoạch tuyến tính, tuy nhiên trên thực tế, may mắn là điều kiện Slater thường được thỏa mãn nên khi ứng dụng người ta vẫn ngầm coi điều kiện này thỏa mãn và xây dựng bài toán đối ngẫu Lagrange để giải bài toán gốc.
  2. Thuật ngữ: (1) được gọi là tính đối ngẫu yếu (weak duality), (2) được gọi là tính đối ngẫu mạnh (strong duality) khi bài toán quy hoạch lồi bị chặn thỏa mãn điều kiện Slater.

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: