Hàm Lồi (4) – Điều Kiện Của Cực Tiểu

Trang chủ » Hàm Lồi Chặt » Hàm Lồi (4) – Điều Kiện Của Cực Tiểu

Có thể bạn quan tâm

Định lý (xấp xỉ Taylor là cận dưới của hàm lồi): Xấp xỉ Taylor bậc 1 tại x\in\mathrm{Dom}f mà f có đạo hàm không lớn hơn giá trị thực của hàm lồi. Tức là với mọi y\in\mathrm{Dom}f, ta có

f(x)+(y-x)^Tf'(x)\leq f(y)

Chứng minh: Xét z bất kì nằm giữa x,y, tức là z=x+\lambda(y-x) với 0<\lambda<1. Vì f lồi nên

\displaystyle\frac{f(z)-f(x)}{||z-x||}\leq\frac{f(y)-f(x)}{||y-x||}

Ta có

\displaystyle\frac{f(z)-f(x)}{||z-x||}=\frac{f(x+\lambda(y-x))-f(x)}{||x+\lambda(y-x)-x||} =\frac{f(x+\lambda(y-x))-f(x)}{\lambda||y-x||}

Cho \lambda\rightarrow 0^+, ta có \displaystyle\frac{f(x+\lambda(y-x))-f(x)}{\lambda}\rightarrow(y-x)^Tf'(x) (Đạo hàm theo \lambda và dùng luật L’Hopital). Tức là

\displaystyle\frac{(y-x)^Tf'(x)}{||y-x||}\leq\frac{f(y)-f(x)}{||y-x||}.

Định lí (tính cục bộ và toàn cục của cực tiểu): Cực tiểu cục bộ của hàm lồi cũng là cực đại toàn cục

Tức là nếu x^*\in\mathrm{Dom}f và \exists r>0:f(x)\geq f(x^*)\forall x\in\mathrm{Ball}(x^*,r) thì f(x)\geq f(x^*)\forall x\in\mathrm{Dom}f.

Chứng minh: Xét x\in\mathrm{Dom}f, vì f lồi, ta có

\displaystyle\frac{f(x)-f(x^*)}{||x-x^*||}\geq\frac{f(z)-f(x^*)}{||z-x^*||}

với mọi z nằm trong đoạn thẳng (x^*,x). Chọn z\in\mathrm{Ball}(x^*,r), ta có vế phải của bất đẳng thức trên không âm, suy ra f(x)\geq f(x^*).

Định lý (tính lồi của tập các cực tiểu): Tập các cực tiểu của hàm lồi là tập lồi.

Chứng minh: Định lý là hệ quả của bổ đề dưới đây.

Bổ đề (tính lồi của tập có giá trị hàm bị chặn trên): Nếu hàm f lồi thì tập X_\alpha=\{x:f(x)\leq\alpha\} lồi.

Nhận xét:

  1. Tập X_\alpha là tập con của miền xác định \mathrm{Dom}f sao cho giá trị của hàm f trên X_\alpha không lớn hơn \alpha.
  2. Rõ ràng, tập tất cả các cực tiểu của hàm f là tập X_{\displaystyle\min_x f(x)}.
  3. Nếu \displaystyle\alpha<\min_x f(x) thì X_\alpha=\emptyset vẫn là tập lồi (theo định nghĩa).

Chứng minh: Nếu x, y\in X_\alpha, ta có

f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)\leq\lambda\alpha+(1-\lambda)\alpha=\alpha.

Tức là \lambda x+(1-\lambda)y\in X_\alpha.

Định nghĩa (Hàm lồi chặt): Hàm f gọi là hàm lồi chặt nếu

  • \mathrm{Dom}f lồi.
  • f(\lambda x+(1-\lambda)y)<\lambda f(x)+(1-\lambda)f(y) với mọi x,y\in\mathrm{Dom}f.

Định lý (điều kiện lồi chặt): Điều kiện đủ để f lồi chặt là ma trận Hessian xác định dương.

Chứng minh: Tương tự như chứng minh f lồi khi ma trân Hessian xác định không âm.

Định lý (tính duy nhất của cực tiểu): Nếu hàm f lồi chặt thì cực tiểu (nếu tồn tại) là duy nhất.

Chứng minh: Giả sử x_1\neq x_2 đều là cực tiểu của f. Ta có

f(\displaystyle\frac{1}{2}x_1 + \frac{1}{2}x_2) < \frac{1}{2}(f(x_1) +f(x_2))=\min_x f(x).

Mâu thuẫn vì f không thể nhận giá trị nhỏ hơn giá trị nhỏ nhất của nó.

Định lý (điều kiện cần và đủ của cực tiểu): Nếu f lồi trên tập lồi Q và có đạo hàm tại x^*\in Q, điều kiện cần và đủ để f đạt cực tiểu tại x^* là

(x-x^*)^T f'(x^*)\geq 0, \forall x\in Q.

Chứng minh:

“\Rightarrow“: Nếu x^* là cực tiểu của hàm f trên tập lồi Q, với mọi x\in Q, ta có

\displaystyle\frac{f(x^*+\lambda(x-x^*))-f(x^*)}{\lambda}\geq 0

với mọi 0<\lambda\leq 1. Cho \lambda\rightarrow 0^+, ta có

(x-x^*)^T f'(x^*)\geq 0

“\Leftarrow“: Theo định lý về xấp xỉ Taylor bậc 1 của hàm lồi f, ta có

f(x)\geq f(x^*)+(x-x^*)^Tf'(x^*)\geq f(x^*), \forall x\in Q.

Nhận xét:

  1. “\Rightarrow” không phụ thuộc vào tính lồi của hàm f. Tức là điều kiện này luôn là điều kiện cần để x^* là cực tiểu.
  2. Điều kiện trên có nghĩa là tập Q\subset\mathrm{R}^n nằm ở một nửa không gian ngăn cách bởi siêu phẳng qua x^* và có véc tơ pháp tuyến f'(x^*) nếuf'(x^*)\neq 0.
  3. Nếu f lồi và f(x^*)=0 thì x^* là cực tiểu.

Định nghĩa (Nón tâm): Xét tập lồi Q và điểm x^*\in Q, nón tâm của Q tại x^* là tập

T_Q(x^*)=\{h:\exists t>0: x^*+th\in Q\},

tức là T_Q(x^*) là tập tất cả các hướng h mà tia từ x^* theo hướng đó có một điểm thuộc Q.

Điều kiện tương đương của cực tiểu: Điều kiện cần và đủ để x^* là cực tiểu của hàm lồi f trên tập lồi Q có thể viết lại như sau

h^Tf'(x^*)\geq 0,\forall h\in T_Q(x^*)

Nếu đặt N_Q(x^*) là nón trực giao của T_Q(x^*), tức là

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

thì điều kiện trên tương đương với f'(x^*)\in N_Q(x^*).

Ví dụ:

  1. Nếu x^*\in \mathrm{int}Q (xem định nghĩa phần trong), thì T_Q(x^*)=\mathbb{R}^n, suy ra N_Q(x^*)=\{0\}. Nghĩa là điều kiện cần và đủ để f đạt cực tiểu tại một điểm x^*\in \mathrm{int}Q là đạo hàm tại đó bằng {0}.
  2. Nếu x^*\in \mathrm{rint}Q (xem định nghĩa phần trong tương đối), giả sử \mathrm{Aff}Q=x^*+L, trong đó L là không gian con của \mathrm{R}^n. Rõ ràng T_Q(x^*) = L. Xét h\in L, nếu g\in N_Q(x^*), suy ra h^Tg\geq 0, (-h)^Tg\geq 0

    tức là h^Tg=0. Suy ra N_Q(x^*)=L^\perp. Có thể giải thích như sau: Từ x^* đi theo hướng -f'(x^*) ta giảm được f(x). Nhưng do f'(x^*)\in L^\perp, không có hướng nào thuộc L ta giảm được f(x), tức là f đạt cực tiểu tại x^* trên tập Q.

    Nếu \mathrm{Aff}Q=\{x:Ax=b\}, ta có L=\{x:Ax=0\} và L^\perp=\{y:y=A^T\lambda\}.

    f'(x^*)\in L^\perp\Leftrightarrow \exists\lambda^* f'(x^*)+A^T\lambda^*=0. \Leftrightarrow f'(x^*)+\sum_{i=1}^n\lambda_i a_i=f'(x^*)+\sum_{i=1}^n\lambda_i \nabla(a_i^Tx-b_i)=0

    Điều kiện này chính là điều kiện tối ưu khi ta dùng phương pháp nhân tử Lagrange.

  3. Nếu x\in Q=\{x:Ax\leq b\}, tại điểm x^*\in Q, tập T_Q(x^*) là tập như thế nào? Định nghĩa:Ràng buộc a_i^Tx\leq b_i gọi là được kích hoạt tại x^* nếu a_i^Tx^*=b_i. Rõ ràng, nếu một ràng buộc không được kích hoạt tại x^* thì x^*+th vẫn thỏa mãn ràng buộc này với hướng h bất kì, miễn là t đủ nhỏ. Như vậy những ràng buộc có thể bị vi phạm là những ràng buộc được kích hoạt tại x^*. Nếu a_i^Tx^*=b_i, để a_i^T(x^*+th)\leq b_i, rõ ràng ta phải có a^T h\leq 0 do t>0. Vậy

    T_Q(x^*)=\{h:a_i^Th\leq 0, \forall i\in I_Q(x^*)\}

    với I_Q(x^*)=\{i: a_i^Tx^*=b_i\}. Còn N_Q(x^*) là tập như thế nào? Nếu g\in N_Q(x^*) thì g^Th\geq 0,\forall h\in T_Q(x^*). Tức là g^Th\geq 0 là hệ quả của hệ bất đẳng thức (-a_i)^Th\geq 0, \forall i\in I_Q(x^*). Theo định lý Farkas thuần nhất, điều kiện cần và đủ là

    \exists \lambda_i\geq 0, i\in I_Q(x^*): g=-\displaystyle\sum_{i\in I_Q(x^*)}\lambda_i a_i

    Vậy

    N_Q(x^*)=\{g=\displaystyle-\sum_{i\in I_Q(x^*)}\lambda_i a_i,\lambda_i\geq 0\}

    và

    f'(x^*)\in N_Q(x^*)\Leftrightarrow \exists \lambda_i\geq 0, i\in I_Q(x^*): f'(x^*)+\displaystyle\sum_{i\in I_Q(x^*)}\lambda_i a_i=0.

    Có thể viết lại điều kiện này như sau

    \exists\lambda\geq 0: \begin{cases} f'(x^*)+\displaystyle\sum_{i=1}^m\lambda_i a_i=0\\\lambda_i(a_i^Tx^*-b_i)=0, i=1,\ldots,m\end{cases}

    Trong đó điều kiện thứ hai chính là tính chất bù nhau ở độ vênh của các ràng buộc mà ta đã gặp ở Bài toán đối ngẫu. Các điều kiện này còn gọi là điều kiện cần Karush-Kuhn-Tucker (KKT necessary conditions) cho bài toán tối ưu hóa có ràng buộc (Lưu ý: đối với hàm lồi thì đây cũng chính là điều kiện đủ).

Ví dụ: Tìm cực tiểu của hàm c^Tx+\displaystyle\sum_{i=1}^n x_i\ln x_i, với ràng buộc x\in Q=\{x_i\geq 0, \displaystyle\sum_{i=1}^n x_i=1\}.

Giả sử điểm cực tiểu x^*\in\mathrm{rint}Q, theo ví dụ 2 ở trên, điều kiện cần và đủ để f đạt cực tiểu tại x^* là

\exists\lambda: f'(x^*)+\displaystyle\lambda\nabla(\sum_{i=1}^n x_i-1)=0

\displaystyle\Leftrightarrow c_i+\ln x_i+1+\lambda=0\Leftrightarrow x_i=e^{-1-\lambda}e^{-c_i}

Do \displaystyle\sum_{i=1}^n x_i=1, ta giải được x_i=\displaystyle\frac{e^{-c_i}}{\displaystyle\sum_{i=1}^n e^{-c_i}}.

Điểm x^* này thỏa mãn điều kiện cần và đủ nên nó là cực tiểu của hàm f trên Q. Để thấy được x^* cũng là cực tiểu duy nhất, có thể tính ma trận Hessian và chứng minh tính xác định dương. Một cách khác là sử dụng định lý về tính lồi của tập các cực tiểu. Điểm x^* là cực tiểu duy nhất trong \mathrm{rint}Q, nếu có một điểm x'\in \partial Q cũng là cực tiểu của f, rõ ràng các điểm trên đoạn thẳng \left[x^*, x'\right.) cũng là cực tiểu, mâu thuẫn vì đoạn thẳng này chứa các điểm thuộc \mathrm{rint}Q (tính trù mật của phần trong tương đối).

Chia sẻ:

  • Facebook
  • X
Thích Đang tải...

Có liên quan

Từ khóa » Hàm Lồi Chặt