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

Learn & Enjoy …

Quy hoạch lồi (2) – Định lý đảo

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

Như ta đã biết, khi phân tích các ràng buộc tuyến tính, ta có định lý đảo tổng quát, tương tự như vậy, để phân tích các ràng buộc lồi, ta cũng có định lý đảo sau:

Định lý (kiểm tra tính có nghiệm của hệ bất đẳng thức lồi): Xét 2 hệ bất đẳng thức

(I)~~\begin{cases}f(x)<c\\g_i(x)\leq 0,i=1,\ldots,m\\x\in X\end{cases}

(II)~~\begin{cases}\displaystyle \inf_{x\in X}\left[f(x)+\sum_{i=1}^m\lambda_i g_i(x)\right]\geq c\\\lambda_i\geq 0, i=1,\ldots,m\end{cases}

ta có

  1. Nếu (II) có nghiệm (tức là tồn tại \lambda\geq 0 thỏa mãn hệ) thì (I) vô nghiệm.
  2. Nếu (I) vô nghiệm và
    X là tập lồi.
    f(x),g_i(x),i=1,\ldots,m là hàm lồi trên X.
    – Hệ ràng buộc g_i(x)\leq 0, x\in X, i=1,\ldots,m thỏa mãn điều kiện Slater.
    thì (II) có nghiệm.

Chứng minh (1): Nếu tồn tại \lambda^*\geq 0 thỏa mãn (II) ta có

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

Giả sử (I) có nghiệm x^*, suy ra

\displaystyle f(x^*)\geq f(x^*)+\sum_{i=1}^m\lambda_i^* g_i(x^*) do \lambda_i^*\geq 0, g_i(x^*)\leq 0, i=1,\ldots,m

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

mâu thuẫn vì x^* là nghiệm của (I) nên f(x^*)<c.

Chứng minh (2): Giả sử (I) vô nghiệm, xét tập S\subset\mathbb{R}^{n+1}

S=\{u\in\mathbb{R}^{n+1}:u_0<c,u_1\leq 0,\ldots,u_m\leq 0\}

và tập T\subset\mathbb{R}^{n+1}

T=\{u\in\mathbb{R}^{n+1}:\exists x\in X:f(x)\leq u_0,g_1(x)\leq u_1,\ldots,g_m(x)\leq u_m\}.

Ta thấy, S,T đều là hai tập khác rỗng, và hơn nữa còn là hai tập lồi. Thật vậy, hiển nhiên S là tập lồi còn nếu u,v\in T, ta có

\exists x,y\in X sao cho f(x)\leq u_0, g_i(x)\leq u_i, f(y)\leq v_0,g_i(y)\leq v_i

f,g_i(x) đều là các hàm lồi trên tập X lồi nên

f(\lambda x+(1-\lambda)y)\leq \lambda f(x)+(1-\lambda)f(y)\leq\lambda u_0+(1-\lambda)v_0

Tương tự như thế với các hàm g_i(x), suy ra \lambda u+(1-\lambda)v\in T. Tức là T lồi.

Nhận xét thấy rằng S\cap T=\emptyset vì nếu có u\in S\cap T thì tồn tại x\in X thỏa mãn các điều kiện của T với u_0<c,u_i\leq 0,i=1,\ldots,m, tức là x là nghiệm của (I). Như vậy, theo định lý phân cách hai tập lồi bằng siêu phẳng, ta có tồn tại a\neq 0 sao cho

\displaystyle \inf_{u\in T}a^Tu\geq\sup_{v\in S}a^Tv

Tức là

\displaystyle \inf_{u\in T}a^Tu=\inf_{x\in X}\inf_{\begin{array}{c}u_0\geq f(x)\\u_i\geq g_i(x)\end{array}}(a_0u_0+a_1u_1+\ldots+a_mu_m)

\displaystyle\geq \sup_{v\in S}a^Tv= \sup_{\begin{array}{c}v_0<c\\v_i\leq 0\end{array}}(a_0v_0+a_1v_1+\ldots+a_mv_m).

Ta thấy nếu a_i<0 thì khi v_i\rightarrow  -\infty ta có a^Tv\rightarrow \infty và không bị chặn trên. Vậy a\geq 0. Khi đó

\displaystyle \inf_{\begin{array}{c}u_0\geq f(x)\\u_i\geq g_i(x)\end{array}}(a_0u_0+a_1u_1+\ldots+a_mu_m)=a_0f(x)+a_1g_1(x)+\ldots+a_mg_m(x)

\displaystyle \sup_{\begin{array}{c}v_0<c\\v_i\leq 0\end{array}}(a_0v_0+a_1v_1+\ldots+a_mv_m)=a_0c

Suy ra

\displaystyle \inf_{x\in X}(a_0f(x)+a_1g_1(x)+\ldots+a_mg_m(x))\geq a_0c

Hơn nữa, nhận xét rằng a_0>0 vì nếu a_0=0 ta có

\displaystyle \inf_{x\in X}(a_1g_1(x)+\ldots+a_mg_m(x))\geq 0

tức là không tồn tại x sao cho a_1g_1(x)+\ldots+a_mg_m(x)<0, mâu thuẫn vì hệ ràng buộc g_i(x)\leq 0,x\in X,i=1,\ldots,m thỏa mãn điều kiện Slater. Vậy a_0>0 ta có

\displaystyle \inf_{x\in X}(f(x)+b_1g_1(x)+\ldots+b_mg_m(x))\geq c với b_i=\displaystyle \frac{a_i}{a_0} ,i=1,\ldots,m.

Nói cách khác hệ (II) có nghiệm.

Nhận xét:

  1. Định lý chia làm 2 phần không đối xứng nhau, phần (1) không đòi hỏi tính lồi của ràng buộc, nhưng phần (2) ngoài việc cần ràng buộc lồi còn đòi hỏi hệ ràng buộc thỏa mãn điều kiện Slater.
  2. Sự bất cân xứng này cũng dẫn đến sự bất cân xứng trong điều kiện của nghiệm tối ư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: