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

Tháng Hai 2008
T2	T3	T4	T5	T6	T7	CN
		Tháng 3 »
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29

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

Đăng bởi tqlong 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$ và

$\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$ và

$\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$ và $\displaystyle c_i-\lambda < 0$

Kết hợp lại, ta có $\displaystyle x_i = \max(c_i-\lambda, 0) = (c_i-\lambda)_+$ và $\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:

Sắp xếp $\displaystyle c_i$ theo giá trị tăng dần ( $\displaystyle O(n\log n)$ ).
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)$ ).
Chọn $\displaystyle i$ để $\displaystyle c_i\leq\lambda \leq c_{i+1}$ .
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.

Bài viết này được đăng vào Tháng Hai 16, 2008 lúc 9:02 sáng và tập tin được lưu ở Quy hoạch lồi. Tagged: KKT, Lagrange, nhân tử Lagrange, Slater. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể Để lại lời nhắn, hoặc trackback từ trang của bạn.

Để lại hồi âm

« Quy hoạch lồi (5) – Điều kiện Karush-Kuhn-Tucker (KKT)

Phương pháp đơn hình (Simplex method) (1) – Bài toán QHTT, dạng chuẩn tắc và các định lý cơ bản »

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

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

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

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

Để lại hồi âm