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

Learn & Enjoy …

Quy hoạch lồi (6) – Một số ví dụ về phương pháp nhân tử Lagrange

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

Khi bài toán quy hoạch lồi thỏa mãn điều kiện Slater, điều kiện cần và đủ của cực tiểu \displaystyle x^* chính là điều kiện Karush-Kuhn-Tucker, tức là tồn tại \displaystyle \lambda^*\geq 0 sao cho

\displaystyle \begin{cases}\displaystyle \nabla f(x^*)+\displaystyle \sum_{i=1}^m\lambda_i\nabla g_i(x^*)\in N_X(x^*)\\\displaystyle \lambda_i^* g_i(x^*)=0,\forall i\end{cases}

trong đó \displaystyle N_X(x^*) là nón trực giao của nón tâm \displaystyle T_X(x^*) được định nghĩa (xem ở bài tính chất cực tiểu của hàm lồi) như sau:

T_X(x^*)=\{h:\exists t>0: x^*+th\in X\}

N_X(x^*)=\{g:h^Tg\geq 0,\forall h\in T_X(x^*)\}

Trong trường hợp \displaystyle x^*\in \mathrm{int}X (thường xảy ra khi \displaystyle X=\mathbb{R}^n), ta có \displaystyle N_X(x^*)=\{0\}, như vậy điều kiện KKT là một hệ phương trình (thuần nhất) gồm \displaystyle n+m phương trình của \displaystyle n biến \displaystyle x_i ban đầu và \displaystyle m biến \displaystyle \lambda_i tương ứng với \displaystyle m ràng buộc của bài toán. Giải hệ phương trình này để tìm ra nghiệm tối ưu \displaystyle x^* và các nhân tử Lagrange \displaystyle \lambda^* tương ứng gọi là phương pháp nhân tử Lagrange.

Ví dụ 1: Giải bài toán quy hoạch

\displaystyle\min \{ x+y : x^2+y^2 \leq 1 \}

Giải: Đây là bài toán quy hoạch lồi vì hàm mục tiêu lồi và ràng buộc \displaystyle x^2+y^2 là hàm lồi. Đồng thời, bài toán thỏa mãn điều kiện Slater (vì tại \displaystyle (x,y)=(0,0) ta có \displaystyle x^2+y^2=0<1). Hàm Lagrange của bài toán là

\displaystyle L(x,y,\lambda)=x+y+\lambda(x^2+y^2-1)

Theo điều kiện Karush-Kuhn-Tucker (KKT) ta có tồn tại \displaystyle \lambda\geq 0 sao cho

\displaystyle \begin{cases}\displaystyle \frac{\partial L(x,y,\lambda)}{\partial x} = 1 + 2\lambda x = 0\\ \displaystyle \frac{\partial L(x,y,\lambda)}{\partial y} = 1 + 2\lambda y = 0\\ \displaystyle \lambda (x^2+y^2-1) = 0\end{cases}

Vậy ta phải có \displaystyle \lambda> 0

\displaystyle \begin{cases}\displaystyle x=y=-\frac{1}{2\lambda}\\ \displaystyle x^2+y^2=\frac{1}{2\lambda^2}=1\end{cases} \Rightarrow \begin{cases}\displaystyle \lambda = \frac{1}{\sqrt{2}}\\ \displaystyle x=y=-\frac{1}{\sqrt{2}}\end{cases}

Ví dụ 2: Khoảng cách từ một điểm \displaystyle z đến hình tròn đơn vị \displaystyle \{u:\|u\|\leq 1\} có thể xem như giá trị tối ưu của bài toán tối ưu

\displaystyle \min_u\{\|z-u\|:\|u\|\leq 1\}

Giải: Có thể thay bài toán trên bằng bài toán tương đương

\displaystyle \min_u\{(z-u)^T(z-u):u^Tu\leq 1\}

Đây là bài toán quy hoạch lồi thỏa mãn điều kiện Slater, hàm Lagrange là

\displaystyle L(u,\lambda)=z^Tz-2z^Tu+u^Tu+\lambda(u^Tu-1)

Điều kiện KKT là tồn tại \displaystyle \lambda \geq 0

\displaystyle \begin{cases}\displaystyle \nabla_u L(u,\lambda)=0\\ \lambda(u^Tu-1)=0\end{cases} \Rightarrow \begin{cases}2z+2u+2\lambda u=0\\ \lambda(u^Tu-1)=0\end{cases}

Có hai trường hợp

+ \displaystyle \lambda>0:

\displaystyle \begin{cases}\displaystyle u=\frac{z}{1+\lambda}\\ \displaystyle u^Tu=\frac{1}{(1+\lambda)^2}z^Tz=1 \end{cases}

\displaystyle \begin{cases}\|z\|>1\\ \lambda = \|z\|-1\\ \displaystyle u=\frac{z}{\|z\|}\end{cases} \Rightarrow \|z-u\|=\|z\|-1

+ \displaystyle \lambda=0

\displaystyle \begin{cases}\|z\|\leq 1\\ u = z\end{cases}\Rightarrow \|z-u\|=0

Như vậy khoảng cách từ \displaystyle z đến hình tròn đơn vị bằng \displaystyle 0 nếu \displaystyle z nằm trong hình tròn còn bằng \displaystyle \|z\|-1 nếu \displaystyle z nằm ngoài hình tròn.

Ví dụ 3: Tìm cực tiểu sau

\displaystyle \min \left\{\sum_{i=1}^n \frac{1}{x_i^2}:\sum_{i=1}^n x_i \leq 1, x_i>0\right\}

Giải: Đây là bài toán quy hoạch lồi vì \displaystyle x^{-2} là hàm lồi khi \displaystyle x>0. Đồng thời bài toán thỏa mãn điều kiện Slater. Hàm Lagrange là

\displaystyle L(x,\lambda)=\sum_{i=1}^n \frac{1}{x_i^2}+\lambda\left(\sum_{i=1}^n x_i - 1\right)

Điều kiện KKT là tồn tại \displaystyle \lambda \geq 0 sao cho

\displaystyle \begin{cases}\displaystyle \nabla_x L(x,\lambda) = 0\\ \displaystyle \lambda\left(\sum_{i=1}^n x_i - 1\right)=0\end{cases}\Rightarrow \begin{cases}-2x_i^{-3}+\lambda = 0,\forall i=1,\ldots,n\\ \displaystyle \lambda\left(\sum_{i=1}^n x_i - 1\right)=0\end{cases}

Vậy \displaystyle \lambda>0

\displaystyle \begin{cases}\displaystyle x_i=\left(\frac{\lambda}{2}\right)^3\\ \displaystyle \sum_{i=1}^n x_i = n \frac{\lambda^3}{8} = 1\end{cases}\Rightarrow \begin{cases}\displaystyle \lambda = \frac{2}{n^{-3}}\\\displaystyle x_i = \frac{1}{n}\end{cases}

Ở bài toán này, ta có thể thay hàm mục tiêu \displaystyle \sum_{i=1}^n \frac{1}{x_i^2}   bằng \displaystyle \sum_{i=1}^n \frac{a_i}{x_i^b},a_i>0,b>0, và ràng buộc \displaystyle \sum_{i=1}^n x_i\leq 1 bằng ràng buộc \displaystyle \sum_{i=1}^n x_i^c\leq 1,c\geq 1. Cách giải vẫn tương tự như trên.

Ví dụ 4: Chiếu 1 điểm lên đơn hình chuẩn (standard simplex):

Xét đa diện lồi sau \displaystyle P = \{x\in \mathbb{R}^n: x_i\geq 0, \sum_{i=1}^n x_i = 1\}. Đa diện lồi này còn được gọi là đơn hình chuẩn. Với một điểm \displaystyle c\in \mathbb{R}^n bất kì, ta muốn tìm một điểm \displaystyle x\in P gần \displaystyle c nhất. Phát biểu bài toán như sau:

\displaystyle \min_{x}\{\frac{1}{2}\|x-c\|^2: x_i\geq 0, \sum_{i=1}^n x_i = 1\}

Hàm Lagrange: Với \displaystyle \mu\geq 0, \lambda

\displaystyle L(x,\mu,\lambda) = \frac{1}{2}\|x-c\|^2 -\sum_{i=1}^n\mu_i x_i+\lambda\left(\sum_{i=1}^n x_i-1\right)

\displaystyle \frac{\partial L}{\partial x_i} = (x_i-c_i)-\mu+\lambda

Vậy điều kiện KKT là

\displaystyle \forall i, \begin{cases}x_i = c_i+\mu_i - \lambda \\ \mu_i x_i = 0 \\ \lambda\left(\sum_{i=1}^n x_i-1\right) = 0\\ \mu_i\geq 0\end{cases}

Nếu \displaystyle \mu_i = 0 ta có \displaystyle x_i = c_i - \lambda\geq 0.

Nếu \displaystyle \mu_i > 0 ta có \displaystyle x_i = 0\displaystyle c_i-\lambda < 0

Kết hợp lại, ta có \displaystyle x_i = \max(c_i-\lambda, 0) = (c_i-\lambda)_+\displaystyle \sum_{i=1}^n x_i = \sum_{i=1}^n (c_i-\lambda)_+ = f(\lambda) = 1

Dễ thấy \displaystyle f(\lambda) là hàm giảm dần theo \displaystyle \lambda, do đó, phương trình \displaystyle f(\lambda) = 1 chỉ có duy nhất 1 nghiệm. Để tìm \displaystyle \lambda, ta sắp xếp \displaystyle c_i tăng dần. Giá trị \displaystyle \lambda cần tìm phải nằm giữa \displaystyle [c_i, c_{i+1}] với \displaystyle 0\leq i\leq n-1 (ở đây chọn \displaystyle c_0=-\infty). Do đó

\displaystyle \sum_{j>i}(c_j-\lambda) = 1\Rightarrow \lambda = \frac{1}{n-i}\left(\sum_{j>i}c_j-1\right)

Ta chỉ cần chọn giá trị \displaystyle i đầu tiên để \displaystyle  c_i\leq \lambda \leq c_{i+1}.

Vậy ta có thuật toán:

  1. Sắp xếp \displaystyle c_i theo giá trị tăng dần (\displaystyle O(n\log n)).
  2. Tính các tổng con \displaystyle \sum_{j>i}c_j với mọi \displaystyle i và tính giá trị \displaystyle \lambda tương ứng (\displaystyle O(n) ).
  3. Chọn \displaystyle i để \displaystyle c_i\leq\lambda \leq c_{i+1}.
  4. Tính các \displaystyle x_i theo công thức \displaystyle x_i=(c_i-\lambda)_+ (\displaystyle O(n)).

Như vậy, ta cần \displaystyle O(n\log n) thao tác để chiếu một điểm lên đơn hình chuẩn.

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: