Unconstrained Nonlinear Optimization – Thuật toán Line search

Cập nhật 10/10/2010: Download bản PDF dễ đọc hơn.

Cho một bài toán tối ưu phi tuyến không ràng buộc (Unconstrained Nonlinear Optimization Problem – UNOP)

\displaystyle \min_{x\in\mathcal{R}^n}f\left(x\right)

tư tưởng chung là ta sẽ phát sinh dãy  \left\{x^k\right\}_{k=0}^\infty sao cho nó hội tụ về lời giải tối ưu x^*. Theo đó, thuật toán tổng quát là:

Thuật toán 1: Thuật  toán tổng quát cho UNOP

1. Khởi tạo x^k\in\mathbf{X}=\mathcal{R}^n,\;k=0.

2. Nếu x^k thoả điều kiện dừng (stopping criterium) nào đó thì gán x^* = x^k và dừng.

3. Nếu x^k không thỏa điều kiện trên thì tịnh tiến  x^k đến một điểm mới tốt hơn (thỏa mãn hàm mục tiêu tốt hơn điểm hiện tại). Cụ thể ta sẽ:

3.1. Tìm hướng giảm (descent direction) \mathbf{d}^k.

3.2. Tìm độ dài bước  (steplength) \alpha^k.

3.3. Cập nhật \mathbf{x}^{k+1}:=\mathbf{x}^k+\alpha^k\mathbf{d}^k,\;k:=k+1. Quay lại bước 2.

Như vậy có 3 vấn đề cần làm rõ trong thuật toán này là:

  • Stopping criterium nào là phù hợp, nghĩa là phải nghĩ ra điều kiện để quyết định lúc nào thì nên dừng thuật toán,
  • Tìm descent direction như thế nào, và cuối cùng
  • Tìm steplength như thế nào.

Bước khởi tạo cũng rất quan trọng, vì nó có thể quyết định kết quả cuối cùng của thuật toán. Tuy nhiên thông thường không có cách nào để biết khởi tạo như thế nào là tốt, do đó người ta sẽ thực hiện thuật toán nhiều lần với các điểm khởi tạo khác nhau, và chọn kết quả tốt nhất.

Ba phần còn lại của bài sẽ tương ứng với 3 vấn đề đã nêu trên.

1. Stopping criterium

Có 3 điều kiện sau:

  • Điều kiện cần của đạo hàm bậc nhất:
    Nếu x^* là điểm tối ưu cục bộ và  f\left(x\right) khả vi liên tục trên một lân cận mở của x^* thì \nabla f\left(x^*\right)=0.
  • Điều kiện cần của đạo hàm bậc 2:
    Nếu x^* là điểm tối ưu cục bộ, f\left(x\right)\nabla^2 f\left(x\right) khả vi liên tục trên một lân cận mở của x^* thì \nabla f\left(x^*\right)=0 và ma trận Hessian \nabla^2 f\left(x^*\right) là ma trận positive semidefinite.
  • Điều kiện đủ của đạo hàm bậc 2:
    Giả sử \nabla^2 f\left(x\right) liên tục trên một lân cận mở của x^*\nabla f\left(x^*\right)=0 và ma trận Hessian \nabla^2 f\left(x^*\right)positive definite. Khi đó  x^* là điểm tối ưu chặt (strict local minimizer) của f\left(x\right).

Nói một cách ngắn gọn (bỏ qua các điều kiện):

  • Nếu \nabla f\left(x^*\right) = 0 thì x^* là tối ưu cục bộ.
  • Nếu \nabla f\left(x^*\right) = 0\nabla^2 f\left(x^*\right)positive semidefinite thì x^* là tối ưu cục bộ.
  • Nếu \nabla f\left(x^*\right) = 0\nabla^2 f\left(x^*\right)positive definite thì x^* là tối ưu cục bộ chặt.

Nhắc lại rằng ma trận vuông \mathbf{M}\in\mathbb{R}^{n\times n} gọi là:

  • negative-semidefinite nếu z^\mathrm{T}Mz \leq 0 với mọi vector z\in\mathbb{R}^n khác 0.
  • negative-definite nếu z^\mathrm{T}Mz < 0 với mọi vector z\in\mathbb{R}^n khác 0.
  • positive-definite nếu z^\mathrm{T}Mz > 0 với mọi vector z\in\mathbb{R}^n khác 0.
  • positive-semidefinite nếu z^\mathrm{T}Mz \geq 0 với mọi vector z\in\mathbb{R}^n khác 0.
  • indefinite nếu nó không phải negative-semidefinite cũng không phải positive-semidefinite.

Nhân tiện cũng nhắc lại mối quan hệ giữa ma trận Hermitian (là các ma trận có  chuyển vị liên hợp bằng chính nó M = M^*) và trị riêng. Ma trận Hermitian M là:

  • negative-semidefinite khi và chỉ khi các trị riêng đều không dương \lambda_i \leq 0.
  • negative-definite khi và chỉ khi các trị riêng đều âm \lambda_i < 0.
  • positive-definite khi và chỉ khi các trị riêng đều dương \lambda_i > 0.
  • positive-semidefinite khi và chỉ khi các trị riêng đều không âm \lambda_i \geq 0.

Trong các điều kiện dừng ta chỉ xét đến tối ưu cục bộ. Trong trường hợp đặc biệt nếu f\left(x\right) là hàm lồi (convex) thì mọi điểm tối uu cục bộ đều là tối ưu toàn cục. Hơn nữa nếu f(x) vừa lồi vừa khả vi thì mọi điểm x^* làm đạo hàm bậc nhất bằng 0 đều là điểm tối ưu toàn cục.

Về lí thuyết, để xét 1 hàm có lồi hay không, ta xét tính chất của ma trận Hessian (đạo hàm bậc 2) trên toàn miền xác định. Theo đó f(x):

  • là hàm lồi  (convex) nếu ma trận Hessian là positive semidefinite tại mọi điểm trên miền xác định.
  • là hàm lồi chặt (strict convex) nếu ma trận Hessian là positive definite tại mọi điểm trên miền xác định.
  • là hàm lõm (concave) nếu -f(x) là hàm lồi.
  • là hàm lõm chặt (strict concave) nếu -f(x) là hàm lồi chặt.

Rõ ràng việc kiểm tra trên toàn miền xác định là bất khả thi, trừ vài trường hợp đơn giản như các hàm bậc 2 thì sẽ có Hessian là hằng v.v…

Trong trường hợp tổng quát, khi việc tính đạo hàm bậc nhất và bậc 2 gặp khó khăn vì không tìm được công thức đạo hàm tường minh, hoặc do giới hạn độ chính xác của máy tính… thì các điều kiện trên trở nên khó kiểm tra. Khi đó ta phải dùng một số điều kiện thực tế. Thuật toán sẽ dừng nếu:

  • độ lớn tương đối của đạo hàm bậc nhất tại x^k đủ nhỏ
    \displaystyle \max_{1\leq i\leq n}\left|\frac{\max{\left\{\left|x_i^k\right|,1\right\}}}{\max{\left\{\left|f\left(x^k\right)\right|,1\right\}}}\nabla f\left(x^k\right)_i\right|\leq \varepsilon^\frac{1}{3}
  • hoặc x^k thay đổi một khoảng đủ nhỏ
    \displaystyle \max_{1\leq i\leq n}\left|\frac{\left|x_i^{k+1}-x_i^k\right|}{\max{\left\{x_i^k,1\right\}}}\right|\leq \varepsilon^\frac{2}{3}

với  \varepsilon là độ chính xác của máy (hàm eps trong MATLAB).

2. Descent direction

Định nghĩa:

d^k\in\mathbb{R}^n là một hướng giảm (descent direction) của một bài toán UNOP tại  x^k nếu:

\exists\bar{\alpha}\in\mathbb{R}^+\vert\forall\alpha\in\left[0,\bar{\alpha}\right]:\;f\left(x^k+\alpha d^k\right)<f\left(x^k\right)

Descent direction

Hình 1: Descent direction

Ý tưởng của định nghĩa này được minh hoạ trong hình trên. Với hàm f(x) như trong hình, tại vị trí x^k, khi đi theo hướng d^k thì giá trị của f\left(x\left(\alpha\right)\right) sẽ giảm dần. Mặc dù đến một lúc nào đó thì giá trị của f\left(x\left(\alpha\right)\right) lại tăng, và còn có thể lớn hơn f(x), nhưng vì ta có thể tìm được \bar{\alpha} theo như định nghĩa nên d^k là hướng giảm của f(x) tại  x^k.

Định nghĩa này rõ ràng rất khó áp dụng do có các toán tử tồn tại và với mọi.  Trong thực tế, ta dùng các điều kiện đơn giản hơn để xét d^k có phải là descent direction hay không, theo đó nếu:

  • \nabla f\left(x\right)d < 0 thì d là hướng giảm (descent direction) của f(x) tại x,
  • \nabla f\left(x\right)d > 0 thì d là hướng tăng (ascent direction) của f(x) tại x,
  • \nabla f\left(x\right)d = 0 thì tùy thuộc vào ma trận Hessian của f(x) tại x.

Như vậy ta chỉ cần xét tích vô hướng của đạo hàm bậc nhất tại x với vector d để kiểm tra điều kiện trên. Ý tưởng này được minh họa trong hình sau. Hàm f(x) với điểm tối ưu tại x^* được khảo sát. Tại x = (0, 0), các mũi tên màu đỏ là các hướng tăng, màu xanh lá là hướng giảm. Tinh ý thì ta sẽ thấy rằng do \nabla f\left(x\right)d là tích vô hướng nên nếu góc giữa \nabla f(x)d lớn hơn \frac{\pi}{2} thì tích vô hướng âm, d là hướng giảm. Đây là nhận xét quan trọng, sẽ có dịp ta trở lại với nó.

Hình 2: Descent direction: điều kiện đủ

Như vậy cho trước một vector d, ta đã có cách để kiểm tra nó có phải là descent direction không. Nhưng vấn đề là tại điểm x^k bất kì, làm sao để tìm hướng giảm d^k? Ta có các phương pháp sau:

  • Sử dụng đạo hàm bậc nhất:
    • Steepest descent (còn gọi là gradient method): d^k = -\nabla f\left(x^k\right).
    • Conjugate Gradient: d^k = -\nabla f\left(x^k\right) + \beta^kd^{k-1}.
    • Quasi-Newton: d^k = -\mathbf{B}^k\nabla f\left(x^k\right), trong đó các \mathbf{B}^k là ma trận đối xứng, positive definite.
  • Sử dụng đạo hàm bậc 2:
    • Phương pháp Newton: d^k = -\left[\nabla^2 f\left(x^k\right)\right]^{-1}\nabla f\left(x^k\right)

Tính chất của mỗi phương pháp sẽ được trình bày chi tiết sau.

3. Steplength: Thuật toán line search

Như vậy tại điểm x^k ta xác định được hướng giảm d^k, do đó x^{k+1} phải nằm trên nửa đường thẳng  x\left(\alpha\right)=x^k+\alpha d^k,\;\left(\alpha > 0\right). Vấn đề là ta phải xác định xem ta cần đi xa bao nhiêu trên nửa đường thẳng này, nghĩa là phải xác định độ dài bước tốt nhất \alpha^*.

Line search là thuật toán thực hiện việc này, và rõ ràng bản thân line search cũng là một bài toán tối ưu:

\alpha^*=\arg\min\left\{f\left(x+\alpha d \vert \alpha \leq 0\right)\right\}

Sở dĩ ta cực tiểu f\left(x+\alpha d\right) là vì không những ta muốn tìm \alpha tốt nhất, mà còn muốn thuật toán kết thúc nhanh nhất có thể.

Ta có thể giải chính xác bài toán line search bằng cách lấy đạo hàm của f\left(x\left(\alpha\right)\right) để tìm giá trị của  \alpha tại điểm cực trị.

Chẳng hạn xét lại ví dụ trong hình 2: min_{x\in\mathbb{R}^n} f\left(x\right) = 0.875x_1^2 + 0.8x_2^2 - 350x_1 - 300x_2. Tại x=\left(0, 0\right)^\mathrm{T}, hướng giảm (tính theo steepest descent) là d = -\nabla f\left(x\right)'=\left(350, 300\right)^\mathrm{T}. Ta có thể kiểm tra \nabla f\left(x\right)d < 0 nên d là hướng giảm của f(x) tại x. Ta có:

f\left(x\left(\alpha\right)\right) = f\left(x+\alpha d\right) = 179187.5\alpha^2 - 212500\alpha, và

\frac{\partial f\left(x\left(\alpha\right)\right)}{\partial \alpha}=0 \Leftrightarrow \alpha^* = 0.5939.

Như vậy ta đã chọn được \alpha^k và có thể tiếp tục bước 3.3 trong Thuật toán 1.

Tuy nhiên trong nhiều trường hợp, việc tính đạo hàm của f\left(x\left(\alpha\right)\right) là bất khả thi nên ta cần cách khác để tìm \alpha^*, và đó chính là nội dung của thuật toán linesearch. Mục tiêu của linesearch là xác định xấp xỉ  \alpha^k\approx \arg\min\left\{f\left(x^k+\alpha d^k\right)\vert \alpha \geq 0\right\} sao cho nó làm giảm độ lớn của f(x), tiến gần hơn về cực tiểu, đồng thời không tốn quá nhiều chi phí tính toán.

Thuật toán 2: Thuật toán backtracking line search

1. Định nghĩa tiêu chuẩn chấp nhận (acceptability) cho \alpha^k.

2. Đặt \alpha:=\alpha_{max}, bước thử đầu cho \alpha.

3. Lặp cho đến khi  \alpha thỏa tiêu chuẩn chấp nhận

Bằng cách nào đó (chia đôi, giảm dần, nội suy…) tìm bước thử mới cho \alpha sao cho \alpha < \alpha_{max}.

4. Đặt \alpha^k:=\alpha.

Trong bước 3, để tìm bước thử mới cho \alpha, ta có thể:

  • Chia \alpha cho một hằng số k nào đó, như vậy các giá trị của  \alpha lần lượt là \alpha_{max}, \frac{\alpha_{max}}{k}, \frac{\alpha_{max}}{k^2}\cdots. Đến khi nào thỏa điều kiện thì ngừng.
  • Trừ dần  \alpha cho một hằng số c nào đó, các giá trị của  \alpha lần lượt là \alpha_{max}, \alpha_{max}-c, \alpha_{max}-2c\cdots.
  • Dùng một hàm nào đó để nội suy giá trị của \alpha. Thông thường ta sẽ dùng một hàm bậc 2 g\left(\alpha\right)=a\alpha^2+b\alpha+c. Nhận xét rằng
    g\left(0\right)=f\left(x^k\right)
    g'\left(0\right)=\nabla f\left(x^k\right)d^k
    f\left(\alpha_{max}\right)=f\left(x^k+\alpha_{max}d^k\right)
    ta có 3 phương trình để tìm các hệ số a, bc của  g\left(\alpha\right). Sau khi có công thức hàm g\left(\alpha\right) thì có thể chọn \alpha bất kì trong đoạn \left[0, \alpha_{max}\right]. Một ví dụ ở cuối bài sẽ minh họa cách làm này.

Mảnh ghép cuối cùng còn thiếu của thuật toán là tiêu chuẩn chấp nhận trong Thuật toán 2. Người ta hay dùng tiêu chuẩn Wolfe, còn gọi là tiêu chuẩn Armijo-Goldstein. Tiêu chuẩn này gồm 2 bất phương trình sau:

f\left(x^k+\alpha d^k\right) \leq f\left(x^k\right) + \left[c_1\nabla f\left(x^k\right)d^k\right].\alpha     (1)

\nabla f\left(x^k+\alpha d^k\right)d^k\geq c_2\nabla f\left(x^k\right)d^k         (2)

với  c_1, c_2 là các hằng số thỏa 0 < c_1 < c_2 < 1.

Hình 3: Minh họa tiêu chuẩn Armijo-Goldstein

Hình 3 minh họa các tiêu chuẩn này. Đồ thị của hàm \Phi\left(\alpha\right)=f\left(x^k+\alpha d^k\right) (vế trái của (1)) được vẽ trong hình. Gốc tọa độ là tại vị trí \alpha = 0. Đường màu cam là đồ thị vế bên phải của (1). Do đó ý nghĩa của tiêu chuẩn (1) là chỉ những \alpha nằm trong đoạn màu cam được chọn. Tiêu chuẩn (2) dựa vào hệ số góc của tiếp tuyến tại x_0. Nhận xét rằng càng gần điểm cực trị (local optima), tiếp tuyến tại vị trí đó sẽ càng ít dốc, do đó điều kiện (2) đảm bảo ta đang tiến gần về local optimum. Như vậy chỉ những \alpha nằm trong đoạn màu vàng mới được chọn theo tiêu chuẩn (2). Cuối cùng phần giao sẽ là những  \alpha thỏa cả 2 tiêu chuẩn trên. Tiêu chuẩn (1) rất quan trọng vì nó đảm bảo thuật toán sẽ hội tụ, tiêu chuẩn (2) chỉ là một kĩ thuật thêm vào. Trong vai trường hợp khó, nếu ta không thể chọn steplength rơi vào trong vùng thỏa điều kiện (2) thì thuật toán có thể không dừng, do đó cần phải thận trọng.

Ta sẽ làm rõ line search bằng một ví dụ.

4. Ví dụ

Cho hàm f\left(x\right) = x_1^3 + x_1x_2 + \frac{2x_1}{x_2}.

1. Tại điểm x^k=\left[1 1\right]^\mathrm{T}, kiểm tra d^k = \left[0 -1\right]^\mathrm{T} có phải là hướng giảm của f(x) không. Nếu không hãy tìm một hướng giảm thỏa điều kiện.

2. Thực hiện bước đầu tiên của thuật toán line search tại x^k theo hướng  d^k bằng phương pháp nội suy bậc 2, các tham số  \alpha_max = 1, c_1 = 0.01, c_2 = 0.5.

1. Ta có

\nabla f\left(x\right)=\left[\begin{array}{cc} 3x_{1}^{2}+x_{2}+\frac{2}{x_{2}} & x_{1}-\frac{2x_{1}}{x_{2}^{2}}\end{array}\right]\Rightarrow\nabla f\left(x^{k}\right)=\left[\begin{array}{cc} 6 & -1\end{array}\right].

\nabla f\left(x^{k}\right)d^{k}=\left[\begin{array}{cc}6 & -1\end{array}\right]\left[\begin{array}{c}0\\-1\end{array}\right]=1>0

nên d^{k} là hướng tăng của f\left(x\right) tại x^{k} (chứ không phải hướng giảm).

Có thể chọn hướng giảm của f\left(x\right) tại x^{k}d^{k}=\left[\begin{array}{cc}-1 & 0\end{array}\right]^{\mathrm{T}}\nabla f\left(x^{k}\right)d^{k}=\left[\begin{array}{cc}6 & -1\end{array}\right].\left[\begin{array}{c}-1\\\mathbf{0}\end{array}\right]=-6<0

2. Line search tại x^{k}=\left[\begin{array}{cc}1 & 1\end{array}\right]^{\mathrm{T}} với  \quad d^{k}=\left[\begin{array}{cc}-1 & 0\end{array}\right]^{\mathrm{T}},\quad\alpha_{max}=1,\quad c_{1}=0.01,\quad c_{2}=0.5.

Ta có:

f\left(x^{k}\right)=4,\quad\nabla f\left(x^{k}\right)=\left[\begin{array}{cc}6 & -1\end{array}\right],

\quad\nabla f\left(x^{k}\right)d^{k}=-6,\quad f\left(x^{k}+\alpha_{max}d^{k}\right)=f\left(\left[\begin{array}{c}0\\1\end{array}\right]\right)=0.

Nội suy bậc 2: hàm bậc 2 của  \alpha có dạng g\left(\alpha\right)=a\alpha^{2}+b\alpha+c và thỏa:
\begin{cases}g\left(0\right) & =f\left(x^{k}\right)\\g'\left(0\right) & =\nabla f\left(x^{k}\right)d^{k}\\g\left(\alpha_{max}\right) & =f\left(x^{k}+\alpha_{max}d^{k}\right)\end{cases}\Leftrightarrow\begin{cases}c & =4\\b & =-6\\a & =2\end{cases}

Vậy g\left(\alpha\right)=2\alpha^{2}-6\alpha+4

g'\left(\alpha_{g}\right)=4\alpha_{g}-6=0\Leftrightarrow\alpha_{g}=\frac{3}{2}.

Ta có thể chọn \alpha_{g}=\min\left(\frac{3}{2},\alpha_{max}\right)=1.

Kiểm tra tiêu chuẩn Armijo-Goldstein với \alpha_{g} bằng MATLAB:


function [ f ] = prob6_func( x )
  f = x(1)^3 + x(1)*x(2) + 2*x(1)/x(2);
end

function [ g ] = prob6_grad( x )
  g = zeros(1, 2);
  g(1, 1) = 3*x(1)^2 + x(2) + 2/x(2);
  g(1, 2) = x(1) - 2*x(1)/(x(2)^2);
end

>> xk = [1; 1]; dk = [-1; 0];
>> alpha_g = 1;
>> c1 = 0.01; c2 = 0.5;
>> l1 = prob6_func(xk+alpha_g*dk);
>> r1 = prob6_func(xk)+alpha_g*c1*(prob6_grad(xk)*dk);
>> l1 <= r1
  ans =
    1
>> l2 = prob6_grad(xk+alpha_g*dk)*dk;
>> r2 = c2*(prob6_grad(xk)*dk);
>> l2 >= r2
  ans =
    1

Vậy \alpha_{g}=1 thỏa tiêu chuẩn A-G.

5. Kết luận

Bài này tổng quan về các bài toán tối ưu phi tuyến không ràng buộc, đồng thời làm rõ thuật toán line search như một bước quan trọng trong thuật toán chung.

Tuy nhiên bài này chưa trình bày rõ các phương pháp chọn hướng giảm như Steepest Descent hay Conjugate Gradient. Để có thể đánh giá, lựa chọn giữa các phương pháp này, ta cần biết cách đánh giá mức độ hội tụ của một thuật toán tối ưu. Bài tiếp theo trong series Optimization sẽ nói về hội tụ cục bộ, hội tụ toàn cục, định lí Zoutendijk, hội tụ tuyến tính, siêu tuyến tính… Đây sẽ là cơ sở để đánh giá các phương pháp chọn hướng giảm mà ta đã nhắc tới trong bài này.

Advertisements

6 comments

  1. anh gì đó ơi. chắc anh đang nghiên cứu về hướng giảm phải không? không biết anh còn tài liêu nào hác không? không biết anh có thể cho em đươc không cảm ơn anh nhiều. nếu được xin nh gửi đến mail: thaianh_choino@yahoo.com.vn
    cảm ơn anh nhiều

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s