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

Learn & Enjoy …

Quy hoạch lồi (4) – Nhìn từ góc độ trò chơi, điểm yên ngựa

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

Nếu ta định nghĩa

\overline{L}(x)=\displaystyle \sup_{\lambda\geq 0}L(x,\lambda)=\sup_{\lambda\geq 0}\left[ f(x)+\sum_{i=1}^m\lambda_i g_i(x)\right]

thì ta có

\overline{L}(x)=\begin{cases}f(x)&x\in S_P\\+\infty&x\notin S_P\end{cases}

vì khi x\notin S_P, ta có \exists i:g_i(x)>0, cho \lambda_i\rightarrow \infty ta có L(x,\lambda) không bị chặn. Như vậy

\displaystyle \inf_{x\in X}\overline{L}(x)=\inf_{x\in S_P}f(x)=\mathrm{Opt} (P).

Vậy bài toán gốc là bài toán minimax:

\mathrm{Opt}(P)=\displaystyle \inf_{x\in X}\sup_{\lambda\geq 0}L(x,\lambda)

còn bài toán đối ngẫu (D) là bài toán maximin:

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

Tổng quát hóa lên ta có trò chơi sau: Cho hàm F(x,\lambda), (x,\lambda)\in X\times\Lambda\subset\mathbb{R}^n \times \mathbb{R}^m  . Hai người A và B chọn hai véctơ x\lambda. Sau đó A phải đưa cho B F(x,\lambda) đồng (trường hợp F(x,\lambda)>0 là A mất tiền, trường hợp F(x,\lambda)< 0 là A được tiền).

Xét các kiểu chơi sau đây:

  1. A chọn x trước, B chọn \lambda sau: rõ ràng, nếu B là người chơi không tồi B sẽ chọn \lambda tốt nhất có thể sao cho B được lượng tiền bằng
    \overline{F}(x)=\displaystyle \sup_{\lambda\in\Lambda}F(x,\lambda)

    Vì vậy nếu A là người chơi không tồi, A phải chọn x sao cho A chỉ phải đưa cho B lượng tiền bằng

    \mathrm{Opt}(P)=\displaystyle \inf_{x\in X}\overline{F}(x)= \inf_{x\in X}\sup_{\lambda\in\Lambda}F(x,\lambda).
  2. B chọn \lambda trước, A chọn x sau: rõ ràng, nếu A là người chơi không tồi A sẽ chọn x tốt nhất có thể sao cho B chỉ được lượng tiền bằng
    \underline{F}(\lambda)=\displaystyle \inf_{x\in X}F(x,\lambda)

    Vì vậy nếu B là người chơi không tồi, B phải chọn \lambda sao cho A phải đưa cho B lượng tiền bằng

    \mathrm{Opt}(D)=\displaystyle \sup_{\lambda\in\Lambda}\underline{F}(\lambda)= \sup_{\lambda\in\Lambda}\inf_{x\in X}F(x,\lambda).

Trong 2 kiểu chơi này, kiểu chơi nào có lợi hơn đối với A (thiệt hơn đối với B)? Định lý sau đây có kết quả tương tự như tính đối ngẫu yếubài trước.

Định lý (người đi sau có lợi hơn): Nếu cả hai đều chơi không tồi thì số tiền A phải đưa cho B nếu A đi sau không lớn hơn nếu A đi trước, nghĩa là ta luôn có

\mathrm{Opt}(D)\leq \mathrm{Opt}(P)

Chứng minh: Do \mathrm{Opt}(P)=\displaystyle \inf_{x\in X}\overline{F}(x) nên với mọi \epsilon>0 tồn tại x^* sao cho

\mathrm{Opt}(P)+\epsilon\geq \overline{F}(x^*)=\displaystyle \sup_{\lambda\in\Lambda}F(x^*,\lambda).

Tức là \mathrm{Opt}(P)+\epsilon\geq F(x^*,\lambda),\forall \lambda. Suy ra

\mathrm{Opt}(P)+\epsilon\geq\displaystyle \inf_{x\in X}F(x,\lambda), \forall \lambda

hay \mathrm{Opt}(P)+\epsilon\geq \displaystyle \sup_{\lambda\in\Lambda}\inf_{x\in X}F(x,\lambda)=\mathrm{Opt}(D). Bất đẳng thức đúng với mọi \epsilon>0 nên ta có kết luận

\mathrm{Opt}(D)\leq \mathrm{Opt}(P).

Bây giờ ta xét một kiểu chơi khác: Nếu A và B chọn x,\lambda cùng lúc, trong trường hợp nào cả hai đều có thể đảm bảo lựa chọn của mình là tối ưu? Người ta chứng minh rằng, nếu đồ thị của hàm F(x,\lambda) có những điểm đặc biệt gọi là điểm yên ngựa (saddle point) thì A và B sẽ đảm bảo được lựa chọn đồng thời của hai người là tối ưu, theo nghĩa là tại điểm tối ưu này, A và B đều không có lựa chọn nào tốt hơn nếu đối phương giữ nguyên lựa chọn của mình.

Định nghĩa (điểm yên ngựa): Điểm (x^*,\lambda^*)\in X\times\Lambda gọi là điểm yên ngựa của hàm F(x,\lambda) nếu

F(x,\lambda^*)\geq F(x^*,\lambda^*)\geq F(x^*,\lambda), \forall (x,\lambda) \in X\times\Lambda.

Định lý (điều kiện tồn tại điểm yên ngựa): Hàm F(x,\lambda) có điểm yên ngựa (x^*,\lambda^*) nếu và chỉ nếu hai bài toán (P),(D) đều giải được và có giá trị tối ưu bằng nhau:

\mathrm{Opt}(D)= \mathrm{Opt}(P).

Khi đó x^* là nghiệm tối ưu của (P)\lambda^* là nghiệm tối ưu của(D).

Chứng minh:

\Rightarrow “: Giả sử hàm (x^*,\lambda^*) là điểm yên ngựa của F(x,\lambda), ta có

F(x^*,\lambda^*)=\displaystyle \sup_{\lambda\in\Lambda}F(x^*,\lambda)\geq \inf_{x\in X}\sup_{\lambda\in\Lambda}F(x,\lambda)=\mathrm{Opt}(P)

F(x^*,\lambda^*)=\displaystyle \inf_{x\in X}F(x,\lambda^*)\leq\sup_{\lambda\in\Lambda}F(x,\lambda)=\mathrm{Opt}(D)

Như vậy các bất đẳng thức trên thực sự là đẳng thức do \mathrm{Opt}(D)\leq \mathrm{Opt}(P) theo định lý trên, ta có

F(x^*,\lambda^*)= \mathrm{Opt}(P)=\mathrm{Opt}(D)

hay cả hai bài toán (P),(D) đều giải được và có giá trị tối ưu bằng nhau.

\Leftarrow “: Giả sử hai bài toán (P),(D) đều giải được và

\mathrm{Opt}(D)= \mathrm{Opt}(P)

đồng thời x^* là nghiệm của (P)\lambda^* là nghiệm của(D).

Ta có

\mathrm{Opt}(P)=\overline{F}(x^*)=\displaystyle \sup_{\lambda\in\Lambda}F(x^*,\lambda)\geq F(x^*,\lambda^*)

\mathrm{Opt}(D)=\underline{F}(\lambda^*)=\displaystyle \inf_{x\in X}F(x,\lambda^*)\leq F(x^*,\lambda^*)

Do \mathrm{Opt}(D)= \mathrm{Opt}(P) nên các bất đẳng thức trên đều là đẳng thức, tức là

F(x^*,\lambda^*)=\displaystyle\sup_{\lambda\in\Lambda}F(x^*,\lambda)\geq F(x^*,\lambda),\forall \lambda\in\Lambda.

F(x^*,\lambda^*)=\displaystyle\inf_{x\in X}F(x,\lambda^*)\leq F(x,\lambda^*),\forall x\in X.

tức là (x^*,\lambda^*) là điểm yên ngựa của F(x,\lambda).

Áp dụng định lý này vào bài toán quy hoạch ta có định lý sau:

Định lý (điều kiện của nghiệm tối ưu trong bài toán quy hoạch): Cho bài toán quy hoạch (P)

  1. (Điều kiện đủ) Nếu (x^*,\lambda^*), x^*\in X,\lambda^*\geq 0 là điểm yên ngựa của hàm L(x,\lambda) trên tập X\times \{\lambda\geq 0\} thì x^* là nghiệm tối ưu của bài toán quy hoạch.
  2. (Điều kiện cần và đủ cho bài toán quy hoạch lồi) Bài toán quy hoạch lồi (P) thỏa mãn điều kiện Slater có nghiệm tối ưu x^* nếu và chỉ nếu tồn tại \lambda^*\geq 0 sao cho (x^*,\lambda^*) là điểm yên ngựa của hàm L(x,\lambda) trên tập X\times \{\lambda\geq 0\}.
  3. Trong cả hai trường hợp, ta đều có
    \lambda_i^*g_i(x^*)=0,\forall i

Chứng minh (1):(x^*,\lambda^*) là điểm yên ngựa của hàm L(x,\lambda) trên tập X\times \{\lambda\geq 0\} nên theo định lý trên, x^*,\lambda^* là nghiệm tối ưu của hai bài toán (P), (D):

L(x^*,\lambda^*)=\displaystyle \inf_{x\in X}\sup_{\lambda\geq 0} L(x,\lambda)=\sup_{\lambda\geq 0}\inf_{x\in X}L(x,\lambda)

Ta sẽ chứng minh x^*\in S_Pf(x^*)=L(x^*,\lambda^*). Thật vậy vì

\displaystyle L(x^*,\lambda^*)= \sup_{\lambda\geq 0}L(x^*,\lambda)=\sup_{\lambda\geq 0}\left[f(x^*)+\sum_{i=1}^m\lambda_i g_i(x^*)\right]

nên nếu\exists i:g_i(x^*)>0, ta cho \lambda_i\rightarrow\infty thì L(x^*,\lambda) không bị chặn (tức là (x^*,\lambda^*) không phải điểm yên ngựa), vì thế g_i(x^*)\leq 0,\forall i, tức là x^*\in S_P.

Do g_i(x^*)\leq 0\lambda_i^*\geq 0 nên để L(x^*,\lambda^*)\geq L(x^*,\lambda),\forall\lambda\geq 0 ta phải có

\lambda_i^*g_i(x^*)=0, \forall i

vì vậy f(x^*)=L(x^*,\lambda^*).

Chứng minh (2):

\Leftarrow “: hiển nhiên theo (1).

\Rightarrow“: Nếu x^* là nghiệm của bài toán quy hoạch lồi (P) thỏa mãn điều kiện Slater, theo định lý về bài toán đối ngẫu Lagrange, tồn tại \lambda^*\geq 0 là nghiệm tối ưu của (D)

f(x^*)=\mathrm{Opt}(P)=\mathrm{Opt}(D)= \underline{L}(\lambda^*),

Theo định lý trên (x^*,\lambda^*) phải là điểm yên ngựa của hàm L(x,\lambda) trên tập X\times\{\lambda\geq 0\}. Ngoài ra, ta có

\displaystyle \underline{L}(\lambda^*)=\inf_{x\in X}\left[f(x)+\sum_{i=1}^m\lambda_i^* g_i(x) \right]\leq f(x^*)+\sum_{i=1}^m\lambda_i^* g_i(x^*)\leq f(x^*)

x^* thỏa mãn các ràng buộc. Đẳng thức chỉ xảy ra nếu

\lambda_i^*g_i(x^*)=0, \forall i.

Nhận xét:

  1. Ta thấy được điều kiện để x^*,\lambda^* là nghiệm tối ưu của hai bài toán (P),(D) thì độ vênh ở ràng buộc phải bù nhau:
    \lambda_i^*g_i(x^*)=0,\forall i

    giống như ở trường hợp quy hoạch tuyến tính.

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: