Tháng Mười Một 2009
T2	T3	T4	T5	T6	T7	CN
« Tháng 7
	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
30

Archive for the ‘Giải tích lồi’ Category

Tối ưu không ràng buộc (5) – Tốc độ hội tụ của phương pháp đạo hàm (hàm lồi)

Đăng bởi tqlong on Tháng Tư 25, 2008

Ta biết, hàm lồi có các tính chất rất “đẹp” đối với các thuật toán tối ưu hóa. Đặc biệt, cực tiểu cục bộ của hàm lồi cũng là cực tiểu toàn cục. Tính chất này cho phép ước lượng các sai số như $\displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P)$ hay $\displaystyle \epsilon(t)=\|x_t-x^*\|$ , đồng thời còn đảm bảo các thuật toán tối ưu hoạt động khá hiệu quả trên hàm lồi như ta sẽ thấy dưới đây.

Định lý (tốc độ hội tụ của thuật toán ArD): Nếu $\displaystyle f\in C^{1,1}$ và $\displaystyle f$ là hàm lồi thì với thuật toán ArD (với tham số $\displaystyle 0.5\leq \epsilon<1,\nu>1$ ), ta có

Quỹ đạo $\displaystyle \{x_t\}_{t=1}^\infty$ hội tụ đến một cực tiểu toàn cục $\displaystyle \bar{x}\in X^*$ nào đó.
Tốc độ hội tụ của sai số $\displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P)$ là
$\displaystyle \epsilon(N)\leq \frac{\nu L_f \|x_0-\bar{x}\|^2}{4(1-\epsilon)N}$

trong đó $\displaystyle L_f$ là hệ số Lipschitz của $\displaystyle \nabla f(x)$ , $\displaystyle x_0$ là nghiệm ban đầu.

Chứng minh (1): Để cho tiện, đặt

$\displaystyle d_t = \|x_t-x^*\|^2$

với $\displaystyle x^*\in X^*$ bất kì (lưu ý là $\displaystyle x^*$ có thể khác $\displaystyle \bar{x}$ ). Ta có

$\displaystyle d_{t+1}=\|x_{t+1}-x^*\|^2=\|x_t-\gamma_t\nabla f(x_t)-x^*\|^2$ $\displaystyle =\|x_t-x^*\|^2-2\gamma_t(x_t-x^*)^T\nabla f(x_t)+\gamma_t^2\|\nabla f(x_t)\|^2$ $\displaystyle =d_t-2\gamma_t(x_t-x^*)^T\nabla f(x_t)+\gamma_t^2\|\nabla f(x_t)\|^2$

Vì $\displaystyle f$ là hàm lồi nên xấp xỉ Taylor bậc 1 là cận dưới của hàm, ta có

$\displaystyle f(x^*)\geq f(x_t)+(x^*-x_t)\nabla f(x_t)$

$\displaystyle (x_t-x^*)\nabla f(x_t)\geq f(x_t)-f(x^*)=\epsilon(t)$

Hơn nữa, do $\displaystyle \gamma_t$ là bước nhảy Armijo nên

$\displaystyle \epsilon\gamma_t\|\nabla f(x_t)\|^2\leq f(x_t)-f(x_{t+1})$

$\displaystyle \gamma_t^2\|\nabla f(x_t)\|^2\leq \frac{\gamma_t}{\epsilon}(\epsilon(t)-\epsilon(t+1))$

Vậy, ta có

$\displaystyle d_{t+1}\leq d_t - 2\gamma_t\epsilon(t) + \frac{\gamma_t}{\epsilon}(\epsilon(t)-\epsilon(t+1))$ $\displaystyle = d_t-\gamma_t[(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]$

Hơn nữa, ta lại có ước lượng của bước nhảy Armijo

$\displaystyle \gamma_t\geq \frac{2(1-\epsilon)}{\nu L_f}$

nên nếu $\displaystyle \epsilon\geq 0.5$ hay $\displaystyle 2-\epsilon^{-1}\geq 0$ thì

$\displaystyle d_{t+1}\leq d_t - \frac{2(1-\epsilon)}{\nu L_f} [(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]\leq d_t$

Tức là khoảng cách $\displaystyle \|x_t-x^*\|$ không tăng theo $\displaystyle t$ , nói cách khác quỹ đạo $\displaystyle \{x_t\}_{t=1}^\infty$ bị chặn. Theo định lý về tính hội tụ của các phương pháp sử dụng đạo hàm, các điểm giới hạn $\displaystyle \bar{x}$ của quỹ đạo $\displaystyle \{x_t\}_{t=1}^\infty$ thỏa mãn tính chất $\displaystyle \nabla f(x^*)=0$ . Nhưng do $\displaystyle f$ là hàm lồi nên $\displaystyle \bar{x}$ cũng là cực tiểu toàn cục của $\displaystyle f$ . Ngoài ra, do $\displaystyle \bar{x}$ là điểm giới hạn của quỹ đạo nên có 1 dãy con hội tụ về $\displaystyle \bar{x}$ , nhưng do khoảng cách $\displaystyle \|x_t-\bar{x}\|$ không tăng theo $\displaystyle t$ nên

$\displaystyle \lim_{t\rightarrow \infty} \|x_t-\bar{x}\|=0$

hay $\displaystyle \lim_{t\rightarrow \infty}x_t = \bar{x}\in X^*$ .

Chứng minh (2): Thay $\displaystyle \bar{x}=x^*$ , ta có

$\displaystyle \frac{2(1-\epsilon)}{\nu L_f} [(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]\leq d_t - d_{t+1}$

$\displaystyle d_0-d_N=\sum_{t=0}^{N-1} d_t-d_{t+1}\geq \frac{2(1-\epsilon)}{\nu L_f} \sum_{t=0}^{N-1}[(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]$

Vì $\displaystyle \epsilon(t)\geq \epsilon(N),\forall t\leq N$ (do thuật toán luôn làm giảm hàm mục tiêu) nên

$\displaystyle \|x_0-\bar{x}\|^2=d_0\geq d_0-d_N\geq \frac{2(1-\epsilon)N}{\nu L_f} 2\epsilon(N)$

$\displaystyle \epsilon(N)\leq \frac{\nu L_f\|x_0-\bar{x}\|^2}{4(1-\epsilon)N}$

Như vậy, hàm sai số $\displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P)$ hội tụ về $\displaystyle 0$ chậm hơn tuyến tính. Tuy nhiên, nếu hàm lồi $\displaystyle f$ có cận trên và cận dưới là một hàm bậc 2 thì ta có kết quả mạnh hơn, đó là tốc độ hội tụ của thuật toán ArD là tuyến tính.

Định nghĩa (hàm lồi mạnh): Hàm lồi $\displaystyle f$ gọi là hàm lồi mạnh (strongly convex) với tham số $\displaystyle (l_f,L_f)>0$ nếu $\displaystyle f$ khả vi liên tục và

$\displaystyle f(x)+d^T\nabla f(x)+\frac{l_f}{2}\|d\|^2\leq f(x+d)\leq f(x)+ d^T\nabla f(x)+\frac{L_f}{2}\|d\|^2$

Định lý (tính chất của hàm lồi mạnh): Nếu $\displaystyle f$ là hàm lồi mạnh với tham số $\displaystyle (l_f,L_f)$ thì

Tập $\displaystyle \{x:f(x)\leq a\}$ là tập compact với mọi $\displaystyle a\in \mathbb{R}$ .
Hàm $\displaystyle f$ là hàm lồi chặt và có cực tiểu toàn cục duy nhất.
Hàm $\displaystyle f$ là hàm thuộc lớp $\displaystyle C^{1,1}$ với tham số $\displaystyle L_f$ .

Bổ đề: Hàm $\displaystyle f$ là hàm lồi mạnh với tham số $\displaystyle (l_f,L_f)$ nếu và chỉ nếu

$\displaystyle l_f\leq \lambda \leq L_f$

với $\displaystyle \lambda$ là giá trị riêng (eigenvalue) bất kì của ma trận Hessian của $\displaystyle f$ tại $\displaystyle x$ .

Chứng minh:

“ $\displaystyle \Rightarrow$ “: Nếu $\displaystyle f$ là hàm lồi mạnh với tham số $\displaystyle (l_f,L_f)$ , đặt $\displaystyle \phi(t)=f(x+td)$ , ta có

$\displaystyle \phi(t)\leq \phi(0)+t\phi'(0)+\frac{L_f}{2}t^2\|d\|^2$

$\displaystyle \phi(0)\leq \phi(t)-t\phi'(t)+\frac{L_f}{2}t^2\|d\|^2$

Suy ra

$\displaystyle \frac{\phi'(t)-\phi'(0)}{t}\leq L_f\|d\|^2$

Cho $\displaystyle t\rightarrow 0$ ta được $\displaystyle \phi''(0)=d^T\nabla^2 f(x)d\leq L_f\|d\|^2,\forall x,d$ . Nếu chọn $\displaystyle d$ là vectơ riêng ứng với giá trị riêng $\displaystyle \lambda$ thì

$\displaystyle d^T\nabla^2 f(x)d=\lambda \|d\|^2\leq L_f\|d\|^2$

hay $\displaystyle \lambda\leq L_f$ . Tương tự, ta cũng có $\displaystyle \lambda\geq l_f$ .

“ $\displaystyle \Leftarrow$ “: Giả sử

$\displaystyle 0<l_f\leq \lambda \leq L_f$

trong đó $\displaystyle \lambda$ là giá trị riêng bất kì của $\displaystyle \nabla^2 f(x)$ với mọi $\displaystyle x$ .

Ta có khai triển Taylor bậc 2 của $\displaystyle f(x+d)$ tại $\displaystyle x$ là

$\displaystyle f(x+d)=f(x)+d^T\nabla f(x)+\frac{1}{2} d^T\nabla^2 f(\psi)d$

với $\displaystyle \psi\in [x,x+d]$ . Ta lại có

$\displaystyle \frac{l_f}{2}\|d\|^2\leq \frac{1}{2} d^T\nabla^2 f(\psi)d\leq \frac{L_f}{2}\|d\|^2$

Vậy ta có điều phải chứng minh.

Chứng minh (1): Ta sẽ chứng minh $\displaystyle f$ bị chặn dưới. Thật vậy, cố định $\displaystyle x$ , ta có

$\displaystyle f(x+d) \geq f(x)+d^T\nabla f(x)+\frac{l_f}{2}\|d\|^2$ $\displaystyle \geq f(x)-\|d\|\|\nabla f(x)\|+\frac{l_f}{2}\|d\|^2,\forall d$

Vế phải là hàm bậc hai của $\displaystyle \|d\|$ với hệ số ở lũy thừa 2 dương nên bị chặn dưới, do đó $\displaystyle f(x+d)$ bị chặn dưới với mọi $\displaystyle d$ . Đặt $\displaystyle c=\inf f(x)$ , và xét $\displaystyle x\in \{x:f(x)\leq a\}$ , ta có

$\displaystyle a-c\geq f(y)-f(x)\geq (y-x)^T\nabla f(x)+\frac{l_f}{2} \|y-x\|^2$ $\displaystyle \geq -\|y-x\|\|\nabla f(x)\|+\frac{l_f}{2} \|y-x\|^2,\forall y\in \{x:f(x)\leq a\}$

Vế phải là hàm bậc 2 với hệ số ở lũy thừa 2 dương nên chỉ bị chặn trên khi $\displaystyle \|y-x\|$ bị chặn trên. Vậy tập $\displaystyle \{x:f(x)\leq a\}$ bị chặn. Hơn nữa, do tính liên tục của $\displaystyle f(x)$ , tập $\displaystyle \{x:f(x)\leq a\}$ là tập đóng nên cũng là tập compact.

Chứng minh (2): Tập $\displaystyle \{x:f(x)\leq a\}$ là tập compact nên phải tồn tại cực tiểu của $\displaystyle f(x)$ trong tập này. Rõ ràng, đây cũng là cực tiểu toàn cục của $\displaystyle f(x)$ . Hơn nữa $\displaystyle f$ là hàm lồi chặt nên cực tiểu này là duy nhất (ma trận Hessian xác định dương do $\displaystyle l_f>0$ ).

Chứng minh (3): Ta có

$\displaystyle \|\nabla f(x+d)-\nabla f(x)\|=\|\nabla^2 f(\psi)d\|$

với $\displaystyle \psi\in [x,x+d]$ . Theo bổ đề trên, ta lại có

$\displaystyle \|\nabla^2 f(\psi)d\|^2=d^T(\nabla^2f(\psi))^2d\leq L_f^2\|d\|^2$

Vậy

$\displaystyle \|\nabla f(x+d)-\nabla f(x)\|\leq L_f \|d\|$

Tức là $\displaystyle L_f$ là hệ số Lipschitz của $\displaystyle \nabla f(x)$ , điều phải chứng minh.

Định lý (tốc độ hội tụ của thuật toán ArD khi hàm mục tiêu lồi mạnh): Nếu $\displaystyle f$ là hàm lồi mạnh với tham số $\displaystyle (l_f,L_f)$ thì với thuật toán ArD (với tham số $\displaystyle 0.5\leq \epsilon<1,\nu>1$ ), ta có

Quỹ đạo $\displaystyle \{x_t\}_{t=0}^\infty$ hội tụ về cực tiểu duy nhất $\displaystyle x^*$ .
Tốc độ hội tụ của hàm sai số $\displaystyle \epsilon_1(t)=\|x_t-x^*\|$ là
$\displaystyle \epsilon_1(N)\leq \theta^N \epsilon_1(0)$

với $\displaystyle \theta=\sqrt{\frac{Q_f-(2-\epsilon^{-1})(1-\epsilon)\nu^{-1}}{Q_f+(\epsilon^{-1}-1)\nu^{-1}} }$ và $\displaystyle Q_f=\frac{L_f}{l_f}$ gọi là tỉ số điều kiện (condition number) của hàm $\displaystyle f$ .
Tốc độ hội tụ của hàm sai số $\displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P)$ là
$\displaystyle \epsilon(N)\leq \theta^{2N}Q_f\epsilon(0)$

Chứng minh (1): Dễ thấy vì các tính chất trên của hàm lồi mạnh nên các điều kiện của các định lý về tính hội tụ của thuật toán ArD với hàm mục tiêu lồi được thỏa mãn.

Chứng minh (2): Theo định lý trên, ta có

$\displaystyle \frac{2(1-\epsilon)}{\nu L_f} [(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]\leq d_t - d_{t+1}$

Với điều kiện hàm lồi mạnh, ta có thể ước lượng $\displaystyle \epsilon(t)$ chính xác hơn

$\displaystyle \epsilon(t)=f(x_t)-f(x^*)\geq \frac{l_f}{2}\|x_t-x^*\|=\frac{l_f}{2}d_t$

do $\displaystyle \nabla f(x^*)=0$ , vậy

$\displaystyle d_t - d_{t+1}\geq \frac{(1-\epsilon)l_f}{\nu L_f} [(2-\epsilon^{-1})d_t+\epsilon^{-1}d_{t+1}]$

$\displaystyle d_{t+1}\leq \frac{Q_f-(2-\epsilon^{-1})(1-\epsilon)\nu^{-1}}{Q_f+(\epsilon^{-1}-1)\nu^{-1}} d_t$

$\displaystyle d_{t+1}\leq \theta^2 d_t$

$\displaystyle \epsilon_1(t+1)=\sqrt{d_{t+1}}\leq \theta \sqrt{d_t}=\theta \epsilon_1(t)$

$\displaystyle \epsilon_1(N) \leq \theta^N \epsilon_1(0)$

Chứng minh (3): Ta có

$\displaystyle \epsilon(N)=f(x_N)-f(x^*)\leq \frac{L_f}{2}d_N \leq \frac{L_f\theta^{2N}}{2}d_0$

Ta lại có

$\displaystyle d_0=\|x_0-x^*\|^2\leq \frac{2}{l_f}[f(x_0)-f(x^*)]=\frac{2}{l_f}\epsilon(0)$

suy ra

$\displaystyle \epsilon(N)\leq \frac{L_f\theta^{2N}}{l_f}\epsilon(0)=\theta^{2N}Q_f\epsilon(0)$

Nhận xét:

Trong trường hợp tổng quát, ta chỉ có thể đánh giá $\displaystyle \epsilon_\nabla(t)=\|\nabla f(x_t)\|^2$ do hàm mục tiêu có thể có nhiều cực tiểu cục bộ (và các điểm KKT khác).
Trong trường hợp hàm lồi thuộc lớp $\displaystyle C^{1,1}$ , ta có thể đánh giá được hàm $\displaystyle \epsilon_f(t)=f(x_t)-\mathrm{Opt}(P)$ vì các điểm KKT là cực tiểu toàn cục của hàm mục tiêu. Tuy nhiên ta không thể đánh giá hàm $\displaystyle \epsilon_x(t)=\|x_t-x^*\|$ vì có thể có rất nhiều cực tiểu toàn cục.
Trong trường hợp hàm lồi mạnh, chỉ có một cực tiểu duy nhất nên ta có điều kiện ước lượng $\displaystyle \epsilon_x(t)=\|x_t-x^*\|$ .
Tuy tốc độ hội tụ trong trường hợp hàm mục tiêu lồi mạnh là tuyến tính, tỉ lệ hội tụ $\displaystyle \theta$ phụ thuộc rất nhiều vào tỉ số điều kiện $\displaystyle Q_f=\frac{L_f}{l_f}$ . Khi $\displaystyle Q_f$ lớn thì $\displaystyle \theta$ gần bằng $\displaystyle 1$ tức là thuật toán hội tụ rất chậm. Trường hợp này ta nói hàm $\displaystyle f$ là hàm có điều kiện tồi (ill-conditioned).
Những hàm thay đổi mạnh trên một hướng nhưng thay đổi rất ít trên hướng khác là những hàm có điều kiện tồi.
Ví dụ: Thuật toán StD chạy trên hàm $\displaystyle f(x)=5x_1^2+0.2x_2^2$ , tỉ số điều kiện $\displaystyle Q_f=\frac{5}{0.2}=25$
Như vậy, phương pháp tối ưu theo hướng đạo hàm phụ thuộc vào hệ tọa độ quy chiếu, trong ví dụ trên nếu ta đổi biến
$\displaystyle y_1=\sqrt{5}x_1, y_2=\sqrt{0.2}x_2$

thì $\displaystyle f(y)=y_1^2+y_2^2$ , tỉ số điều kiện lúc này là $\displaystyle Q_f=1$ và thuật toán hội tụ rất nhanh.

Đăng trong Giải tích lồi, Quy hoạch lồi, Quy hoạch phi tuyến | Tagged: armijo, hàm lồi, tốc độ hội tụ | Leave a Comment »

Tập lồi (7) – Cấu trúc của đa diện lồi

Đăng bởi tqlong on Tháng Hai 14, 2008

Định nghĩa (đa diện lồi): Tập $P=\{x\in \mathbb{R}^n :Ax\leq b\}$ gọi là đa diện lồi (polyhedra) trong $\mathbb{R}^n$ .

Nhận xét:

Đa diện lồi là tập đóng, lồi.
$\mathbb{R}^n$ cũng là đa diện lồi khi ta chọn $A=0, b\geq 0$ .
Các ràng buộc của bài toán quy hoạch tuyến tính tạo nên đa diện lồi.

Định lý (cấu trúc của đa diện lồi): Đa diện lồi $P=\{x\in \mathbb{R}^n :Ax\leq b\}$ luôn có thể biểu diễn dưới dạng

$P=P^*+L$

trong đó $P^*$ là tập đóng lồi không chứa đường thẳng, $L=\mathrm{Null}A$ là không gian con của $\mathbb{R}^n$ .

Lưu ý: Nhắc lại khái niệm trong đại số tuyến tính:

$\mathrm{Null}A=\{x:Ax=0\}$ (nhân của ma trận, còn kí hiệu là $\mathrm{Ker}A$ ).
$\mathrm{Im}A=\{y:y=Ax\}$ (không gian con tạo bởi các cột của $A$ ).
Tính chất: $\mathrm{Im}A^T=(\mathrm{Null}A)^\perp$ .

Chứng minh: Ta sẽ chứng minh theo thứ tự sau

Nếu $x\in P$ , đường thẳng $\{x(t):x+th, x\in P,t\in \mathbb{R},h\neq 0\}\subset P$ nếu và chỉ nếu $h\in\mathrm{Null}A$ .
Đặt $P^*=P\cap\mathrm{Im}A^T=\{x\in \mathrm{Im}A^T,Ax\leq b\}$ thì $P=P^*+\mathrm{Null}A$ và $P^*$ không chứa đường thẳng.

Chứng minh (1): Nếu $h\in\mathrm{Null}A$ , ta có $A^T(x+th)=A^Tx\leq b,\forall t\in\mathbb{R}$ .

Ngược lại, nếu $A(x+th)\leq b,\forall t$ , tức là $a_i^T(x+th)\leq b_i,\forall i,t$ ( $a_i$ là dòng thứ $i$ của $A$ ). Xét 2 trường hợp:

$a_i^Th>0$ , rõ ràng khi $t\rightarrow \infty$ ta sẽ có $a_i^T(x+th)>b_i$ .
$a_i^Th<0$ thì khi $t\rightarrow -\infty$ ta cũng có $a_i^T(x+th)>b_i$ .

Vậy chỉ còn khả năng $a_i^Th=0,\forall i$ , tức là $h\in\mathrm{Null}A$ .

Chứng minh (2): Rõ ràng $P^*\subset P$ nên $P^*+\mathrm{Null}A\subset P$ theo (1). Ngược lại, nếu $x\in P$ , chiếu $x$ xuống $\mathrm{Im}A^T$ , ta có

$x=y+z, y\in \mathrm{Im}A^T, z\in\mathrm{Null}A$

Ta thấy $y=x-z$ nên $y\in P$ theo (1), như vậy $y\in P\cap\mathrm{Im}A^T=P^*$ , suy ra $x\in P^*+\mathrm{Null}A$ . Tức là $P\subset P^*+\mathrm{Null}A$ . Kết luận $P=P^*+\mathrm{Null}A$ .

Để thấy $P^*$ không chứa đường thẳng, để ý rằng $P^*\subset P$ nên mọi đường thẳng trong $P^*$ cũng là đường thẳng trong $P$ , nghĩa là hướng của đường thẳng này nằm trong $\mathrm{Null} A$ , vô lý vì $P^*$ nằm trong không gian trực giao với $\mathrm{Null} A$ .

Nhận xét:

Ta thấy $P^*$ là đa diện lồi trong không gian con của $\mathbb{R}^n$ nên nó cũng là đa diện lồi trong $\mathbb{R}^n$ (ngoài điều kiện $Ax\leq b$ ta thêm vào các điều kiện $a_i^Tx\leq 0,-a_i^Tx\leq 0,\forall i$ ).
$P$ không chứa đường thằng nếu và chỉ nếu $\mathrm{Null}A=\{0\}$ .

Định lý (cấu trúc của đa diện lồi có điểm cực biên): Nếu $P=\{x\in \mathbb{R}^n :Ax\leq b\}$ là đa diện lồi không chứa đường thẳng thì $P$ có thể biểu diễn dưới dạng

$P=\mathrm{Conv}V+\mathrm{Cone}R$

trong đó $V=\mathrm{Ext}P$ hữu hạn, $R$ là tập hữu hạn các véctơ và $\mathrm{Cone}R=\{r:Ar\leq 0\}$ .

Chứng minh: Ta sẽ chứng minh theo thứ tự sau

Nếu $r\neq 0$ sao cho tồn tại $x\in P:x+tr\in P,\forall t>0$ thì $Ar\leq 0$ .
Hơn nữa, với $r$ như vậy, với mọi $y\in P, y+tr\in P,\forall t>0$ .
$P=\mathrm{ConvExt}P+\{r:Ar\leq 0\}$ .
Tập $V=\mathrm{Ext}P$ hữu hạn.
Tập $\{r:Ar\leq 0\}$ là tập tất cả các tổ hợp nón của một tập hữu hạn véctơ $R=\{r_1,\ldots,r_k\}$ .

Chứng minh (1): Ta có $A(x+tr)\leq b,\forall t>0$ , tức là $a_i^T(x+tr)\leq b_i,\forall i, t>0$ . Nếu $a_i^Tr>0$ thì khi $t\rightarrow \infty$ , ta sẽ có $a_i^T(x+tr)>b_i$ . Như vậy, ta phải có $a_i^Tr\leq 0,\forall i$ , tức là $Ar\leq 0$ .

Chứng minh (2): Vì $Ar\leq 0$ , với mọi $y\in P, t>0$ , ta có $A(y+tr)\leq Ay\leq b$ , tức là toàn bộ tia $\{y(t)=y+tr,t>0\} \subset P$ .

Chứng minh (3): Rõ ràng $\mathrm{ConvExt}P\subset P$ nên $\mathrm{ConvExt}P+\{r:Ar\leq 0\}\subset P$ theo (2). Ngược lại, nếu $x\in P$ , ta sẽ chứng minh $x\in\mathrm{ConvExt}P+\{r:Ar\leq 0\}$ bằng quy nạp theo $n=\dim P$ .

Cơ sở: với $n=0$ tức là $P=\{x\}$ định lý đúng.

Quy nạp: giả sử định lý đúng với $n<k$ , ta sẽ chứng minh định lý cũng đúng với $n=k$ . Thật vậy, chọn một véctơ $r\neq 0, r\in\{r:Ar\leq 0\}$ . Vì $P$ không chứa đường thẳng nên $Ar\neq 0$ (do $\mathrm{Null}A=\{0\}$ theo định lý trên). Đồng thời, tia $\{x(t)=x-tr, t>0\}$ phải thoát ra khỏi $A$ ở một điểm $x^*\in\partial P$ nào đó, nếu không $P$ sẽ chứa toàn bộ đường thẳng $\{x(t)=x+tr,t\in \mathrm{R}\}$ . Xét siêu phẳng $\Pi=\{x:f^Tx=a\}$ đỡ $P$ ở $x^*$ , đặt $Q=\Pi\cap P$ . Rõ ràng $Q$ cũng là đa diện lồi, không chứa đường thẳng, theo giả thiết quy nạp điểm $x^*$ phải thuộc vào tập $\mathrm{ConvExt}Q+\{r:Ar\leq 0,f^Tr=0\}$ (do ta thêm một điều kiện $f^Tx=a$ vào đa diện lồi). Rõ ràng

$\mathrm{ConvExt}Q\subset\mathrm{ConvExt}P$

$\{r:Ar\leq 0,f^Tr=0\}\subset\{r:Ar\leq 0\}$

tức là $x^*\in \mathrm{ConvExt}Q+\{r:Ar\leq 0,f^Tr=0\}\subset\mathrm{ConvExt}P+\{r:Ar\leq 0\}$ . Suy ra $x=x^*+tr \in\mathrm{ConvExt}P+\{r:Ar\leq 0\}$ .

Chứng minh (4): Kết luận (4) là hệ quả của bổ đề sau đây

Bổ đề (điều kiện cực biên của đa diện lồi): Nếu $x$ là điểm cực biên của $P$ , trong các ràng buộc được kích hoạt tại $x$ , phải có $n$ ràng buộc độc lập tuyến tính, tức là có

$a_{i_1}^Tx=b_{i_1},\ldots,a_{i_n}^Tx=b_{i_n}$ và $(a_{i_1},\ldots,a_{i_n})$ độc lập tuyến tính.

Chứng minh: Thật vậy, giả sử ngược lại, chỉ có $k<n$ ràng buộc độc lập tuyến tính. Như vậy, tồn tại véctơ $h\neq 0$ sao cho $h$ trực giao với tất cả $a_{i_j}$ của các ràng buộc được kích hoạt tại $x$ . Xét điểm $x(\epsilon)=x+\epsilon h, \epsilon\in \mathbb{R}$ . Rõ ràng, các ràng buộc được kích hoạt tại $x$ vẫn được kích hoạt tại $x(\epsilon)$ , ngoài ra, với $|\epsilon|>0$ đủ nhỏ, các ràng buộc không được kích hoạt tại $x$ vẫn được thỏa mãn tại $x(\epsilon)$ , như vậy $x+\epsilon h,x-\epsilon h\in P$ với $|\epsilon|>0$ đủ nhỏ, tức là $x$ không phải là điểm cực biên, mâu thuẫn.

Do số lượng các bộ $n$ ràng buộc trong $m$ ràng buộc ( $m$ là số dòng của ma trận A) là $\mathrm{C}_n^m$ hữu hạn nên số điểm cực biên, $|\mathrm{Ext}P|$ , cũng là hữu hạn.

Chứng minh (5): Để chứng minh kết luận (5) ta cũng dùng cách quy nạp như chứng minh (3), tuy nhiên, ta không chọn siêu phẳng đỡ bất kì mà chọn siêu phẳng $\Pi_i$ tạo bởi một điều kiện $a_i^Tx\leq b_i$ bị kích hoạt tại $x^*$ (tại $x^*\in\partial P$ phải có điều kiện được kích hoạt, nếu không nó phải nằm trong $\mathrm{rint}P$ ). Theo giả thiết quy nạp,

$x^* \in \mathrm{Conv}Ext(\Pi_i\cap P)+\mathrm{Cone}R_i$

với $R_i$ là tập hữu hạn. Như vậy

$x=x^*+th\in\mathrm{Conv}\mathrm{Ext}(\Pi_i\cap P)+\mathrm{Cone}(R_i\cup\{r\})$ .

Do số ràng buộc, $m$ , là hữu hạn nên nếu ta đặt $R=\displaystyle\cup_{i=1}^m R_i\cup\{r\}$ , thì

$x\in\mathrm{Conv}\mathrm{Ext}P+\mathrm{Cone}R$ .

Nhận xét:

Qua hai định lý trên, tổng hợp lại, ta luôn có khẳng định sau: Đa diện lồi $P=\{x:Ax\leq b\}$ luôn có thể viết dưới dạng
$P=\mathrm{Conv}V+\mathrm{Cone}R=\left\{\displaystyle \sum_{i=1}^I\lambda_i v_i+\sum_{j=1}^J\mu_j r_j\right\}$ (*)

trong đó $\lambda_i,\mu_j\geq 0, \displaystyle \sum_{i=1}^I\lambda_i=1$ và $I, J$ hữu hạn.
Có thể chứng minh mọi tập có dạng (*) đều là đa diện lồi.
Nếu coi biểu diễn $\{x:Ax\leq b\}$ là biểu diễn từ phía ngoài ( $A,b$ ràng buộc $P$ ) thì biểu diễn (*) là biểu diễn từ phía trong, nghĩa là trong $P$ có một số hữu hạn véctơ mà tất cả các véctơ khác có thể biểu diễn bằng các véctơ này.
Với tập đóng, lồi và bị chặn, ta đã biết $P=\mathrm{ConvExt}P$ .
Hai cách biểu diễn như vậy giúp hiểu rõ cấu trúc của đa diện lồi, đồng thời còn giúp trả lời các vấn đề mà nếu chỉ sử dụng biểu diễn ngoài rất khó giải thích (xem tiếp ở dưới).
Bổ đề về điều kiện cực biên của đa diện lồi là cơ sở của phương pháp đơn hình giải bài toán quy hoạch tuyến tính.

Định lý (các phép biến đổi đa diện lồi): Nếu $P$ là đa diện lồi thì

Ảnh của đa diện lồi qua ánh xạ affine ngược cũng là đa diện lồi.
Ảnh của đa diện lồi qua ánh xạ affine cũng là đa diện lồi.
Giao của hai đa diện lồi là đa diện lồi.
Tổng của hai đa diện lồi là đa diện lồi (hay tổng quát hơn tổ hợp tuyến tính các đa diện lồi cũng là đa diện lồi).

Chứng minh: (1) và (3) là hệ quả trực tiếp của biểu diễn ngoài, (2) và (4) là hệ quả trực tiếp của biểu diễn trong vì đây là các phép toán biến đổi tập lồi và nón lồi (Lưu ý, rất khó chứng minh (2) và (4) nếu chỉ sử dụng biểu diễn ngoài).

Định lý (hàm tuyến tính bị chặn đạt cực trị trong đa diện lồi): Nếu hàm tuyến tính bị chặn trên (chặn dưới) trong đa diện lồi $P$ thì nó đạt cực đại (cực tiểu) trong đa diện lồi đó.

Chứng minh: Nếu $f^Tx$ bị chặn trên trong đa diện lồi $P=\mathrm{Conv}V+\mathrm{Cone}R$ thì với mọi $r\in\mathrm{Cone}R$ ta phải có $f^Tr\leq 0$ . Thật vậy, nếu $f^Tr>0$ , rõ ràng với mọi $x\in P$ ta có $f^T(x+tr)$ không bị chặn khi $t\rightarrow \infty$ . Suy ra, với mọi $x\in P, x=\displaystyle \sum_{i=1}^I\lambda_i v_i+r, r\in\mathrm{Cone}R$ ta có

$\displaystyle f^T x=\sum_{i=1}^I\lambda_i f^Tv_i+f^Tr\leq\sum_{i=1}^I\lambda_i f^Tv_i\leq\max_{v_i\in V}f^Tv_i$

Tức là cực đại của $f^Tx$ trên $V$ cũng là cực đại của $f^Tx$ trên $P$ .

Nhận xét:

Định lý đảm bảo bài toán quy hoạch tuyến tính luôn có nghiệm nếu hàm mục tiêu bị chặn.
Khi $P$ không chứa đường thẳng, cực đại của hàm mục tiêu luôn có thể đạt được ở một trong các điểm cực biên.
Với bài toán quy hoạch tuyến tính ở dạng chuẩn tắc
$\displaystyle \mathrm{Opt}(P)=\max \{c^Tx: Ax=b,x\geq 0\}$

các ràng buộc tạo nên tập nghiệm luôn có điểm cực biên (không chứa đường thẳng) vì các biến đều có ràng buộc không âm.

Đăng trong Giải tích lồi, Quy hoạch tuyến tính | Tagged: bao lồi, bao nón, biến đổi, biểu diên, cấu trúc, cực tiểu, cực đại, chiếu, Quy hoạch tuyến tính, ràng buộc, siêu phẳng đỡ, tập lồi, tổ hợp nón, đa diện lồi, điểm cực biên, đơn hình, đường thẳng | Leave a Comment »

« Những bài viết trước

	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

Archive for the ‘Giải tích lồi’ Category

Tối ưu không ràng buộc (5) – Tốc độ hội tụ của phương pháp đạo hàm (hàm lồi)

Tập lồi (7) – Cấu trúc của đa diện lồi