Constrained Optimization – Intuition for the First and Second order conditions

Trong bài trước, ta liệt kê các điều kiện bậc nhất và bậc 2 cho bài toán tối ưu có ràng buộc. So với tối ưu không ràng buộc, việc xuất hiện toán tử Lagrange làm cho bài toán tối ưu có ràng buộc trở nên ít trực quan hơn. Bài này sẽ giải thích nôm na các điều kiện này, lí giải tại sao nếu một điểm feasible point thỏa cả 2 điều kiện thì nó sẽ là local optimum. Việc hiểu ý nghĩa của các điều kiệu này là rất cần thiết cho việc hiểu các phương pháp tối ưu như active set, simplex method .v.v… mà ta sẽ lần lượt giới thiệu sau.

Ý tưởng chung của các phương pháp tối ưu có ràng buộc là bắt đầu từ vị trí khởi đầu (feasible point), ta di chuyển trong không gian tạo bởi các ràng buộc, sao cho nó tối thiểu hóa hàm mục tiêu. Muốn làm được vậy, tại mỗi vị trí, ta phải tính hướng di chuyển tiếp theo  sao cho đi theo hướng đó thì sẽ giảm được giá trị hàm mục tiêu (hướng như vậy gọi là feasible descent direction). Tuy nhiên vấn đề là đi theo hướng đó một đoạn bao nhiêu. Ta xác định độ dài phải đi (steplength) bằng thuật toán linesearch. Cứ tiếp tục như vậy đến khi không thể tìm được feasible descent direction thì dừng.

Đây là tư tưởng chung nhất của tất cả các thuật toán tối ưu ta sẽ tìm hiểu, tuy nhiên tùy vào đặc trưng của hàm mục tiêu (tuyến tính, bậc 2 hay phi tuyến) và của ràng buộc (ràng buộc tuyến tính đẳng thức hay bất đẳng thức, ràng buộc phi tuyến v.v…) mà cách tính feasible point, feasible descent direction và linesearch sẽ khác nhau. Thực tế phần quan trọng nhất trong thuật toán tối ưu là linesearch. Một cài đặt tốt cho linesearch có thể lên đến vài chục trang mã nguồn vì có quá nhiều điều kiện cần phải kiểm tra, và với mỗi trường hợp lại phải xử lí khác nhau. Tất nhiên mục đích của ta không phải là cài đặt lại các thuật toán này, nhưng nói vậy để thấy sự phức tạp của linesearch và các thuật toán tối ưu nói chung.

Trở lại với các điều kiện bậc nhất và bậc 2, ta sẽ giải thích nôm na các điều kiện này bằng ví dụ đơn giản sau

1. Tối ưu với ràng buộc đẳng thức

{\displaystyle \min_x f\left(x\right)=x_1+x_2\quad \text{s.t.}\; h\left(x\right)=x_1^2+x_2^2-1=0}

Hình sau đây minh họa toàn bộ bài toán này:

Minh họa điều kiện bậc nhất và bậc 2 tối ưu có ràng buộc

Trong hình trên, các đường nét đứt thể hiện contour của hàm f(x): các điểm nằm trên cùng 1 đường contour có cùng giá trị của f(x). Không gian tạo bởi ràng buộc h\left(x\right)=x_1^2+x_2^2=1 chính là đường tròn tâm O bán kính 1. Như vậy ý tưởng là ta di chuyển trên đường tròn này, tìm điểm mà làm cực tiểu hàm mục tiêu f(x). Ta sẽ dùng hình này để giải thích các điều kiện bậc 1 và bậc 2.

Nhắc lại rằng với ràng buộc đẳng thức, điều kiện bậc 1 là đạo hàm bậc nhất của hàm Lagrangian bằng 0:

\displaystyle \nabla_x L\left(x^*, \lambda^*\right)=\nabla f\left(x^*\right) + \lambda^{*\top}\nabla h\left(x^*\right) = 0^\top

và điều kiện bậc 2 là ma trận sau đây là positive definite:

\displaystyle Z^\top\nabla_x^2L\left(x^*,\lambda^*\right)Z

với \nabla_x^2L\left(x^*,\lambda^*\right) = \nabla^2 f\left(x^*\right) + \sum_{j=1}^m\lambda_j^*\nabla^2 h_j\left(x^*\right) là ma trận Hessian của f(x), và Z là cơ sở của không gian tangent plane. Chi tiết xem trong bài trước.

Ý tưởng của điều kiện bậc nhất là tại điểm cực trị x*, vector đạo hàm của hàm mục tiêu \nabla f\left(x^*\right) và vector đạo hàm của ràng buộc \nabla h\left(x^*\right) phải phụ thuộc tuyến tính, với hệ số là \lambda^*.

Cụ thể trên hình, xét điểm A không phải là điểm cực trị, ta có \nabla h\left(x_A\right) là đạo hàm của h(x) tại x_A, nên nó trực giao với đồ thị của h(x). Ta cũng có \nabla f\left(x_A\right) là đạo hàm của f(x) tại x_A, nên nó vuông góc với contour của f(x) (thực ra có thể tính ngay được \nabla f\left(x\right) = \left[1\;1\right]). Rõ ràng trong trường hợp này, \nabla h\left(x_A\right)\nabla f\left(x_A\right) không phụ thuộc tuyến tính (không cùng phương). Ta cũng có Z là cơ sở của tagent plane. Nhắc lại rằng tagent plane là không gian vuông góc  với \nabla h\left(x_A\right) nên được vẽ bằng đường màu đỏ đi qua x_A trong hình. Nhận xét rằng tagent plane là không gian tiếp tuyến tại x_A của h(x), nên thay vì di chuyển trong không gian h(x), ta có thể di chuyển một khoảng nhỏ trong không gian  tagent plane sao cho nó giảm giá trị của hàm mục tiêu f(x). Để giảm được giá trị của f(x) thì hướng di chuyển phải ngược chiều với \nabla f\left(x_A\right), do đó là chiều của mũi tên màu xanh như trong hình. Rõ ràng tại x_A, ta còn có thể di chuyển trong tagent plane theo chiều mũi tên để giảm hơn nữa giá trị của hàm f(x).

Tuy nhiên tại x_C, đạo hàm \nabla h\left(x_C\right) vuông góc với h(x), và \nabla f\left(x_C\right) vuông góc với contour của f(x), nên thành ra \nabla h\left(x_C\right)\nabla f\left(x_C\right) cùng phương (phụ thuộc tuyến tính). Rõ ràng trong trường hợp này, ta vẫn có không gian tagent plane (được vẽ bằng màu đỏ), nhưng vì tagent plane cũng vuông góc với \nabla f\left(x_C\right) nên ta không thể di chuyển trong tagent plane để giảm giá trị của f(x) được nữa. Tagent plane tại x_C trùng với đường contour của f(x) nên mọi điểm trong tagent plane đều cho giá trị f(x) như nhau. Rõ ràng vì không thể tìm được hướng di chuyển nữa nên x_C là một điểm cực trị. Tình hình cũng tương tự tại x_B.

Như vậy với bài toán này, điều kiện bậc nhất sẽ đúng tại x_Bx_C. Tóm lại điều kiện bậc nhất kiểm tra điểm cực trị, và điều kiện bậc 2 kiểm tra xem đó là điểm cực đại hay cực tiểu. Trong ví dụ này, cả x_Bx_C đều thỏa điều kiện bậc 1, nhưng chỉ x_B mới thỏa điều kiện bậc 2.

Thực tế với bài toán đơn giản này, ta có thể giải bằng tay không mấy khó khăn.

Kiểm tra điều kiện bậc 1: nhận xét rằng điểm x thỏa điều kiện bậc 1 thì \nabla_x L\left(x, \lambda\right) = 0, và x phải nằm trong không gian của ràng buộc nên h\left(x\right) = 0. Như vậy ta được hệ sau:

\begin{cases} \nabla f\left(x\right)+\lambda\nabla h\left(x\right) & =\left[\begin{array}{c} 1\\ 1\end{array}\right]+ \lambda\left[\begin{array}{c} 2x_{1}\\ 2x_{2}\end{array}\right]=0\\ h\left(x\right) & =x_{1}^{2}+x_{2}^{2}-1=0\end{cases}

\Leftrightarrow\begin{cases} x_{1} & =x_{2}\\ x_{1}^{2}+x_{2}^{2} & =1\end{cases}\Leftrightarrow x_{1}=x_{2}=\pm\frac{1}{\sqrt{2}}

Như vậy ta được 2 điểm cực trị là \left[\frac{1}{\sqrt{2}}\;\frac{1}{\sqrt{2}}\right]^\top\left[\frac{-1}{\sqrt{2}}\;\frac{-1}{\sqrt{2}}\right]^\top. Việc còn lại là kiểm tra điều kiện bậc 2.

Trong trường hợp tổng quát, mỗi ràng buộc có một nhân tử lagrange nên ta có p nhân tử lagrange cho hệ n phương trình \nabla f\left(x\right)+\lambda\nabla h\left(x\right) = 0. Ngoài ra ràng buộc h\left(x\right) = 0 cũng có p phương trình cho n ẩn (nhớ rằng x\in\mathbb{R}^n). Do đó hệ:

\begin{cases} \nabla f\left(x\right)+\lambda\nabla h\left(x\right) & =0\\ h\left(x\right) & =0\end{cases}

(n+p) phương trình và (n+p) ẩn, nên về lí thuyết là giải được. Tuy nhiên trong trường hợp tổng quát, việc tính bằng tay như trên là không khả thi, do đó các thuật toán phức tạp hơn được đề xuất, và ta sẽ lần lượt tìm hiểu sau.

2. Tối ưu với ràng buộc bất đẳng thức

Nhắc lại rằng điều kiện cho bài toán ràng buộc có bất đẳng thức là:

\begin{array}{r}\nabla_x \mathcal{L}\left(x^*,\lambda^*, \mu^*\right) = \nabla f\left(x^*\right) + \lambda^{*\top} \nabla h\left(x^*\right) + \mu^{*\top} \nabla g\left(x^*\right)= 0^\top \\ \mu^{*\top}g\left(x^*\right) = 0\\ \mu^* \geq 0 \end{array}

Điều kiện thứ 2 và thứ 3 có vẻ hơi thiếu tự nhiên. Thực tế \mu^{*\top}g\left(x^*\right) = 0 có nghĩa là với mọi ràng buộc bất đẳng thức g_j\left(x\right), hoặc g_j\left(x\right) = 0 hoặc nhân tử Lagrange \mu_j = 0. Nếu g_j\left(x\right) < 0 thì điều kiện này đảm bảo \mu_j = 0, khi đó ràng buộc bất đẳng thứ này là vô hiệu (inactive) trong điều kiện 1. Ngược lại nếu g_j\left(x\right) = 0 thì ràng buộc này đang active, và \mu_j có thể lớn hơn hay bằng 0.

Để dễ hiểu, ta xét bài toán sau:

{\displaystyle \min_x f\left(x\right)=x_1+x_2\quad \text{s.t.}\; g\left(x\right)=x_1^2+x_2^2-1\leq 0}

Khi đó không gian tạo bởi ràng buộc g\left(x\right) là cả đường tròn bán kính 1 như vẽ trong hình. g\left(x\right) < 0 tương ứng với trường hợp x nằm hẳn bên trong đường tròn, do đó ràng buộc này không có ý nghĩa gì đối với đạo hàm của hàm Lagrange. Ngược lại g\left(x\right) = 0 tương ứng với trường hợp x nằm trên đường tròn.

3. Tổng kết

Bài này giải thích nôm na điều kiện bậc nhất của tối ưu có ràng buộc. Ta chỉ giải thích bằng ví dụ trong không gian 2 chiều, nhưng người đọc có thể tự tưởng tượng cho không gian 3 chiều hoặc cao hơn.

Advertisements

One comment

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